정렬 - 버블정렬(bubble sort), 선택정렬(selection sort), 퀵정렬(quick sort)

선택정렬(Selection Sort)

1. 선택정렬(Selection Sort)이란?

-. 실제 프로그래밍에서 많이 사용되는 간단한 정렬방법으로 오름차순을 기준으로 한다면,

    최소값을 찾아 왼쪽으로 이동시키는데 배열크기만큼 반복하여 정렬하는 방법이다.

-. 가장 작은 값을 찾아서 첫번째 위치에 있는 값과 교환하고, 두번째로 작은 값을 찾아 두번째

    위치에 있는 값과 교환하는 방법으로 이러한 방법을 반복한다.

 

2. 선택정렬을 이용하여 오름차순으로 정렬하는 방법

 

 

3. 선택정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면    이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

-. 5개의 값을 오름차순으로 선택정렬을 하면...

   공식에 의해서 5(5 – 1)/2 = 10 가 성립된다.

   즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다.

 

4. 선택정렬의 연산시간

   -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

-. 수학식으로 표현하면 아래와 같다.

     = n(n – 1) – (n – 1)/2 = n(n - 1)/2 이므로 Worst Case는 n(n – 1)/2 이다.

   그래서 연산시간은 O(n²)가 되는 것이다.

  

5. 선택정렬의 장점

-. 데이터의 양이 적을 때 아주 좋은 성능을 나타낸다.

-. 작은 값을 선택하기 위해서 비교는 여러 번 하지만 교환횟수가 작다

 

6. 선택정렬의 단점

-. 가장 작은 값과 현재값을 교환하는 방식이라 현재값이 뒤쪽의 어디로 갈지 알 수 없으므로

    안전성이 없다.

-. 100개 이상의 자료에 대해서는 속도가 급격히 떨어져서 적절히 사용되기가 힘들다.

 

7. 선택정렬을 이용해서 작성한 예제

#include "stdio.h"   void Select_Sort(int parm_data[], int parm_count) {     int min_data = 0, min_index = 0;     int i, j;     int comparison_count = 0;       for(i = 0; i < parm_count - 1; i++){         min_index = i;         min_data = parm_data[i];         for(j = i + 1; j < parm_count; j++){             comparison_count++;             if(min_data > parm_data[j]){                 min_data = parm_data[j];                 min_index = j;             }         }         parm_data[min_index] = parm_data[i];         parm_data[i] = min_data;     }     printf("총 비교회수는 [ %d 회] 이다.", comparison_count);     printf("\n\n\n");   }   void main() {     int array[5] = {7, 4, 11, 9, 2};     int i;       printf("=== 선택정렬하기 전 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Select_Sort(array, 5);     printf("=== 선택정렬한 후 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

 

결과는 아래와 같습니다.

버블정렬(bubble sort)

 

1. 버블정렬이란?

-. 인접해 있는 두 개의 값을 비교해서 자료 교환을 한다.

-. 오름차순 정렬은 두 개의 값을 비교해서 큰 값을 오른쪽으로 보내는 방식이다,

    내림차순 정렬은 두 개의 값을 비교해서 작은 값을 오른쪽으로 보내는 방식이다.

 

2. 버블정렬(Bubble Sort)과 유사한 용어

-. Interchange Sort

-. Shifting Sort

 

3. 버블정렬을 이용하여 오름차순으로 정렬하는 방법

 

 

4. 버블정렬의 비교회수

-. 비교 회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면    이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

-. 5개의 값을 오름차순으로 버블정렬을 하면...

   공식에 의해서 5(5 – 1)/2 = 10 가 성립된다.

   즉, 총 10번의 비교를 통해서 오름차순으로 정렬된 값을 볼 수 있다.

 

5. 버블정렬의 연산시간

   -. 연산시간 공식 : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

  

6. 버블정렬의 장점

-. 인접해 있는 두 개의 값을 비교하여 자료의 위치를 이동시키므로 단순하다.

-. 여러 차례 값을 비교하므로 안전성 있게 값을 정렬한다.

 

7. 버블정렬의 단점

-. 첫번째 패스에서 자료의 교환이 없었다면 주어진 값은 이미 오름차순으로 정렬된 상태이지만,

   최대 N(N – 1)/2 만큼의 비교회수와 O(n²) 만큼의 연산시간이 소요된다.

  -. 다른 정렬에 비해서 연산시간이 오래 걸린다.

8. 버블정렬을 이용해서 작성한 예제

#include "stdio.h"   void Bubble_Sort(int parm_data[], int parm_count) {     int i, j, temp = 0;     int comparison_count = 0;       for(i = 0; i < parm_count - 1; i++){         for(j = 0; j < parm_count - 1 - i; j++){             comparison_count++;             if(parm_data[j] > parm_data[j+1]){                 temp = parm_data[j];                 parm_data[j] = parm_data[j+1];                 parm_data[j+1] = temp;                                                 }         }     }     printf("총 비교회수는 [ %d 회] 이다.", comparison_count);     printf("\n\n\n"); }   void main() {     int array[5] = {7, 4, 11, 9, 2};     int i;       printf("=== 버블정렬하기 전 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Bubble_Sort(array, 5);     printf("=== 버블정렬한 후 ===\n\n");     for(i = 0; i < 5; i++) printf("%d   ", array[i]);     printf("\n\n");   }

 결과는 아래와 같습니다.

 

버블 소트의 단점중에 이미 소트가 완료된 경우를 체크하지 못하고 계속 정렬을 시도하는 것입니다.
즉, 오름차순 정렬인데 데이터가 1,2,3,4 로 되어 있는 경우, 정렬할 필요가 없다는것을 알지
못하고 6번을 비교하게 됩니다. 따라서 이 부분을 고려할수 있도록 소스를 수정해서 사용하는
경우도 많습니다. 방법은 아래와 같습니다.

