[자료구조] Sorting(정렬) - Insertion, Quick Sort

 

Stable Sorting vs Unstable Sorting

 

Stable Sorting은 같은 두 수를 정렬할 때 그 수의 순서가 바뀌지 않고 유지되며 정렬되는 것이다.

반대로 Unstable Sorting은 같은 두 수를 정렬할 때 그 수의 순서가 서로 바뀌면서 정렬되는 것이다.

 

 

 

Insertion Sort

 

삽입 정렬은 정렬된 배열에 한 숫자씩 삽입해 정렬하는 것이다.

정렬된 배열의 뒷부분부터 비교하며, 삽입하려는 수보다 큰 경우에만 인덱스를 줄여 비교한다.

따라서 같은 수인 경우에는 다음 인덱스에 정렬되기 때문에 Stable Sorting이다. 

 

void insert(element e, element a[], int i) {
	a[0] = e;
    	while(e.key < a[i].key) {
    		a[i+1] = a[i];
        	i--;
    	}
    	a[i+1]=3;
}

void insertionSort(element a[] ,int n) {
	int j;
	for (j = 2; j <= n; j++) {
        element temp = a[i];
		insert(temp, a, j-1);
	}
}

 

 

Quick Sort

 

퀵 정렬은 pivot보다 큰 것을 오른쪽, pivot보다 작은 것을 왼쪽에 두어 수를 정렬하는 방법이다.

 

만약 right 와 left 인덱스가 교차하는 경우에는 left와 right 값을 서로 바꾼다.

배열의 첫 인덱스부터 left 인덱스까지, left + 1 인덱스부터 배열의 마지막까지 두 개로 나뉘어 다시 정렬이 반복되어 종료되면 전체 배열이 정렬된 모습을 확인할 수 있다.

 

 

 

아래의 그림과 코드를 보면 Quick sort를 이해할 수 있다.

void quickSort(element a[], int left, int right) {
	int pivot, i, j;
    	element temp;
        if (elft < right) {
        i = left; j = right + 1;
        pivot = a[left].key;
        do {
        	do i++; while(a[i].key < pivot);
        	do j--; while(a[j].key > pivot);
        	if (i<j) SWAP(a[i], a[j], temp);
        } while (i<j);
        SWAP(a[left], a[j], temp);
        quickSort(a, left, j-1);
        quickSort(a, j+1, right);
        }
}

 

퀵 정렬은 배열 내의 데이터가 불균형으로 정렬된 경우 최악의 경우이므로 시간복잡도는 O(n^2)이다.

평균적으로는 O(nlogn)이며 교체가 발생하기 때문에 Unstable Sorting이다.