정렬알고리즘2부 - 퀵,합병,히프 정렬

퀵 정렬 

퀵 정렬 의 기본 개념은 기준이 되는 숫자 피벗을 정한 후에 그 숫자를 기준으로 작은 데이터와 큰 데이터를 나누고 다시

분리한 양쪽의 데이터에서 다시 기준이 되는 숫자를 정한 후 그숫자를 기준으로 작은 데이터와 큰 데이터를 나누는 작업을

반복하는 것입니다.. 이러한 작업을 위해선 기준이 되는 값보다 작은 값을 찾기 위한 인덱스와 큰 값을 찾기 위한

인덱스가 필요합니다..

작은 값을 찾기 위한 인덱스는 왼쪽에서 진행하고 큰 값을 찾기 위한 인덱스는 오른쪽부터 진행합니다.

왼쪽에서 진행하는 인덱스는 기준값보다 크거나 같은 경우에 멈추고 오른쪽에서 진행하는 인덱스는 기준값보다 작거나 같은

경우에 멈춥니다. 그 상태에서 해당 인덱스에 위치한 데이터의 위치를 서로 바꿉니다. 

이 작업을 반복하면 기준값을 기준으로 좌측에는 작거나 같은 값, 우측에는 크거나 같은 값이 위치하게 됩니다.

1    Quick Sort Algorithm
2    
3    Partition // ‘분할’의 뜻을 가지고 있다.
4    {
5    low = left + 1 // low의 위치는 left보다 한 칸 오른쪽이다.
6    high = right // high의 위치는 right와 동일하다.
7    pivot = arr[left] // 피벗의 위치는 가장 왼쪽이다.
8    
9    while (low <= high) // low와 high가 교차되지 않을 때까지 계속 반복한다.
10    {
11    while (pivot >= arr[low] and low <= right) // 피벗보다 큰 값을 찾을 때까지
12    low++ // low를 한 칸 오른쪽으로 이동한다.
13    
14    while (pivot <= arr[high] and high >= (left + 1) // 피벗보다 작은 값을 찾을 때까지
15    high-- // high를 한 칸 왼쪽으로 이동한다.
16    
17    
18    if (low <= high) // low와 high가 교차되지 않았다면,
19    low가 가리키는 값과 high가 가리키는 값 교환
20    }
21    피벗의 값과 high가 가리키는 값 교환 // low와 high가 교차되었다면
22    return high // high의 위치를 가져온다.
23    }
 

퀵 정렬은 내부 정렬 방법 중에서 수행속도가 가장 빠른 알고리즘입니다. 동작 방식에 있어서는 스택을 사용하여 재귀호출

을 기반으로 작동합니다. 퀵 정렬은 N개의 데이터를 정렬할 때, 최악의 경우에는O(n^2)번의 비교를 수행하고, 평균적으로

O(nlogn)번의 비교를 수행합니다. 최선의 경우에 저장된 배열이 각 분할단계에서 정확히 이등분할 때 교환 및 비교 횟수

가 적어 매우 빠른 속도로 수행합니다. 하지만 안전성이 뒤떨어지는 단점이 있습니다.

합병 정렬

합병 정렬은 단어의 뜻처럼 2개의 부분 파일을 서로 합치면서 정렬해 나가는 것 을 말합니다. 이를 위해서는 정렬되지

않은 데이터를 합병하기 위한 최소 단위로 먼저 분할하는 것이 필요합니다.

예를 들어 8개의 데이터가 정렬되지 않은 상태로 있다면 먼저 해당 데이터를 2개의 부분 파일로 나눕니다. 이 2개의

부분 파일을 각각 또 하나의 정렬되지 않은 데이터로 보고 다시 각각을 2개로 나눕니다. 그러면 총 4개의 부분 파일이

만들어 지겠죠. 이를 다시 각각에 대하여 분할하면 최소단위의 개별 데이터가 됩니다.

이제 분리된 데이터를 2개씩 합병하면서 정렬합니다. 최초 합병을 실행하면 각 2개의 데이터가 정렬되면서 총 4개의

부분 파일을 생성합니다. 다시 4개의 부분 파일을 2개씩 묶으면서 정렬을 수행합니다.

이 과정을 수행하면 총 4개로 구성된 2개의 부분 파일을 생성합니다. 마지막으로 2개의 부분 파일을 하나로 합병하면서 

정렬을 수행하면 최종적으로 정렬된 8개의 데이터를 얻을 수 있습니다.

#include <stdio.h>
 
#define max 10
 
int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };
int b[10];
 
