160112P(화)

자료구조 Chapter 8 - 개선된 정렬

 

퀵 정렬(Quick Sort)

정렬 알고리즘으로 가장 우수한 평균 수행속도를 가진다.

분할 알고리즘(partition algorithm)을 기본 개념으로 하고 있다.

 

시간 복잡도 : O(N * logN)

최악의 경우 : O(N^2)

 

분할 알고리즘(partition algorithm)

피봇(pivot)을 기준으로 한쪽은 그것보다 작은 값들의 자료들로만, 또 다른 한쪽은 그것보다 큰 값의 자료들로 분류

배열의 양 끝 방향에서부터 시작해서 각각 피봇보다 큰값과 작은값을 발견하면 그 값들을 서로 치환

 

시간 복잡도 : O(N)

 

퀵 정렬 과정

분할 알고리즘을 사용하여 정렬하고자 하는 배열을 2개의 하위 배열로 분할하고 하위배열에서는 다시 재귀적으로 자신의 배열을 분할하는 과정을 반복한다.

퀵 정렬은 멀리 떨어진 자료를 직접적으로 치환함으로써 이웃한 자료를 서로 비교하여 치환하는 다른 정렬보다 수행속도를 개선시켰다. 이웃한 자료를 비교하고 치환하면 자료가 정렬될 위치에서 멀면 멀수록 정렬의 수행속도가 떨어진다.

 

1. 배열을 2개의 하위배열, 즉 왼쪽 하위배열은 피봇값보다 작은값으로 이루어진 배열, 오른쪽 하위배열은 피봇값보다 큰값으로 이루허진 배열로 분할한다.

 

2. 왼쪽 하위배열에 퀵정렬을 다시 실행시킨다.

 

3. 오른쪽 하위 배열에 퀵 정렬을 다시 실행시킨다.

 

중간값(median of three)

퀵정렬에서는 피봇 값을 선정하는 작업이 아주 중요하다.

분할될 때 한쪽배열의 크기가 1씩 진행된다면 퀵정렬의 성능을 제대로 낼수 없다.

주어진 배열을 매번 반으로 분할하고 하위배열도 반으로 분리된다면 최적의 성능

 

배열의 첫번 째 왼쪽 값, 중간 값, 마지막 오른쪽 값을 정렬해서 중간값을 피봇으로 사용하는 방법

 

QuickSort.java

public static void quickSort(int[] a, int leftmost, int rightmost) {

if(rightmost - leftmost <= 0) {

return;

}

else {

int pivot = a[rightmost];

 

int i = leftmost -1;

int j = rightmost;

 

while(true) {

while(a[++i] < pivot)

;

 

while(j > leftmost && a[--j] > pivot)

;

 

if(i >= j) {

break;

}

else

swap(a, i, j);

}

swap(a, i, rightmost);

 

// 좀 이상하다

quickSort(a, leftmost, i - 1);

 

// 좀 이상하다2

quickSort(a, leftmost + 1, rightmost);

}

}

 

static void swap(int[] a, int i, int j) {

int temp;

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

 

static void displayArray(int[] arr) {

for(int i = 0; i < arr.length; i++) {

System.out.print(arr[i] + " ");

}

}

 

내가 생각했을 때 위의 코드는 pivot을 매번 배열의 오른쪽으로 잡아버린다.

중간으로 잡는것이 더 나은 알고리즘 이라고 생각한다.

(그리고 위의 코드는 뭔가 이상하다 ㄷㄷㄷ)

 

public static void quickSort(int[] a, int leftmost, int rightmost) {

if(rightmost - leftmost <= 0) {

return;

}

else {

int pivot = Math.floor((leftmost + rightmost) / 2);

 

int i = leftmost -1;

int j = rightmost;

 

while(true) {

while(i < rightmost && a[++i] < pivot)

;

 

while(j > leftmost && a[--j] > pivot)

;

 

if(i >= j) {

break;

}

else

swap(a, i, j);

}

swap(a, i, pivot);

 

quickSort(a, leftmost, pivot - 1);

 

quickSort(a, pivot + 1, rightmost);

}

}

 

병합정렬(Merge Sort)

여러개의 정렬된 자료의 집합을 결합하여 한 개의 정렬된 집합으로 만드는 정렬 방법

부분집합으로 분할하고 각 부분집합에 대해서 정렬 작업을 완성한 후에 정렬된 부분집합들을 다시 결함하는 Divide and Conquer기법을 사용한다.

 

시간 복잡도 : O(N * logN)

 

2-way 병합

2개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법

 

n-way 병합

n개의 정렬된 자료 집합을 결합하여 하나의 집합으로 만드는 병합 방법

 

1. 분할(Divide)

자료들을 같은 크기의 부분집합 2개로 분할한다.

 

2. 정복(Conquer)

부분집합에 있는 원소들을 정렬한다.

부분집합의 크기가 충분히 작지 않으면 재귀를 이용하여 다시 분할한다.

 

3. 결합(Combine)

정렬된 부분집합들을 하나의 집합으로 결합한다.

 

mergeSort.java

static void merge(int a[], int m, int middle, int n) {

int i, j, k, t;

 

// 첫 번째 부분집합의 시작 위치

i = m;

 

// 두 번째 부분집합의 시작 위치

j = middle + 1;

 

// 배열 sorted에 정렬된 원소를 저장할 위치 설정

k = m;

 

while(i <= middle && j <= n) {

if(a[i] <= a[j]) {

sorted[k] = a[i];

i++;

}

else {

sorted[k] = a[j];

j++;

}

k++;

}

 

if(i > middle) {

for(t = j; t <= n; t++, k++) {

sorted[k] = a[t];

}

}

else {

for(t = i; t <= middle; t++, k++) {

sorted[k] = a[t];

}

}

 

for(t = m; t <=n; t++) {

a[t] = sorted[t];

}

printf("\n 병합 정렬 >> ");

 

for(t = 0; t < size; t++) {

printf("%4d ", a[t]);

}

}

 

static void mergeSort(int a[], int m, int n) {

int middle;

 

if(m < n) {

middle = (m + n) / 2;

 

mergeSort(a, m, middle);

mergeSort(a, middle + 1, n);

 

merge(a, m, middle, n);

}

}