Dev 일기장

Heap Sort

• Heap 자료구조를 이용하여 정렬하는 방식
• Best case, Worst case 모두 시간 복잡도가 \(O(nlogn)\)
  • 그러나 대체로 Quick Sort보다 느림
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬

• 

Heap (약식)

• 최댓/최솟값을 찾는 연산을 빠르게 하기위해 고안된 자료구조
• 완전 이진트리(Complete Binary Tree)
• 부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높음
• index i에 대해서
  • 왼쪽 자식 노드의 index: \(i * 2 + 1\)
  • 오른쪽 자식 노드의 index: \(i * 2 + 2\)
  • 부모 노드의 index: \(i / 2\)
• 구조적으로 Tree이지만 배열로 표현가능
  •  

    

동작

Step 1. 배열을 Heap으로 만든다.

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높다

Step 1-1. 

Step 1-2.

Step 1-3.

Step 2. 첫번째 index와 마지막 index를 swap 후 heap size를 1 줄인다.

Step 2-1.

Step 2-2.

Step 2-3.

Step 2-4.

Step 2-5.

Step 2-6.

코드

public class Sort {
	
    public void heapSort(int[] arr) {
    	int lastIndex = arr.length - 1;
        buildHeap(arr, lastIndex);
        
        for(int i = lastIndex; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i-1);
        }
    }
    
    public void buildHeap(int[] arr, int lastIndex) {
    	int parent = (lastIndex - 1) / 2;
        
        for(int i = parent; i >= 0; i--) {
            heapify(arr, i, lastIndex);
        }
    }
    
    public void heapify(int[] arr, int parentIndex, int lastIndex) {
    	int leftChildIndex = parentIndex * 2 + 1;
        int rightChildIndex = parentIndex * 2 + 2;
        int largestIndex = parentIndex;
        
        if(leftChildIndex > lastIndex) {
        	return;
        }
        
        if(arr[leftChildIndex] > arr[largestIndex]) {
        	largestIndex = leftChildIndex;
        }
        
        if(rightChildIndex < lastIndex && arr[rightChildIndex] > arr[largestIndex]) {
        	largestIndex = rightChildIndex;
        }
        
        if(largestIndex != parentIndex) {
        	swap(arr, largestIndex, parentIndex);
            heapify(arr, largestIndex, lastIndex);
        }
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 \(O(nlogn)\)일까?

Heap Sort의 의사코드를 보면 다음과 같다.

HeapSort(arr) {

    buildHeap(arr) // O(n)
    
    // O(nlogn)
    for( i = heapLastIndex ~ 0 ) {
        swap(arr, i, heapLastIndex)
        heapify(arr, 0, i - 1)
    }
}

Build Heap이 \(O(n)\)인 이유

for 구문이 \(O(nlogn)\)인 이유

Quick Sort

• 특정 원소(pivot)를 기준으로 왼쪽은 lower, 오른쪽은 upper 원소들을 두는 방식
• Merge Sort와 마찬가지로 Divide and Conquer 알고리즘
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort): 비교하는 원소의 값이 같을 때 input 순서대로 정렬
• 평균적으로 \(O(nlogn)\)의 시간복잡도를 가지며, 매 Step마다 적어도 한 개의 원소는 반드시 자기 자리를 찾아가므로 매우 빠름
  • 하지만 최악의 경우에 \(O(n^2)\)의 시간복잡도를 가짐

  • 

동작

Step 1

Step 2

Step 3

Step 4

코드

public class Sort {
	
    public void quickSort(int[] arr, int first, int last) {
        if(first < last) {
            int pivot = partition(arr, first, last);
            quickSort(arr, first, pivot - 1);
            quickSort(arr, pivot + 1, last);
        }
    }
    
    public int partition(int[] arr, int first, int last) {
    	int pivot = arr[last];
        int i = first - 1;
        
        for(int j = first; j < last; j++) {
            if(arr[j] < pivot) {
            	swap(arr, ++i, j);
            }
        }
        swap(arr, i + 1, pivot);
        
        return i + 1;
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 최악의 경우에는 \(O(n^2\)일까?

• 최선의 경우: 매 Step마다 원소가 중앙에 위치되어서 반으로 나누어지는 경우

• 최악의 경우: 매 Step마다 원소가 끝에 위치되어서 1 : 9 로 나누어지는 경우 (이미 정렬된 배열)

그래서 pivot을 선택하는 여러 variation 기법이 존재한다. (Randomized Quick Sort 등..)

Merge Sort

• 원소 개수가 1개 또는 0개가 될 때까지 반으로 나눈뒤 반으로 나눈 원소들을 합쳐가는 과정에서 정렬하는 방식
• 정렬하려는 배열 크기만큼의 추가 배열이 필요함
• \(O(nlogn)\)으로 \(O(n^2)\)인 Selection, Insertion, Bubble Sort보다 훨씬 빠름
• Divide And Conquer 알고리즘

• 

동작

Merge가 동작하는 시점?을 하나의 Step으로 본다.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

코드

public class Sort {
	
    public void mergeSort(int[] arr, int first, int last) {
    	if(first < last) {
        	int mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }
    
    public void merge(int[] arr, int first, int mid, int last) {
    	int i = first;
        int j = mid + 1;
        int k = first;
        int[] copy = new int[arr.length];
        
        while(i <= mid && j <= last) {
        	if(arr[i] > arr[j]) {
            	copy[k++] = arr[j++];
            } else {
            	copy[k++] = arr[i++];
            }
        }
        
        if(i > mid) {
        	for(int l = j; j <= last; j++) {
            	copy[k++] = arr[l];
            }
        } else {
        	for(int l = i; i <= mid; i++) {
            	copy[k++] = arr[l];
            }
        }
        
        for(int l = first; l <= last; l++) {
        	arr[l] = copy[l];
        }
    }
    
}

왜 \(O(nlogn)\)일까?

Insertion Sort

• k번째 원소를 k-1번째 원소부터 첫번째 원소까지 비교하며 위치를 찾아 끼워넣는 방식
• O(n^2)인 정렬중에 빠른편에 속한다.

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void insertionSort(int[] arr) {
    	for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            for(int j = i - 1; j >= 0 && arr[j] > target; j--) {
            	arr[j+1] = arr[j];
            }
            arr[j+1] = target;
        }
    }
}

Bubble Sort

• 첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.
• Selection Sort와 마찬가지로 O(n^2)이다.

• 

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2 

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = arr[index1];
    }
    
    public void bubbleSort(int[] arr) {
    	for(int i = arr.length - 1; i >= 0; i--) {
        	for(int j = 0; j < i; j++) {
            	if(arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
}

Selection Sort

• 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
• k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.

• 

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
	
	public void selectionSort(int[] arr) {
    	for(int i = arr.length-1; i >= 0; i--) {
        	int maxIndex = i;
            int j;
            for(j = 0; j < i; j++) {
            	if(arr[j] > arr[maxIndex]) {
                	maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }
    
    
}