160110P(일)

자료구조 Chapter 7 - 기본정렬

 

자료를 데이터베이스화 하면 할수록 정렬(sorting)은 복잡해진다.

정렬은 복잡한 자료를 특정한 항목에 따라 순서대로 나열함으로써 원하는 자료의 처리를 용이하게 해준다.

 

컴퓨터 기억 공간내의 순서없이 나열된 자료들 중에서 특정 항목을 기준으로 그 기준값에 따라 "자료를 재배치"하는것을 말한다.

오름차순(ascending)과 내림차순(descending)이 있다.

 

기본정렬

1. 버블 정렬(Bubble sort)

가장 기본적인 정렬방법

서로 인접한 자료들을 서로 자리바꿈하면서 뒤에서부터 정렬되는 방법

개념적으로 가장 간단하며 정렬기술의 기초

 

1. 두 개의 항목을 비교한다.

2. 오른쪽 항목이 적으면 자리바꿈을 한다.

3. 오른쪽으로 한자리 이동한다.

4. 가장 오른쪽에 한 항목을 비교할 때까지 1~3단계를 반복한다.

 

간단하며 비효율적이고 정렬할 대상이 적을때 사용하는것이 바람직하다.

첫번째 정렬이 끝나면 맨 마지막 항목은 정렬이 완료된 상태이다.

 

비교횟수 = N * (N - 1) / 2

시간복잡도 = O(n^2)

 

BubbleSort.java

static int[] bubbleSort(int[] arr) {

for(int i = arr.length - 1; i > 0; i--) {

 

// 한번 정렬이 끝날때마다 맨 마지막 항목은 정렬이 완료되므로 j < i

for(int j = 0; j < i; j++) {

if(arr[j] > arr[j + 1]) {

swap(arr, j, j + 1);

}

}

 

displayArray(arr);

System.out.println();

}

return arr;

}

 

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

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

 

static void displayArray(int[] arr) {

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

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

}

}

 

2. 선택 정렬(Selection Sort)

버블 정렬의 자리바꿈 횟수를 줄임으로써 성능을 개선한 알고리즘

그러나 선택정렬의 비교횟수는 버블정렬과 같다.

 

정렬할 항을 선택하고 가장 작은 항목을 기준 항과 자리바꿈한다.

앞부분부터 정렬이 하나씩 완료된다.

 

자리바꿈 횟수는 버블정렬보다 적으나, N의 수가 아주 크다고 가정하면 O(n^2)이다.

버블정렬은 큰 자료부터 정렬되지만, 선택정렬은 작은수부터 정렬된다.

 

자리바꿈 횟수는 버블정렬보다 적지만, 항목 비교 횟수는 여전히 많다.

정렬할 대상이 적고, 항목들에 대한 자리바꿈 시간이 비교횟수에 걸리는 시간보다 상대적으로 클 때 사용하는것이 유용하다.

 

비교횟수 = N * (N - 1) / 2

시간복잡도 = O(n^2)

 

SelectionSort.java

static int[] selectionSort(int[] arr) {

int min;

 

// 선택은 처음부터 마지막항 - 1까지 선택해서 정렬하게 된다.

// min이 선택된 항을 뜻한다.

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

min = i;

 

// 선택된 항의 다음 부분부터 가장 작은 항을 찾으므로 j = i + 1;

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

if(arr[j] < arr[min]) {

min = j;

}

}

swap(arr, i, min);

 

displayArray(arr);

System.out.println();

}

return arr;

}

 

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

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

 

static void displayArray(int[] arr) {

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

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

}

}

 

3. 삽입 정렬

이미 정렬된 부분 배열에 새로운 항목을 삽입하여 정렬을 수행하는 방법이다.

 

1. 정렬할 막대를 임시기억장치에 저장한다.

2. 자리가 비어있으므로 오른쪽으로 한칸씩 이동한다.

3. 정렬할 막대보다 적은 값을 만나면 그 오른쪽에 삽입한다.

 

평균 비교횟수는 N * (N - 1) / 4 이고, 항목끼리 비교한 뒤 자리바꿈의 변화가 없기때문에 다음 차례로 진행되는 복사횟수도

 비교횟수와 동일하다. 그러나 복사횟수는 자리이동과 같이 시간적인 소비에 큰영향이 없다.

∴ 삽입정렬은 버블정렬에 비해서 2배의 속도가 빠르며, 선택정렬에 비해 다소 빠른 효율을 보인다.

 

앞에서부터 인접한 항목과 비교하기 때문에 오름차순에서 큰 값이 앞쪽에 속해있는 배열에서는 효율이 떨어진다.

정렬할 대상이 적거나, 이미 부분적으로 정렬되어져 있으면 기본정렬중 가장 효율적이다.

퀵정렬에서 삽입정렬이 사용된다.

 

비교횟수 = N * (N - 1) / 2

시간복잡도 = O(n^2)

 

InsertionSort.java

static int[] insertionSort(int[] arr) {

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

int tmp = arr[i];

int j = i;

 

while(j > 0 && arr[j - 1] >= tmp) {

arr[j] = arr[j - 1];

 

--j;

}

arr[j] = tmp;

 

displayArray(arr);

System.out.println();

}

return arr;

}

 

static void displayArray(int[] arr) {

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

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

}

}

 

안정성(Stability)

숫자 뿐만 아니라 문자나 문자열도 항목이 될 수 있다.

1차 기준에 따라서 정렬된 후에 2차정렬에서도 상대적인 순서가 그대로 유지되면 그 정렬 알고리즘은 안정성이 있다고 한다.

 

ex)

1차 : 이름순으로 정렬

2차 : 1차의 결과에대해 출생년도를 기준으로 정렬