퀵정렬 알고리즘 ( Quick Sort )

퀵 정렬 알고리즘은 병합 정렬과 마찬가지로 "분할 정복 (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]