알고리즘 (2): 거품 정렬, 삽입 정렬, 선택 정렬, 합병 정렬, 빠른 정렬

---

정렬 알고리즘

• 정렬 알고리즘은 원소들을 일정한 순서대로 열거하는 알고리즘이다.

• n개의 입력이 주어졌을 때 이를 효율적으로 정렬하는 것은 매우 중요하다.

• 정렬 알고리즘은 크게 수행시간(time complexity), 추가 공간의 필요성(in-place), 중복된 값에 대한 처리유무(stability)로 비교할 수 있다.

이 글에서의 정렬 알고리즘은 주어진 입력이 int형의 배열이라고 가정하고 설명함.

거품 정렬(Bubble Sort)

• 인접한 두 원소의 관계를 검사하여 정렬하는 알고리즘.

• 거품 정렬은 코드가 단순하며 이미 정렬된 입력에 대해 가장 빠르게 수행된다.

  void bubbleSort(int n, int* array){
      for(int i=0;i<n-1;i++){
          for(int j=i+1;j<n;j++){
              if(array[j]<array[i]){
                  int temp = array[i];
                  array[i] = array[j];
                  array[j] = temp;
              }
          }
      }
  }

삽입 정렬(Insertion Sort)

• 모든 원소를 이미 정렬된 부분과 비교하여 위치를 찾아 삽입하는 알고리즘.

• 첫 원소를 정렬된 상태라고 가정하고 두번째 원소의 삽입부터 삽입된 배열과 대소관계를 검사하여 원소의 위치를 결정한다.

• 거품 정렬에 비해 대입연산의 일부분을 외부 루프에서 수행하므로 수행시간이 빠르지만 최악의 경우 삽입되는 모든 $O(n^2)$의 시간복잡도를 갖는다.

void insertionSort(int n,int* array){
    for(int i=1;i<n;i++){
        int x = array[i];
        int j = i-1;
        while(j>=0 && array[j]>x){
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = x;
    }
}

선택 정렬(Selection Sort)

• 정렬되지 않은 모든 원소 중 최소 값을 선택하여 정렬하는 알고리즘.

• 선택 정렬은 내부 루프에서 대입연산을 수행하지 않아 대입 연산의 수행시간은 $3n$으로 최악의 경우에도 빠른 수행시간을 갖는다.

• 선택 정렬은 대소관계에 만족하는 경우 대입 연산을 수행하지 않는 거품 정렬, 삽입 정렬에 비해 내부 루프를 모두 탐색하고 외부 루프에서 대입 연산을 수행하므로 평균 수행시간이 최악의 경우의 수행시간과 같다는 단점이 있다.

• 또한 최소값의 위치와 교환이 일어나는 인덱스의 값이 다른 원소와 중복된 값인 경우, 들어온 순서에 상관없이 정렬이 이루어진다는 단점이 있다.(Non-Stable)

void selectionSort(int n,int* array){
    for(int i=0;i<n-1;i++){
        int smallest = i;
        for(int j=i+1;j<n;j++){
            if(array[j]<array[smallest])    smallest = j;
        }
        int temp = array[smallest];
        array[smallest] =array[i];
        array[i] = temp;
    }
}

합병 정렬(Merge Sort)

• 문제를 해결하기 쉽도록 배열을 여러 개의 작은 배열로 나누고(divide) 나눈 배열을 각각 정렬한 후(Conquer) 정렬한 배열을 통합하는 분할정복(divide & conquer)를 사용하는 알고리즘.

• 배열을 합치는 과정에서 분할되었던 두 배열의 원소의 대소관계를 비교하여 반환될 배열에 차례대로 삽입하여 정렬이 수행된다.

• 순서에 의한 정렬이 배열의 통합에서 수행되므로 재귀함수를 사용하여 구현할 수 있고 수행시간도 $O(nlog n)$으로 빠르다는 장점이 있다.

• 배열을 분할할때마다 분할된 배열을 저장하는 공간이 추가적으로 필요하여 $2n$의 공간 복잡도를 갖는다는 단점이 있다. (제자리정렬 알고리즘이 아니다.)

void mergeSort(int n,int* array){
    int h = n/2, m=n-h;
    int* U = new int[h];
    int* V = new int[m];
    if(n>1){
        for(int i=0;i<n;i++){
            if(i<h){
                U[i] = array[i];
            }else{
                V[i-h] = array[i];
            }
        }
        mergeSort(h,U);
        mergeSort(m,V);
        merge(h,m,U,V,array);
    }
}
void merge(int h, int m, int* U, int* V, int* array){
    int i=0,j=0,k=0;
    while(i<h&&j<m){
        if(U[i]<V[j]){
            array[k] = U[i];
            i++;
        }else{
            array[k] = V[j];
            j++;
        }
        k++;
    }
    if(i>h){
        for(;j<m;j++){
            array[i+j] = V[j];
        }
    }else{
        for(; i<h;i++){
            array[i+j] = U[i];
        }
    }
}

빠른 정렬(Quick Sort)

• 임의의 기준(pivot)을 정하고 기준을 중심으로 관계를 검사하여 교환하는 알고리즘.

• 빠른 정렬은 분할정복(divide & conquer)의 방식을 사용하며 이에 분할교환정렬(Partition Exchange Sort)이라고도 한다.

• 기준 값과의 대소비교를 통해 기준 값보다 작은 값들의 집합과 큰 값들의 집합으로 분할하는 방식을 반복함으로써 정렬이 이루어진다.

• 분할정복 방식이면서 퀵 정렬과 달리 추가적인 공간을 사용하지 않고 정렬할 수 있으며 재귀함수로 순환이 시작되기 전에 대부분의 작업이 수행되어.

• 입력 값들을 절반으로 나누어 정렬함으로써 수행시간은 $O(n logn)$이지만 기준 값을 최솟값 혹은 최대값으로 설정할 경우 정렬결과가 한쪽으로 쏠려(Skewed) 최악의 경우 수행시간은 $O(n^2)$을 갖는다.

• 중복된 값의 입력에 대하여 추가적인 공간을 사용하는 경우, 입력 순서를 유지할 수 있지만(non In-place, Stable) 추가적인 공간을 사용하지 않는 경우, 입력 순서에 상관없이 교환이 발생하므로(In-place, nonStable) Stable과 In-place 중 우선적으로 필요한 것을 선택해야한다.

• 기준을 정하는 방법은 여러가지 방법이 있지만, 임의의 3개의 원소 중 중간값을 기준 값으로 설정하고 가장 큰 값을 기준 보다 뒤에 있도록 옮겨 최소 1개의 큰 값들의 집합을 갖도록 하는 중간값 분할(Median-of-Three Partitioning)이 제일 좋은 방법으로 알려져 있다.

//Median-3 퀵 정렬 알고리즘
void quickSort(int * array, int start, int end){
    int pivot,m,l,r;
    if(end-start>1){
        l = start;
        r = end-1;
        m = (start+end)/2;
        if(array[start]>array[m]) swap(array,start,m);
        if(array[start]>array[end]) swap(array,start,end);
        if(array[m]>array[end]) swap(array,m,end);
        swap(array,m,r);
        pivot = array[r];    
        for(;;){
            while(array[++l]<pivot);
            while(array[--r]>pivot);
            if(l>=r) break;
            swap(array,l,r);
        }
        swap(array,l,end-1);
        quickSort(array,start,l-1);
        quickSort(array,l+1,end);
    }else if(array[start]>array[end]) swap(array,start,end);
}
void swap(int* array,int a, int b){
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}