[자료구조] 효율적인 데이터 정렬을 위한 비교 정렬 알고리즘 분석

 

정렬 알고리즘이란 n개의 숫자가 주어졌을 때, 이를 사용자가 지정한 기준에 따라 정렬하는 알고리즘을 뜻한다.

 

지금부터 어떤 알고리즘이 있는지 살펴보도록 하자.

 

 

---

 

비교 정렬(comparison sort)

 

비교 정렬은 배열의 원소 쌍 간의 비교를 기반으로 정렬하는 알고리즘이다.

 

가장 쉽게 생각할 수 있는 알고리즘이자 O(nlogn)이라는 시간 한계를 넘어서지 못한다.

 

이러한 비교 정렬의 종류로써 선택 정렬(Selection Sort), 삽입 정렬(Insertion Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort), 퀵 정렬(Quick Sort)이 있다.

 

 

 

 

 

 

 

 

선택 정렬

 

제일 먼저 선택 정렬이란?

 

배열에서 아직 정렬되지 않은 부분에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘을 의미한다.

 

 

선택 정렬 알고리즘

 

 

그림과 같이 인덱스(i)를 하나씩 증가시키며 탐색을 한다.

 

노란색 범위에서 최솟값을 찾고 그 값을 정렬된 부분의 제일 오른쪽에 둔다.

 

 

다음은 삽입 정렬에 관한 코드 예시이다.

 

import java.lang.Comparable;

public class Selection {
	public static void sort(Comparable[] a) {
    
    	// 정렬할 배열의 길이
    	int N = a.length;
        
        for(int i=0; i<N; i++) {
        	// 최솟값을 찾기 시작
        	int min = i;
            // 그림에서 노란색 부분에 해당
            // 최솟값을 찾음 -> isLess 메서드 사용
            for(int j=i+1, j<N; j++) {
            	if( isLess(a[j], a[min])) min = j;
            }
            
            // 최솟값과 정렬된 부분의 맨 오른쪽 부분을 바꿈
        	swap(a, i, min);	
        }
    }
    // 두 원소 중 누가 더 작은 지 비교하는 메서드
    private static boolean isless(Comparable i, Compariable j) {
    	return (i.compareTo(j) < 0);
    }
    
