this.code(9).DS_ sort I. [heap, merge, quick]sort

※ 정렬 (Sorting)

정렬은 오름차순, 내림차순과 같은 방식으로 특정 필드값인 key를 기준으로 value간의 정렬을 진행해 주며 다음 2가지로 나뉜다.

단순, 비효율적 방법: 삽입, 선택, 버블 정렬      ==> 대개 자료의 개수가 적을 때 사용
복잡, 효율적인 방법: 힙, 합병, 퀵 정렬             ==> 반드시 자료의 개수가 많다면 효율적 알고리즘을 사용해야 함.

 

🧐 복잡하지만, 효율적인 정렬 방법 

👉 힙 정렬 (Heap Sort)

힙 (heap)은 완전 이진트리(complete binary tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조다.

힙(heap)은 요소들이 완전히 정렬된 것은 아니지만 일종의 반 정렬상태를 유지한다.
이로 인해 삽입 삭제의 시간복잡도가 O(log n)으로 다른 방법보다 훨씬 유리하다.

이런 힙은 여러 개의 값들 중 최댓값과 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조이다.
이를 위해 부모 노드의 key 값  >  자식 노드의 key 값 을 항상 만족하도록 만들어졌다. (보통 최대힙으로 가정하는 편)
단, BST와는 다르게 Heap tree는 중복된 값을 허용한다.

- 위는 힙에 대한 설명으로 힙정렬은 다음과 같은 방식으로 진행한다.

1. 정렬할 배열을 먼저 최소 힙으로 변환한다.
2. 가장 작은 원소부터 차례대로 추출한다.

#include <queue>
#include <functional>  //최소 힙을 사용하기에 써줘야 함
using namespace std;

// 최대 힙을 사용한 내림차순 정렬
void heapSortDec(int arr[], int n) {
    priority_queue<int> maxHeap;
    for (int i = 0; i < n; i++) {
        maxHeap.push(arr[i]);
    }
    // maxHeap을 이용해 내림차순으로 정렬
    for (int i = 0; i < n; i++) {
        arr[i] = maxHeap.top();
        maxHeap.pop();
    }
}

// 최소 힙을 사용한 오름차순 정렬
void heapSortInc(int arr[], int n) {
    priority_queue<int, vector<int>, greater<int> > minHeap;
    for (int i = 0; i < n; i++) {
        minHeap.push(arr[i]);
    }
    // minHeap을 이용해 오름차순으로 정렬
    for (int i = 0; i < n; i++) {
        arr[i] = minHeap.top();
        minHeap.pop();
    }
}

 

 

 

👉 합병 정렬 (Merge Sort)

합병정렬은 분할 정복(divide and conquer)기법을 바탕으로 두고 있다.

🤨 Divide and Conquer란?

1. 하나의 리스트를 2개의 균등한 크기로 분할 (점점 작은 sub problem을 만드는 방법)
2. 분할을 계속 지속해서 1개의 원소로 나눈 후 정렬 진행
3. 두 원소씩 다시 합쳐 전체가 정렬된 리스트를 만드는 방법

🤨 merge Algorithm

merge(A, left, mid, last)
b1 <- left;
e1 <- mid;
b2 <- mid + 1;
e2 <- right;
sorted 배열을 생성;
index <- 0;
while b1 ≤ e1 and b2 ≤ e2 do
    if (A[b1] < A[b2])
        then
            sorted[idx] <- A[b1];
            b1++;
            idx++;
         else
             sorted[idx] <- A[b2];
             b2++;
             idx++;
요소가 남아있는 부분배열을 sorted로 복사;
sorted를 A로 복사;

🤨 merge sort Algorithm

mergeSort (A, left, right)
if left < right
    mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid + 1, right)
    merge(A, left, mid, right)

#define Max_Size 1024
static void merge(int A[], int left, int mid, int right) {
    int i, j, k = left, l;
    static int sorted[Max_Size];
    for (i = left, j = mid + 1; i <= mid && j <= right; )
        sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];
    if (i > mid)
        for (l = j; l <= right; l++, k++)
            sorted[k] = A[l];
    else
        for (l = i; l <= mid; l++, k++)
            sorted[k] = A[l];
        for (l = left; l <= right; l++)
            A[l] = sorted[l];
}

void mergeSort (int A[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid + 1, right);
        merge(A, left, mid, right);
    }
}

 

 

 

 

👉 퀵 정렬 (Quick Sort)

평균적으로 매우 빠른 속도를 자랑하는 정렬방법으로 위의 합병정렬같은 분할 정복(divide and conquer)기법을 바탕으로 두고 있다.

다만 합병정렬과는 달리 리스트를 균등하게 분할하지 않고 리스트 안의 한 요소를 pivot으로 선택한다.

퀵정렬의 과정은 아래와 같이 진행된다.

🤨 퀵 정렬 과정

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

이를 위해 중요한 3개의 함수가 사용된다.
- quickSort: 퀵정렬 알고리즘을 이용해 배열의 left ~ right를 오름차순으로 정렬.
- partition: 퀵정렬에서 가장 중요한 함수로 pivot을 설정, 데이터를 left, right로 크기에 따라 이동시킴.
- swap: 조건에 따라 pivot기준으로 왼쪽과 오른쪽의 값들을 서로 바꿔주기 위한 함수

 

https://coding-factory.tistory.com/615

#include <iostream>
using namespace std;

static int partition(int A[], int left, int right) {
    int low = left;
    int high = right + 1;
    int pivot = A[low];

    do {
        do {
            low++;
        } while (low <= high && A[low] < pivot);
        do {
            high--;
        } while (high >= left && A[high] > pivot);
        if (low < high)
            swap(A[low], A[high]);
    } while (low < high);
    swap(A[left], A[high]);
    return high;
}

void quickSort (int A[], int left, int right) {
    if (left < right){
        int q = partition(A, left, right);
        quickSort(A, left, q - 1);
        quickSort(A, q + 1, right);
    }
}