void Ex_Bubble_Sort(int parm_data[], int parm_count)
{
    int i, j, temp = 0, flag = 1;
    int comparison_count = 0;

    for(i = 0; i < parm_count - 1; i++){
        // 각 패스의 시작시점에서 flag값을 1로 설정한다.
        flag = 1;
        for(j = 0; j < parm_count - 1 - i; j++){
            comparison_count++;
            if(parm_data[j] > parm_data[j+1]){
                // 자리 바꿈이 일어났다면 flag 값을 0으로 변경한다.
                flag = 0;
                temp = parm_data[j];
                parm_data[j] = parm_data[j+1];
                parm_data[j+1] = temp;                                   
            }
        }
        // flag값이 1이라는 소리는 한번도 자리바꿈이 일어나지 않았다는 뜻이다.
        // 따라서 더 이상 정렬할 필요가 없다는 것으로 간주하여 종료한다.
        if(flag == 1) break;
    }

    printf("총 비교회수는 [ %d 회] 이다.", comparison_count);
    printf("\n\n\n");
}

퀵정렬(Quick Sort)

1. 퀵정렬(Quick Sort)이란?

-. 교환정렬의 일종이며 분할-정복법(divide and conquer)에 근거한다.

-. 정렬할 리스트를 두개로 분할하고 정렬하는 방법이다.

-. 축(pivot)값을 기준으로 정렬하는데, 축값을 중심으로 축값보다 큰 값은 오른쪽 리스트에

   작은 값은 왼쪽리스트로 이동시킨다. (첫번째의 데이터를 축값으로 한다.)

-. 오른쪽 리스트와 왼쪽 리스트부분은 독립적인 단위로 정렬하여 오른쪽 리스트부분에 대한

   새로운 분할 축값을 선택하여 두 부분으로 분리하고, 왼쪽 리스트부분 역시 새로운 축값을

   선택하여 두 부분으로 분리하는 과정을 반복하는데 리스트들은 재귀적 방법으로 각각 재배열

   하는 방식이다.

-. 각 분할 자료개수가 1이 되면 정렬은 완료된다.

 

2. 퀵정렬을 이용하여 오름차순으로 정렬하는 방법

 

3. 퀵정렬의 비교회수

-. 최선일 경우의 비교회수 공식 : N - 1

-. 최악일 경우의 비교회수 공식 : N(N – 1)/2

-. 위의 그림을 보시면 아시겠지만 제일 처음에는 (N – 1)번을 비교하고,

   그 다음에는 (N – 2)번 만큼 비교하고, 그 다음은 (N – 3)번을 비교하면서 비교회수가 1이 될

   때까지 이 작업을 반복할 것이다.

-. 비교회수는 (N – 1) + (N – 2) + (N – 3) …… + 1 이 될 것이다.

   최대 (N – 1)번을 수행할 것이며, 각 패스가 수행할 때마다

   수학식으로 표현하면   이므로 공식은 N(N – 1)/2 이런 공식이 성립된다.

 

4. 퀵정렬의 연산시간

  -. 연산시간 공식(평균) : 0(n log n)

  -. 연산시간 공식(최악이 경우) : O(n²)

-. 연산시간을 표기하는 방법은 일반적으로 사용하는 O표기법인데, 이 O표기법은 ‘최악의 경우’

   (Worst Case)에 대한 연산시간을 나타낸다.

  

5. 퀵정렬의 장점

-. 정렬할 데이터가 이미 준비되어 있고 모든 데이터들을 정렬해야 할 경우에 가장 빠른

   수행속도를 보여준다.

 

6. 퀵정렬의 단점

-. 축(pivot)값이 같은 것끼리는 순서관계가 파괴된다.

   (중요한 데이터의 경우에는 퀵정렬을 사용하지 않는 것이 좋다.)

-. 안정성이 없다.

 

7. 퀵정렬을 이용해서 작성한 예제

#include "stdio.h"   void Quick_Recursive(int parm_data[], int parm_left, int parm_right);   void Quick_Sort(int parm_data[], int parm_count) {     Quick_Recursive(parm_data, 0, parm_count - 1); }   void Quick_Recursive(int parm_data[], int parm_left, int parm_right) {     int pivot, left_hold, right_hold;     left_hold = parm_left;     right_hold = parm_right;       // 0번째 원소를 pivot으로 선택한다.     pivot = parm_data[parm_left];       while(parm_left < parm_right){         while((parm_data[parm_right] >= pivot) && (parm_left < parm_right)) parm_right--;         if(parm_left != parm_right){             parm_data[parm_left] = parm_data[parm_right];         }           while((parm_data[parm_left] <= pivot) && (parm_left < parm_right)) parm_left++;         if(parm_left != parm_right){            parm_data[parm_right] = parm_data[parm_left];            parm_right--;         }     }       parm_data[parm_left] = pivot;     pivot = parm_left;     parm_left = left_hold;     parm_right = right_hold;       if(parm_left < pivot) Quick_Recursive(parm_data, parm_left, pivot - 1);     if(parm_right > pivot) Quick_Recursive(parm_data, pivot + 1, parm_right); }   void main() {     int array[10] = {27, 4, 37, 2, 62, 12, 59, 16, 49, 18};     int i;       printf("=== 퀵정렬하기 전 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n");     printf("================================");     printf("\n\n");       Quick_Sort(array, 10);     printf("=== 퀵정렬한 후 ===\n\n");     for(i = 0; i < 10; i++) printf("%d   ", array[i]);     printf("\n\n"); }

 

  결과는 아래와 같습니다.

자료출처 : http://www.tipssoft.com