알고리즘 - 정렬 정리

1. Selection Sort (선택 정렬)

<기본 원리> : n 개의 키 중에서 가장 작은 것을 찾아서 그 키와 첫째 키인 A[0]와 자리바꿈을 하고, 남은 키들을 앞과 같은 방식으로 처리.

그림 1. Selection Sort

void SelectionSort(int A[], int n) {
	...
}

<시간 복잡도>

(n+1) + (n+2) + ... + 1 = n(n+1)/2

평균시간복잡도 : O(n^2)

최악시간복잡도 : O(n^2)

 

<제자리성>

- 제자리 정렬

   -> i, j(for 문), ArraySize 등 상수 크기 메모리

 

<안정성>

- 불안정한 정렬

   -> ex)  B b a c > a b B c

 

2. Bubble Sort (버블 정렬)

<기본 원리> : 첫번째 키와 두번째 키 비교&스왑 -> 두번째 키와 세번째 키 비교&스왑 -> ... -> n-1번째 키와 n번째 키 비교&스왑 (이렇게 되면 마지막에 가장 큰 키가 위치하게 됨!)

                          이 방법을 그 다음엔 첫번째 키부터 n-1번째 키까지 비교&스왑 (더 이상 없을때 까지 반복!)

like Bubble!! 몽글몽글 인접한 키들끼리 바꾼당

그림 2. Bubble Sort 1회차 설명

// 1회차
void BubbleSort(int A[], int n) {
	for(int i ; i < n ;  i++){
    	if(A[i - 1] > A[i])
        	Swap(&A[i-1], &A[i]);
    }
}

// Sort했는지 확인하여 시간 단축
void BubbleSort(int A[ ], int n) { 
    int i, Sorted; 
    Sorted ＝ FALSE; 
    while (!Sorted) { 
        Sorted ＝ TRUE; 
        for (i ＝ 1; i ＜ n; i＋＋) 
           if (A[i－1] ＞ A[i]){ 
        Swap(&A[i－1], &A[i]); 
            Sorted ＝ FALSE;} 
      } 
} 

<시간 복잡도>

(n-1)+(n-2)+ … + 1 = n(n-1)/2

최악시간복잡도 : O(n^2)

 

<제자리성>

- 제자리 정렬

   -> i, Sorted 등 상수 크기 메모리

 

<안정성>

- 안정된 정렬

   -> Because, 인접한 레코들끼리만 자리바꿈!

 

 

3. Insertion Sort (삽입 정렬)

<기본 원리> : 1 ~ 2번째 키까지 정렬, 1 ~ 3번째 키까지 정렬. 여기서 이제 정렬할 때는 3번째 키가 어디로 갈지 찾아간다!! -> 그렇게 1 ~ n번째 키까지 정렬하면 끝!

i번째 키가 어디로 갈지 찾아가서 Insertion(삽입)!

그림 3. Insertion Sort

// 키가 1부터 저장될 때, A[0]은 더미데이터
void InsertionSort(int A[], n) {
    int Value, i, j;
    for (i = 2; i < n; i++)
    {
        Value = A[i];
        j = i;
        while (A[j -1] > Value)
        {
            A[j-1];
            j--;
        }
        A[j] = Value;
    }
}

 

<시간 복잡도>

평균시간복잡도 : O(n^2)

(n-1)+(n-2)+ … + 1 = n(n-1)/22+3+…+n = n(n+1)/2-1

최악시간복잡도 : O(n^2)

 

<제자리성>

- 제자리 정렬

   -> i, j, Value 등 상수 크기 메모리

 

<안정성>

- 안정된 정렬

   -> Because, 인접한 레코들끼리만 자리바꿈!