개발 공부 - [정렬] 기본적인 정렬 알고리즘 (Section 3)

201012: 정렬

1) 정렬 알고리즘 :

- Simple, slow (기본적이나 속도 느림)

Bubble sort

Insertion sort

Selection sort

-Fast (상대적으로 빠름)

Quick sort

Merge sort

Heap sort

- O(N)

Radix sort 

(1) Selection sort

전체 중 제일 큰 값을 찾아서 맨 뒤 것과 자리를 바꾼 뒤 

전체-1 중 제일 큰 값을 찾아서 맨 뒤-1 것과 자리를 바꾼 뒤

... (반복) = 데이터를 오름차순으로 정렬

수도 코드 :

selectionSort(A[], n) { // 배열 A[1...n]을 정렬한다.

    for last <- n downto 2 {                                 ... 1)

        A[1...last] 중 가장 큰 수 A[k]를 찾는다;           ... 2)

        A[k] <-> A[last]; // A[k]와 A[last]의 값을 교환  ... 3)

    }

}

실행 시간:

1) 의 for 루프는 n-1번 반복

2) 에서 가장 큰 수를 찾기 위한 비교 횟수 : n-1, n-2, ... , 2, 1

3) 의 교환은 상수시간 작업

시간복잡도 T(n) = (n-1)+(n-2)+...+2+1 = O(n^2)

(2) Bubble sort

Selection Sort와 유사하나 맨앞 2개씩부터 옮겨가는 구조임

0-1 비교 후 큰 것 1으로 변경

1-2 비교 후 큰 것 2로 변경

이런 식으로 전체 교환

수도 코드 : 

bubblesort(A[], n){    //배열 A[1...n]을 정렬한다.

    for last <- n downto 2 {            ... 1) 

        for i <- 1 to last - 1            ... 2)

        if (A[i] > A[i+1]) then A[i] <-> A[i+1]; // 교환 ... 3)

    }

}

수행 시간 :

1) 의 for 루프는 n-1 반복

2) 의 for 루프는 각각 n-1, n-2, ... , 2, 1번 반복

3) 의 교환은 상수시간 작업 

실행 시간 :

T(n) = (n-1)+(n-2) + ... 2+ 1 = O(n^2) = n(n-1)/2

최악 = 최선 = 평균이 균일하다.

(3) Insertion Sort 

삽입 정렬 알고리즘은 

정렬할 데이터가 6개라면 

1 - 자체로 정렬되어져 있다 

1 & 2 - 두개의 데이터를 정렬된 상태로 만든다. 

1 & 2 & 3 - 세개의 데이터를 정렬된 상태로 만든다.

이런 식으로 데이터를 끼워넣어서 정렬된 상태로 만든다.

어쨌든 이미 정렬된 상태라고 가정하고 앞or뒤로부터 compare 후 shift하여 동작시킨다.

비교할 값은 임시 변수로 지정하여 비교하는 양식을 취한다.

수도 코드

insertionSort(A[], n){ //배열 A[1...n]을 정렬한다.

    for i <- 2 to n{                    ... 1)

        A[1...i]의 적당한 자리에 A[i]를 삽입한다 ... 2)

    }

}

수행 시간:

1) 의 for 루프는 n-1번 반복

2) 의 삽입은 최악의 경우 i-1번 비교

최악의 경우 : T(n) = (n-1) + (n-1) + ... + 2 + 1 = O(n^2)