void merging(int low, int mid, int high) {
   int l1, l2, i;
 
   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
      if(a[l1] <= a[l2])
         b[i] = a[l1++];
      else
         b[i] = a[l2++];
   }
   
   while(l1 <= mid)    
      b[i++] = a[l1++];
 
   while(l2 <= high)   
      b[i++] = a[l2++];
 
   for(i = low; i <= high; i++)
      a[i] = b[i];
}
 
void sort(int low, int high) {
   int mid;
   
   if(low < high) {
      mid = (low + high) / 2;
      sort(low, mid);
      sort(mid+1, high);
      merging(low, mid, high);
   } else { 
      return;
   }   
}
 
int main() { 
   int i;
 
   printf("List before sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
 
   sort(0, max);
 
   printf("\nList after sorting\n");
   
   for(i = 0; i <= max; i++)
      printf("%d ", a[i]);
}

합병 정렬의 수행시간은 최악의 경우에도 O(nlogn)이고 별도의 임시 기억장소가 필요하여 실제로는 

수행시간이 많이 걸리며 외부 정렬에 주로 활용 합니다.

히프정렬

히프 정렬은 히프의 개념과 특징을 먼저 알아야합니다. 히프란 여러 개의 노드들 가운데 가장 큰 키값을 가지는 노드나 가장 

작은 값을 가지는 노드를 빠른 시간 내에 찾아내도록 만들어진 자료 구조를 말합니다. 히프는 완전 이진 나무의 하나로서 각각

의 노드는 유일한 키값을 가지며 우선순위를 가지는 큐라는 의미에서 우선순위 큐라고도 합니다. 이러한 히프는 크게 2가지로

나눌 수 있는데 하나는 Max-heap이며 또 하나는 min-heap 입니다. 

max-heap의 한 노드는 그노드의 모든 자식들보다 큰 키값을 가집니다. 루트에는 항상 큰 키값을 가지는 노드가 위치하므로 

우선순위 큐를 구성하는 데 적합한 자료 구조입니다.

min-heap는 max-heap와 반대로 한 노드는 그 노드의 모든 후손 노드들보다 작은 키값을 가집니다.

히프 정렬은 앞에서 언급한 max-heap를 이용합니다.

원본 데이터를 max-heap를 이용하여 정렬하면 최상단 노드에 최댓값이 위치하게 됩니다. 배열의 개념으로 보면 맨 앞에

위치하게 되는 거죠. 다시 max-heap를 이용하여 정렬하면 또 다시 남은 데이터 중어세 최댓값이 최상단 노드에 위치합니다.

그리고 배열의 개념으로 맨 앞에 위치하게 되면 앞서 최댓값으로 지정된 값의 바로 앞에 위치시킵니다. 이러한 방법을

반복하면 정렬된 배열 데이터를 얻을수 있습니다.

void downheap(int cur, int k)
{
  int left, right, p;
    while(cur < k) {
      left = cur * 2 + 1;
      right = cur * 2 + 2;and t
 
      if (left >= k && right >= k) break;
 
      p = cur;
      if (left < k && data[p] < data[left]) {
        p = left;
      }
      if (right < k && data[p] < data[right]) {
        p = right;
      }
      if (p == cur) break;
 
      swap(&data[cur],&data[p]);
      cur=p;
    }
}
 
void heapify(int n)
{
  int i,p;
  for(i = (n-1)/2; i >= 0; i--){
    downheap(i,n);
  }
  //for(i=0;i<size;++i)printf("%d ",data[i]);
  //printf("\n");
}
 
void heap()
{
  int k;
  heapify(size);
  for(k = size-1; k > 0; ){
    swap(&data[0],&data[k]);
    //k--;
    downheap(0,k);
    k--;
  }
}

히프 정렬은 maxheap를 만들어서 deletemax를 반복 수행하여 정렬하므로 n을 입력 파일의 크기라 하면 buildheap O(n), n번

deletemax O(nlogn)의 성능을 갖고 있으며, buildheap는 내부 노드에서만 수행합니다. 그리고 단말 노드는 더이상 내려갈 곳

이 없으므로 적용할 필요가 없습니다.

이론적으로는 이상적인 O(nlogn)이나 실제 수행시간이 깁니다. 그러나 뛰어난 성능을 가지면서도 추가적인 메모리가

필요하지 않아 많이 사용합니다.