chanmyung

힙 정렬(HeapSort) 힙이란? http://devheat.tistory.com/12 참고 설명 힙의 최상위 노드에는 가장 큰 값이 존재한다는 특성을 이용해 정렬하는 알고리즘 최대 힙 혹은 최소 힙의 노드 삭제를 연속으로 수행해 값이 가장 큰 노드부터 내림차순 혹은 오름차순으로 꺼낼 수 있다. 구현 구현은 이전 포스팅 http://devheat.tistory.com/12 에서 만든 delete 메소드를 연달아 호출하면 된다. 최상위 노드를 꺼내고, 최하위 노드를 최상위에 위치시켜 다시 하향 heapify를 수행하는 것이 핵심 소스코드 번외 이전 포스트와 마찬가지로 Generic Heap에도 정렬 기능을 추가할 수 있다. 구현 힙 사용 예제 (Comparable을 구현한 String 클래스를 사용)

삽입 정렬(Insertion Sort) 설명 오름차순의 경우 K번째 원소를 이전 원소와 비교하며 이전 원소가 K번째 원소보다 작을 때 까지 이전 원소를 다음 인덱스의 값으로 이동시킨다. 그 후 그 자리에 K번째 원소를 끼워 넣는다. 동작 동작 예시 정수형 배열이 [5, 3, 2, 4, 1] 5개의 원소를 가질 때 오름차순 정렬 인덱스는 1부터 시작 (이전 원소와 비교해야 하는데 0은 이전 원소가 없다.) 3과 5 비교, 밀어내기 O [5, 5, 2, 4, 1] 3을 0번지에 끼워 넣음 [3, 5, 2, 4, 1] 2와 5 비교, 밀어내기 O [3, 5, 5, 4, 1] 2와 3 비교, 밀어내기 O [3, 3, 5, 4, 1] 2를 0번지에 끼워 넣음 [2, 3, 5, 4, 1] 이를 반복 시간 복잡도 O..

정렬의 기초, 버블 정렬(Bubble Sort) 설명 가장 직관적이고 대부분의 경우 가장 비효율적인 정렬 알고리즘 따라서 거의 쓰이지 않는다. 동작 구현에 따라 달라지지만 통상 가장 오른 원소부터 차례대로 자리를 찾아가게됨 자신과 자신의 다음 원소를 비교하고, Swap 여부를 결정 동작 예시 정수형 배열이 [1, 2, 4, 2, 5, 7, 1, 3, 9, 8] 10개의 원소를 가졌을 때 오름차순 정렬 시작: [1, 2, 4, 2, 5, 7, 1, 3, 9, 8] 1과 2 비교, Swap X [1, 2, 4, 2, 5, 7, 1, 3, 9, 8] 2와 4 비교, Swap X [1, 2, 4, 2, 5, 7, 1, 3, 9, 8] 4와 2 비교, Swap O [1, 2, 2, 4, 5, 7, 1, 3, 9,..