BLOG

퀵 정렬과 합병 정렬은 리스트를 분할하고 정복하는 방법으로 정렬한다.

이 두 가지 정렬은 특징은 다음과 같다.

퀵 정렬 : 평균 복잡도는 O(NlogN) 이지만 최악의 복잡도는 O(N^2)이다.

합병 정렬 : 시간 복잡도는 O(NlogN)을 보장한다. 하지만 정렬을 하기 위해서 임시 배열을 사용하기 때문에

추가적인 메모리가 필요하다.

[C++]

#include <iostream>
using namespace std;

// 병합정렬 특 : 추가적인 메모리를 요구함
int size = 8;
int sorted[8]; // 정렬 배열은 무조건 전역 변수로 선언

void merge(int a[], int m, int middle, int n) {
  int i = m;
  int j = middle + 1;
  int k = m;
  // 작은 순서대로 배열에 삽입
  while (i <= middle && j <= n) {
    if (a[i] <= a[j]) {
      sorted[k] = a[i++];
    } else {
      sorted[k] = a[j++];
    }
    k++;
  }
  // 남은 데이터도 삽입
  if (i > middle) { // i가 먼저 끝남
    for (int t = j; t <= n; t++)
      sorted[k++] = a[t];
  } else {
    for (int t = i; t <= middle; t++)
      sorted[k++] = a[t];
  }
  // 정렬된 데이터를 실제 배열로 삽입
  for (int t = m; t <= n; t++)
    a[t] = sorted[t];
}

// IDEA : 일단 정확히 반으로 나누고 나중에 정렬
void mergeSort(int a[], int m, int n) {
  // 크기가 1보다 큰 경우
  if (m < n) {
    int middle = (m + n) / 2;
    mergeSort(a, m, middle);
    mergeSort(a, middle + 1, n);
    merge(a, m, middle, n);
  }
}

int main(void) {
  int arr[size] = {7, 6, 5, 8, 3, 5, 9, 1};
  mergeSort(arr, 0, size - 1);
  for (int i = 0; i < size; i++)
    cout << arr[i] << " ";
  return 0;
}

[JAVA]

package MergeSort;

public class MergeSort {

    static void merge(int[] list, int left, int mid, int right, int size) {
        int[] storage = new int[size];
        int i = left;
        int j = mid + 1;
        int k = left;

        // 분할 정렬된 list 들의 합병
        while (i <= mid && j <= right) {
            if (list[i] <= list[j])
                storage[k] = list[i++];
            else
                storage[k] = list[j++];
            k++;
        }

        // 선택받지 못한 값들을 차례대로 채워 넣는다
        if (i > mid) {
            for (int l = j; l <= right; l++)
                storage[k++] = list[l];
        } else {
            for (int l = i; l <= mid; l++)
                storage[k++] = list[l];
        }

        // 임시 배열에 저장된 값을 원래 배열로 옮김
        for (int l = left; l <= right; l++)
            list[l] = storage[l];
        
    }

    static void merge_sort(int[] list, int left, int right, int size) {
        if (left < right) {
            int mid = (left + right) / 2;
            merge_sort(list, left, mid, size); // 기준 왼쪽 정렬
            merge_sort(list, mid + 1, right, size); // 기준 오른쪽 정렬
            merge(list, left, mid, right, size); // 양쪽 정렬된 리스트를 합친다
        }
    }

    public static void main(String[] args) {
        int[] list = new int[10000];
        int[] clist = new int[10000];
        int size = list.length;
        
        // 역순으로 값을 넣는다.
        for(int i=0;i<size;i++) {
            list[i] = size-i;
            clist[i] = size-i;
        }
        
        // 병합 정렬 속도 측정
        long st = System.currentTimeMillis();
        merge_sort(list, 0, size - 1, size);
        long et = System.currentTimeMillis();
        System.out.println("mergesort time(nlogn) : "+(et-st));
        
        // 버블 정렬  측정
        st = System.currentTimeMillis();
        for(int i=0;i<size-1;i++) {
            for (int j = i+1; j < size; j++) {
                if(clist[i]>clist[j]) {
                    int tmp = clist[j];
                    clist[j] = clist[i];
                    clist[i] = tmp;
                }
            }
        }
        
        et = System.currentTimeMillis();
        System.out.println("bubble sort time(n^2) : "+(et-st));

    }

}

Merge Sort(NlogN)  vs Bubble Sort(N^2)  속도 비교

배열 사이즈를 동적으로 바꿔가면서 배열의 값들을 역순으로 넣고 비교했다.

사이즈가 적을 때는 버블 소트가 속도가 확실히 빠르지만, 충분히 큰 사이즈를 넣어줬을 때 부터는 

병합 정렬이 확실히 빨랐다.

https://www.youtube.com/watch?v=YJ-OUnZu7nQ&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=9

조건 : 탐색 전 배열이 정렬되야한다.

시간 복잡도 = log₂ N

"데이터의 수가 n일 때, 최악의 경우에 발생하는 비교연산의 횟수는?"

데이터의 수 n이 n/2, n/4, n/8 ... 줄어서 1이 될 때까지 비교연산을 한 번씩 진행하고, 마지막으로 n이 1일 때 비교연산을 한 번 더 진행하게 된다. 그리고 그것이 탐색 대상이 존재하지 않는 최악의 경우의 비교연산 횟수이다.

퀵 정렬 알고리즘은 병합 정렬과 마찬가지로 "분할 정복 (divede and conquer)"에 근거하여 만들어진 정렬 방법이다.

실제로 퀵 정렬 역시 정렬대상을 반씩 줄여나가는 과정을 포함한다.

시간복잡도

평균 - O(NlogN)

최악 - O(N^2)

퀵 정렬은 시간 복잡도가 O(NlogN)인 알고리즘이다. 하지만 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않으므로 동일한 빅-오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.

[C++]

#include <bits/stdc++.h>

// 일반적으로 퀵정렬이 빠르다.
// 평균 복잡도 n log n, 최악 복잡도 n^2
// 언제 최악의 복잡도가 나올까? 정렬된 데이터를 정렬할 때 

// 기준 값  =  pivot
int data[] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
int number = 10;

void quickSort(int *data, int start, int end) {
  if (start >= end) { // 원소가 1개인 경우 (=)
    return;
  }
  int key = start; // 키는 첫번째 원소 , 피벗
  int i = start + 1;
  int j = end;
  int tmp;

  while (i <= j) {                 // 엇갈릴때까지
    while (data[i] <= data[key]) { // 키값보다 큰값을 만날때까지 오른쪽 이동
      i++;
    }
    while (data[j] >= data[key] &&
           j > start) { // 키 값보다 작은 값을 만날때까지
      j--;
    }
    if (i > j) { // 현재 엇갈린 상태면 키 값과 교체
      tmp = data[j];
      data[j] = data[key];
      data[key] = tmp;
    } else {
      tmp = data[j];
      data[j] = data[i];
      data[i] = tmp;
    }
  }

  quickSort(data, start, j - 1);
  quickSort(data, j + 1, end);
}

int main() {
  quickSort(data, 0, number - 1);
  for (int i = 0; i < number; i++) {
    printf("%d ", data[i]);
  }
  return 0;
}

[JAVA]