Knowledge/Algorithm (13) 썸네일형 리스트형 Insertion Sort (삽입정렬) 삽입정렬(Insertion Sort)란? 삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여,자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.선택정렬이나 버블정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.이미 정렬되어 있는 경우에는 한번씩 밖에 비교를 하지 않기 때문에 시간 복잡도가 O(n)이 된다. 예를 들어 카드 게임을 할 때, 내 손에는 이미 정렬된 카드가 있고, 새로운 카드를 받아 카드 사이의 올바른 자리를찾아 삽입함으로써 정렬이 유지되게 하는 것이다. import java.util.Scanner; /** * Created by Itner o.. Bubble Sort (버블 정렬) 버블 정렬(Bubble Sort)란? 버블정렬은 두 인접한 원소를 비교하여 정렬하는 방법이다. 시간복잡도가 로 상당히 느리지만,코드가 단순하기 때문에 자주 사용된다. 레코드의 이동이 마치 거품이 수면 위로 올라오는 듯한 모습을 보이기 때문에 붙여진 이름이다. 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다.이러한 비교-교환 과정을 스캔이라 하며, 스캔이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽끝으로 이동하게된다. 이러한 스캔은 정렬이 완료될 때까지 반복된다. import java.util.Scanner; /** * Created by Itner on 2017. 7. 19.. */ public class BubbleSort_Rz { public static vo.. Selection Sort (선택정렬) 선택정렬(Selection Sort)란? 선택정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.1. 주어진 리스트 중에 최소값을 찾는다.2. 그 값을 맨 앞에 위치한 값과 교체한다.3. 맨 앞에 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로정렬하는데에 Θ(n2) 만큼의 시간이 걸린다. import java.util.Scanner; /** * Created by Itner on 2017. 7. 19.. */ public class SelectionSort_Rz { public static void main(String[] ar) throws Exception { Scanner scan =.. Doubly Linked List (이중 연결 리스트) 이중 연결 리스트(Doubly Linked List)란? 단순 연결 리스트의 경우 노드는 다음 노드에 대한 참조만 가지고 있으므로 단방향으로 밖에 탐색을 하지 못한다.이중 연결 리스트는 이를 보완하여 다음 노드뿐만 아니라 이전 노드의 참조까지 추가하여양방향으로 탐색이 가능하도록 만들어 검색속도를 향상시킬 수 있는 방법을 제공한다. package datastructure; public class DoublyLinkedList_Rz {class DoublyLinkedList{private Node head;private int size;public DoublyLinkedList(){head = new Node(null);size = 0;}private class Node{private Object data;.. Simple Linked List (단순 연결 리스트) 단순연결리스트(Simple LinkedList)란? 단순연결리스트는 각 노드에 자료 공간과 한 개의 포인터 공간이 있고,각 노드의 포인터는 다음 노드를 가르키는 하나의 참조만을 갖는다.다음 노드의 참조만 가지고 있으므로 노드의 접근은 한 방향으로만 가능하다. public class SimpleLinkedList_Rz { class SimpleLinkedList{private Node head;private int size; public SimpleLinkedList(){head = new Node(null);size = 0;} private class Node{private Object data; // 데이터가 저장될 필드private Node nextNode; // 다음 노드를 가르키는 필드 publi.. 이전 1 2 다음
