정렬

 

1.Bubble Sort

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복합도가 O(n²) 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

int temp[9] = {3, 2, 1, 5, 4, 7, 8, 0, 6};
    int tempCount = 9;
    int hold;

    for (int loop=1; loop<tempCount; loop++) {
        for (int i=0; i<tempCount-1; i++) {
            if (temp[i] > temp[i+1]) {
                hold = temp[i];
                temp[i] = temp[i+1];
                temp[i+1] = hold;
            }
        }
    }
    //이제 temp에는 숫자가 작은 순서대로 있다.

2.Insertion Sort

삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

k번째 반복 후의 결과 배열은, 앞쪽 k + 1 항목이 정렬된 상태이다.

각 반복에서 정렬되지 않은 나머지 부분 중 첫 번째 항목은 제거되어 정확한 위치에 삽입된다. 그러므로 다음과 같은 결과가 된다.

배열이 길어질수록 효율이 떨어지지만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n²) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다.

void insertion_sort ( int *data, int n )
{
  int i, j, remember;
  i = n-1;
  while ( i-- > 0 ) 
  {
    remember = data[(j=i)];
    while ( ++j < n && remember > data[j] );

    if ( --j == i ) continue;
    memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
    data[j] = remember;
  }
}

3.Merge Sort

합병 정렬 또는 병합 정렬(merge sort)은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.

4.Selection Sort

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n²) 만큼의 시간이 걸린다.

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

5.Shell Sort

셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.

셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다.

• 삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.
• 삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.

셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다.

셸 정렬은 다음과 같은 과정으로 나눈다.

1. 데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.
2. 데이터를 다시 잘게 나누어서 삽입 정렬한다.
3. 이렇게 계속 하여 마침내 정렬이 된다.

셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 곱하고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 3N+1이 더 빠르다.

public static void shellSort(Comparable[] array) {
   //각 단계의 시작값
   int[] cols = {1,5,12,23,62,145,367,815,1968,4711,11969,27901,84801,
                 213331,543749,1355339,3501671,8810089,21521774,
                 58548857,157840433,410151271,1131376761,2147483647};
   int c;
   for (c = 0; cols[c] < array.length / 4; c++)
       ;

   // 매개변수 값에 대한 순환
   for (; c >= 0; c--) {
      int step = cols[c];
      for (int i = step; i < array.length; i++) {
         Comparable m = array[i];
         int j;
         for (j=i; j>=step; j-=step) {
            if (isLastBigger(array[j-step],m))
               break;
            array[j] = array[j-step];
         }
         array[j] = m;
      }
   }
}

6.Heap Sort

힙 정렬(Heapsort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성해야 하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 최대 힙을 구성하여 정렬하는 방법은 아래 예와 같다.

1. n개의 노드에 대한 전이진 트리를 구성. 이때 루트 노드부터 부노드, 왼쪽 자노드, 오른쪽 자노드 순으로 구성한다.
2. 최대 힙을 구성. 최대 힙이란 부노드가 자노드보다 큰 트리를 말하는데, 단말 노드를 자노드로 가진 부노드부터 구성하며 아래부터 루트까지 순차적으로 만들어 갈 수 있다. 단, 트리의 특성상 인덱스는 1부터 사용한다(0에 2를 곱해도 계속 0이 되는 현상을 방지)
3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환.
4. 2와 3을 반복한다.

이진 트리를 최대 힙으로 만들기 위하여 최대 힙으로 재구성 하는 과정이 트리의 깊이 만큼 이루어 지므로 O(n)의 수행시간이 걸린다. 구성된 최대 힙으로 힙 정렬을 수행하는데 걸리는 전체시간은 힙 구성시간과 n개의 데이터 삭제 및 재구성 시간을 포함한다. 시간 복잡도는

              = (log n+log(n-1)+...+log 2) 
            = (log n+log(n-1)+...+log 2)+(log n+log(n-1)+...+log 2)
            = O(n*log n)

따라서 힙 정렬은 일반적인 경우 O(n log n) 의 시간복잡도를 가진다.

7.Quick Sort

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다. 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n²)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬은 정렬을 위해 O(log n)만큼의 memory를 필요로한다. 또한 퀵 정렬은 불안정 정렬에 속한다.

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

public void quickSort(int left, int right)
{
   int i,j;
   TableEntry p, tmp;

   if(left<right)
   {
      i=left;
      j=right;
      p=table[left];
      //분할 과정
      while(i<j)
      {
         while(table[j].key>p.key)         j--;
         while(i<j && table[i].key<=p.key) i++;

         tmp = table[i];
         table[i]=table[j];
         table[j]=tmp;
      }
      table[left] = table[i];
      table[i]=p;
      //정렬 과정
      quickSort(left,i-1);
      quickSort(i+1,right);  
   }
}