Algorithm/Sorting Algorithm

Heap Sort

What is Heap? 최대값이나 최소값을 찾아내는 연산을 빠르게 찾아내기 위해 고안된, 완전이진트리 를 기본으로 한 자료구조이다. 완전이진트리는 노드의 맨 마지막 리프 부분을 제외하고는 모든 level이 완전하게 채워져 있으며, 가능하면 왼쪽부터 채워진 구조이다. 그리고 Heap에는 Min-Heap과 Max-Heap이 있다. Min-Heap은 부모 노드에 자신보다 작은 값을 둬서 트리의 루트에는 가장 작은 값이 오게 한다. 반대로 Max-Heap은 부모 노드에 자신보다 큰 값을 둬서 트리의 루트에는 가장 큰 값이 오게 한다. Min-Heap에 대해서 알면 Max-Heap의 구현도 간단해지니 Min-Heap을 한 번 살펴보자. Min-Heap에 노드 삽입하기 우선 완전이진트리의 맨 끝에 추가한다. 추가..

Insertion Sort

Insertion Sort 개념 마치 손에서 카드 놀이를 하는 듯한 간단한 정렬 Algorithm이다. Insertion Sort에서 배열은 정렬된 부분과 정렬되지 않은 부분으로 나누어서 본다. 정렬되지 않은 부분에서 값을 하나씩 꺼내와서, 정렬된 부분에서 해당 값이 있을 수 있는 올바른 위치에 배치한다. 배열의 길이가 n인 배열을 오름차순으로 정렬하기 위한 세부적인 작동은 다음과 같다. arr[1]부터 arr[n]까지 반복 꺼내온 값(key)과 정렬된 부분 배열의 값들을 뒤쪽부터 차례대로 비교 key 값이 비교 대상보다 작은 경우, 정렬된 부분에서의 보다 앞의 값들과 계속해서 비교 Java 구현 class InsertionSort { void sort(int arr[]) { int n = arr.len..

Selection Sort

Selection Sort 개념 배열을 돌면서 가장 작은 값을 찾아내면서 맨 앞으로 옮기는 정렬 방식이다. 초기의 가장 작은 값은 시작값으로 지정하고, 배열을 loop하면서 보다 작은 값이 있으면 가장 작은 값으로 지정한다. 그리고 찾아낸 가장 작은 값을 배열의 맨 앞 요소와 교체해준다. 이런 식으로 배열의 길이만큼 반복하며 정렬해준다. 가장 작은 값을 찾아내기 위한 배열 내 loop를 다시 배열의 길이만큼 찾아내야 하기 때문에 O(n²) 의 시간복잡도를 가진다. 한 번 배열을 돌 때마다 정렬해야 하는 요소도 하나씩 줄어들지만, 그래도 square의 절반의 면적이 나오기 때문에 O(n²) 시간복잡도를 가진다고 말한다. Java로 구현하기 public class Test { public static voi..

Bubble Sort

Bubble Sort 개념 앞에서부터 2개씩, 인접한 요소들끼리 비교해서 작은 값을 앞으로, 큰 값을 뒤로 배치한다. (맨 뒤에서부터 시작하는 것도 가능하다.) 이 작업을 배열의 끝까지 도달하면서 정렬하는 방법이다. 그렇게 한번 배열의 끝까지 도달하는 과정을 거쳤다면 해당 배열의 맨 마지막 요소는 해당 배열에서 가장 큰 값이 된다. 한번 loop를 돌 때마다 끝 쪽에 요소 하나씩은 정해지니, 하나씩 비교하는 loop 자체를 배열의 길이만큼 돌려야 한다. 배열 내 요소의 갯수만큼 반복하는 작업을 다시 배열 내 요소의 갯수만큼 순회하게 되니 이 작업은 O(n²) 의 시간복잡도를 가진다. 물론 인접 요소끼리 비교하는 loop를 한번 돌 때마다 비교해야 하는 요소가 하나씩 빠지기는 하지만, 결국 square에서..

Merge Sort

기본 원리 우선 2개의 정렬된 배열이 있다고 가정해보자. 이 2개의 배열을 하나의 정렬된 배열로 만들고 싶다면, 두 배열의 첫번째 인덱스를 비교해가면서 더 작은 값을 빼내어 새로 만들 배열에 추가해주면 된다. Merge Sort는 배열을 쪼개는 과정부터 시작한다. 우선 각 배열의 길이가 2가 될 때까지 배열을 계속해서 둘로 나눈다. 다 쪼개졌으면 위에서 살펴본 방식대로 배열 안의 값들을 서로 비교하면서 작은 값을 먼저 삽입한다. 이렇게 각 배열의 길이가 2이고, 그 안에서 정렬된 배열들을 똑같은 방법으로 길이가 4이며, 그 안에서 정렬된 배열로 합쳐준다. 이런 식으로 다시 원본 배열의 전체 길이가 될 때까지 합치면서 돌아온다. 이렇듯 함수가 호출될 때마다 절반씩 잘라서 재귀적으로 함수를 호출하고, 작은 ..

Quick Sort

What is Quick Sort? 배열 안에서 기준점(pivot)을 잡고, 해당 기준점보다 작으면 왼쪽으로, 크면 오른쪽으로 옮긴다. 이 때, 기준점 양 옆으로 배열이 partition 2개로 나뉘는데, 왼쪽 따로 정렬하고 오른쪽 따로 정렬하는 작업을 재귀적으로 반복하면 완전히 정렬된 배열을 얻을 수 있게 된다. Quick Sort의 시간 복잡도 평균적으로 O(n log n)이라고 볼 수 있다. 최악의 경우 O(n²) 복잡도가 나오기는 하지만 보통의 경우에는 O(n log n)의 복잡도를 가진다고 설명한다. 그렇다면 왜 O(n log n)의 복잡도를 가진다고 보는지 그 이유를 살펴보자. 일단 partition을 나누는 횟수는 n번이다. 파티션의 데이터가 낱개가 될 때까지 나누게 되는 것이다. 그런데 한..