    // 배열의 원소를 서로 교환시키는 메서드
    private static void swap(Comparable[] a, int i, int j) {
    	Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

 

 

 

 

 

 

선택 정렬의 수행 시간

 

선택 정렬의 수행 시간은 항상 O(n^2)의 수행 시간이 소요된다.

 

또한 입력에 민감하지 않다는 특징이 있다.(Input Insensitive)

 

민감하지 않다는 것은 비교횟수가 항상 균일하게 보장되기 때문이다.

 

이에 대해 생각해보면 루프가 1번 수행될 때마다 정렬 안 된 부분에서 최솟값을 찾을 것이다.

 

이때, n개의 원소중에서 min을 찾기 위해 n-1번 비교하고,

인덱스를 한 칸 이동 시킨 후, n-1개의 원소 중 min을 찾기 위해 n-2번 비교할 것이다.

결국, 정렬시키기 위해서 (n-1) + (n-2) + (n-3) +... + 1번만큼 비교하게 된다.

 

그렇기에 입력에 있어 민감하지 않고 수행 시간이 항상 O(n^2)만큼 소요된다.

 

 

 

 

---

 

 

 

삽입 정렬(Insertion Sort)

 

삽입 정렬이란?

 

배열이 정렬된 부분과 정렬 안 된 부분으로 나뉘며, 정렬 안 된 부분의 가장 왼쪽 원소를 정렬된 부분에 삽입하며 정렬한다.

 

이전의 선택 정렬과의 공통점은 정렬된 부분과 정렬 안된 부분이 있다는 것이다.

 

다만, 정렬된 부분의 제일 오른쪽에 최솟값을 추가했던 선택 정렬과는 달리,

 

삽입 정렬은 정렬된 부분안에 들어갈 위치를 찾아 넣는다.

 

 

삽입 정렬 알고리즘

 

 

그렇기 때문에 원소를 삽입한 이후,

 

정렬된 부분의 원소 수는 1 증가하고 정렬되지 않은 부분의 원소 수는 1 감소한다는 특징이 있다.

 

 

다음은 삽입 정렬에 관련한 코드 예시이다.

 

import java.lang.Comaparable;

public class Insertion {
	public static void sort(Comparable[] a) {
    
    	// 배열 크기 지정
    	int N = a.length;
        for (int i=1; i<N; i++) {
        	// i는 현재 원소의 인덱스이다.
        	for(int j=i; j>0; j--) {
            // 현재 원소를 정렬된 앞 부분에 삽입한다.
            // 즉, i부터 0까지의 인덱스를 탐색하며 적절한 위치에 넣는다.
            	if (isLess(a[j], a[j-1]) {
                	swap(a, j, j-1);
                } else break;
            }
        }
    }
}

 

 

 

 

 

 

삽입 정렬의 수행 시간

 

삽입 정렬의 시간 복잡도는 최선의 경우 O(n), 최악의 경우 O(n^2)이다.

 

최선의 경우는 입력이 이미 정렬된 경우 n-1번만 비교하면 되므로 O(n)이다.

 

만약 입력이 역으로 정렬되었다면, 선택 정렬과 같이 전부 비교해야 하기에 O(n^2)이 되며,

데이터를 교환하는 수도 O(n^2)이 된다.

 

그리고, 평균적인 경우는 O(n^2)을 나타내는데,

왜 최악의 경우와 같은 시간 복잡도를 가지는가하면...

 

원소가 정렬된 부분에 최종적으로 삽입되는 부분이 평균적으로 정렬된 부분의 중간 지점이라고 생각하기 때문이다.

 

그렇기에 기존의 최악의 경우에서 그냥 1/2을 곱한 결과 밖에 안되고,

시간 복잡도는 상수를 곱해봤자 똑같으므로 O(n^2)를 나타내는 것이다.

 

 

 

 

 

삽입 정렬의 응용

 

그렇다면 실질적으로 삽입 정렬은 어떤 경우에 사용하는 게 효율적인가?

 

이미 정렬된 파일의 뒷부분에 소량의 신규 데이터를 추가하여 정렬하는 경우(입력이 거의 정렬됨)

우수한 성능을 보인다.

 

또한 입력 크기가 작은 경우에도 좋은 성능을 보인다.

순환 호출을 하지 않고 프로그램이 간단하기 때문이다.

 

삽입 정렬은 합병정렬이나 퀵 정렬과 함께 사용되어 실질적으로 성능이 향상된다.

(단, 이론적인 수행시간은 향상되지 않는다.)

 

 

 

 

 

---

 

 

 

힙 정렬(Heap Sort)

 

힙 정렬은 힙 자료구조를 이용하는 정렬이다.

 

힙 자료구조에 관해 생각나지 않는다면 다음 포스팅을 참고하길 바란다.

 

[자료구조] 우선순위 큐(Priority Queue), 그리고 힙(Heap)

 

 

 

힙 정렬은 다음과 같은 순서로 정렬을 수행한다.

 

1. 배열에 저장된 데이터의 키를 우선순위로 하는 최대 힙(Max Heap)을 구성한다.

 

2. 루트의 숫자를 힙의 가장 마지막 노드에 있는 숫자와 교환한다.

 

3. 힙 크기를 1 감소시킨다.

이는 마지막으로 이동한 원소를 다음 정렬 시에 배제하기 위함이다.

 

4. 루트로 이동한 숫자로 인해 위배된 힙속성을 downheap 연산으로 복원한다.

 

5. 이 과정을 반복하여 정렬한다.

 

 

 

 

다음은 Heap 정렬과 관련된 코드 예시이다.

 

import java.lang.Comparable;

public class Heap {
	pulbic static void sort(Comparable[] a) {
    	// 힙 사이즈 설정(a[0]은 편의를 위해 사용안함)
    	int heapSize = a.length-1;
        
        
        // 힙 만들기(상향식 힙)
        for(int i= heapSize/2; i>0; i--) {
        	downheap(a, i, heapSize);
        }
        
        // 힙 정렬 수행
        while(heapSize > 1) {
        	// a[1]과 힙의 마지막 항목과 교환
        	swap(a, 1, heapSize--);
            
            // 위배된 힙의 속성을 고친다.
            downheap(a, 1, heapSize);
        }
    }
    
    private static void downheap(Comparable[] a, int p, int heapSize) {
    	while(2*p <= heapSize) {
        	// s는 왼쪽 자식 인덱스이다.
        	int s = 2*p;
            
            // 오른쪽 자식이 더 큰 경우
            if (s < heapSize && isLess(a[s], a[s+1])) s++;
            
            // 부모가 자식 승자보다 크다면 힙 속성 만족
            if (!isLess(a[p], a[s])) break;
            // 힙 속성을 만족하지 않는다면 부모와 자식 승자 교환
            swap(a, p, s);
            
            // 이제 자식 승자의 자리에 부모가 있게 함
            p = s;
        }
    }
}

 

 

상향식 힙을 만드는 과정이나 downheap에 관해서 헷갈린다면, 꼭 이전 포스팅을 참고하길 바란다.

 

 

 

 

 

 

 

힙 정렬의 수행 시간

 

총 수행 시간은 O(nlogn)이다.

 

그 이유는 먼저 상향식(Bottom-up) 방식으로 힙을 구성하는 경우 O(n) 시간이 소요되고,

 

루트와 힙의 마지막 노드를 교환한 후, downheap을 수행하는 데 있어 O(logn) 시간이 소요된다.

 

그리고 루트와 힙의 마지막 노드를 교환하는 횟수는 n-1번이 되므로

 

O(logn) * (n-1)을 수행해 주어야 한다.

 

결국 총 수행 시간은 O(n) + (n-1) * O(logn) = O(nlogn)이 소요된다.

 

힙 정렬은 어떠한 입력에도 항상 O(nlogn) 시간이 소요된다는 특징이 있다.

 

 

 

 

---

 

합병 정렬(Merge Sort)

 

합병 정렬이란?

 

크기가 n인 입력을 n/2 크기로 분할하고, 각각에 대해 순환으로 합병 정렬을 수행한 후, 2개의 각각 정렬된 부분을 합병하는 정렬 알고리즘을 뜻한다.

 

🤔 이때 합병(Merge)이란?

 

2개의 각각 정렬된 리스트를 1개의 정렬된 리스트로 만드는 것이다.

 

합병 정렬은 분할 정복(Divide-and-Conquer) 알고리즘을 활용한 알고리즘인데,

 

분할 정복이란 입력을 분할하여 분할된 입력 각각에 대해 문제를 순환으로 해결한 후, 취합하여 문제를 해결하는 알고리즘이다.

 

출처 : 교수님 자료

 

출처 : 교수님 자료

 

합병 정렬을 코드로 살펴보자.

 

import java.lang.Comarable;
public class Merge {
	private static void merge(Comaprable[] a, Comaparable[] b, int low, int mid, int high) {
    	int i = low, j = mid + 1;
        
        // low~mid, mid+1~high 두 배열을 임시 배열 b에 합병한다.
        for (int k = low, k<=high; k++) {
        
        	// 앞 부분이 먼저 소진된 경우이다.(i의 초깃값 = low)
            // 이 경우, j값을 넣는다.
        	if (i > mid) b[k] = a[j++];
            
            // 뒷 부분이 먼저 소진된 경우이다.(j의 초깃값 = mid+1)
            else if (j > high) b[k] = a[i++];
            
            // 두 i와 j의 값을 비교하며 값을 넣는다.(이때 실질적으로 정렬)
            else if (isLess(a[j], a[i])) b[k] = a[j++];
            else b[k] = a[i++];
            
        }
        // 임시 배열 b의 값을 a의 값으로 옮긴다.
        for (int k = low; k<=high; k++) a[k] = b[k];
    }
    
    public static void sort(Comparable[] a, Comaparable[] b, int low, int high) {
    	if (high <= low) return;
        
        // low와 high의 중간 값인 mid 값을 설정한다.
        int mid = low + (high - low) / 2;
        
        // 나누어진 mid 값을 기준으로 sort를 수행한다.
        sort(a, b, low, mid);
        sort(a, b, mid + 1, high);
        merge(a, b, low ,mid, high);
    }
    
    public staic void sort(Comparable[] a) {
    	// 전체 배열 범위를 기준으로 정렬을 수행한다.
    	Comaparable[] b = new Comparable[a.length];
        sort(a, b, 0, a.length-1);
    }
    
    private static boolean isless(Comparable v, Comparable w) {
    	return (v.compareTo(w) < 0);
    }
}

 

헷갈리니까, 코드의 흐름을 같이 살펴보자.

 

두 번째로 나오는 sort 메서드가 먼저 호출되면 정렬은 실행된다.

 

이는 배열 a 전체를 정렬하는 메서드로, 보조 배열 b를 생성하고,

첫 번째 sort 메서드를 호출하여 배열의 전체 범위를 정렬한다.

 

첫 번째로 나오는 sort 메서드는 배열 a의 특정 부분을 정렬하는 메서드이다.

low와 high 인덱스를 이용하여 배열을 분리하고, 재귀적으로 부분 배열로 정렬한 후, merge메서드를 호출하여 합병한다.

 

merge메서드는 배열 a의 일부분을 합병하는 메서드이다.

low부터 mid까지 첫 번째 부분 배열과 mid+1부터 high까지의 두 번째 부분 배열을 합병하여 보조배열 b에 저장한다.

 

즉, 분할하고(low~mid, mid+1~high) 분할한 값을 정렬하며 합병하는(merge) 과정인 것이다.

 

 

 

---

추가로 합병 정렬은 안정한 정렬이라는 특징을 가지고 있다.

 

안정한 정렬(Stable Sort) 알고리즘은 중복된 키에 대해 입력에서 앞서 있던 키가 정렬 후에도 앞서 있는 알고리즘이다.

 

불안정하다면 그 순서가 뒤바뀐다.

 

 

 

 

---

 

 

 

 

퀵 정렬(Quick Sort)

 

퀵 정렬이란?

 

입력의 맨 왼쪽 원소(피벗, Pivot)를 기준으로 피벗보다 작은 원소들과 큰 원소들을 각각 피벗의 좌우로 분할한 후, 좌우 부분을 각각 순환으로 정렬한다.

 

 

퀵 정렬의 과정은 다음 그림을 보면 쉽게 이해할 수 있다.

 

출처 : 교수님 자료

 

 

즉, 위와 같이 피벗을 설정하고 그 피벗보다 작거나 큰 부분으로 나눈 후, 맨 마지막으로 비교할 원소자리에 피벗이 이동하는 형태인 것이다.

 

이러한 과정을 각각의 작은 원소, 큰 원소 집합에서 반복 수행하는 것이 퀵 정렬의 핵심이다.

 

 

 

퀵정렬의 코드를 살펴보자.

 

import java.lang.Comparable;
public class Quick {
	public static void sort(Comparable[] a) {
    	// 전체 범위 정렬 수행
    	sort(a, 0, a.length - 1);
    }
    
    private static void sort(Comparable[] a, int low, int high) {
    
		// 종료 조건
    	if(high <= low) return;
        
        // 
        int j = partition(a, low, high);
        sort(a, low, j-1);
        sort(a, j+1, high);
    }
    
    private static int partition(Comparable[] a, int pivot, int high) {
    	// 피벗 인덱스
    	int i = pivot;
        
        // 맨 마지막 값 인덱스 설정
        int j = high+1;
        
        // 피벗 값 접근
        Comparable p = a[pivot];
        while(true) {
        	// 피벗 값과 피벗 다음 값으로부터 하나씩 비교해 나감
            // 즉, 양쪽 끝에서 부터 비교해나감
            
            // 피벗 값보다 큰지 작은지 비교
           	// 이 과정을 통해 i와 j는 각각 피벗보다 작은 값, 큰 값이 됨.
            // 만일 각 인덱스 값이 끝에 도달한 경우 종료
        	while(isLess(a[++i], p)) if (i == high) break;
            while(isLess(p, a[--j])) if (j == pivot) break;
            
            // 비교지점이 교차하거나 같아지는 순간 종료
            if( i >= j ) break;
            
            // i와 j 인덱스 값 교환(큰 값, 작은 값 교환)
            swap(a, i, j);
        }
        
        // 마지막 피벗 값과 교환
        swap(a, pivot, j);
        return j;
    }
}

 

 

---

 

퀵 정렬의 수행시간

 

평균, 최선의 경우는 피벗이 매번 입력을 1/2씩 분할하는 경우이며 O(nlogn)이다.

 

최악의 경우는 피벗이 매번 가장 작거나 가장 큰 경우로 피벗보다 작은 부분이나 큰 부분이 없는 경우이다. : O(n^2)

 

퀵 정렬은 평균적으로 빠른 수행 시간을 가지며, 보조 메모리를 사용하지 않는다.

 

최악의 경우 수행 시간이 O(n^2)이므로 성능 향상 방법들을 통해 이를 보완할 수 있다.

 

 

 

---

 

 

퀵 정렬의 성능 향상 방법

 

퀵 정렬은 순환 호출을 사용하므로 입력이 작은 크기가 되었을 때, 삽입 정렬을 호출하여 성능을 향상할 수 있다.

 

또한 피벗의 값에 따라 분할되는 두 영역의 크기가 결정되므로 한쪽이 너무 커지는 것을 방지하기 위해

 

Median-of-Three 방법을 사용할 수 있다. 이는 가장 왼쪽(low), 중간(mid), 가장 오른쪽(high) 원소 중에서 중간 값을 피벗으로 사용하는 방법이다.

 

가령 9개의 원소를 선택하여 이들을 3개씩 하나의 그룹으로 여겨, 각 그룹에서 중간 값을 선택하고, 선택된 3개의 중간 값 중에 중간값을 피벗으로 사용하는 방식이다.