Quick Sort

Quick Sort

- 1960년에 C.A.R 호어가 고안함. 불필요한 계산을 제외하는 거의 최고의 정렬 알고리즘이다.  

- 한번 어느원소가 다른값과 비교하므로, 이후 그 원소들과 다시 비교하지 않아도 되기 때문에 빠르다. ( 즉, 하나의 원소를 다른 모든 원소들과 비교하지 않아도 된다.)

- 시간복잡도 : nLog(n) (최악의 경우 log(n^2) )

  (버블소트: log(n^2), 합병정렬: nlog(n) )

컨셉

- Pivot이 될 배열의 한 원소를 선택한다.

- Pivot을 기준으로 큰거나 같은값 배열, 작은값 배열 2개로 나눈다.

- 위에서 나눈 2개의 집단을 다시 Recursive 해서 정렬한다.

Source

#include "stdafx.h"

#include <iostream>

using namespace std;

void Swap(int aData[], int pos1, int pos2);

void Sort(int aData[], int length);

int _tmain(int argc, _TCHAR* argv[])

{

int aData[] = {5,4,1,3,6,9,8,7,10,2};

int length = sizeof(aData)/sizeof(int);

Sort(aData,length); // sort

for(int idx=0; idx<length; idx++) {

cout<<aData[idx]<<" ";

}

cout<<endl;

return 0;

}

// pos1 과 pos2 위치의 데이터 값을 바꾼다.

void Swap(int aData[], int pos1, int pos2) {

int temp = aData[pos2];

aData[pos2] = aData[pos1];

aData[pos1] = temp;

}

// 주어진 위치까지의 데이터를 가지고 분할한다.

void Sort(int aData[], int length) {

if(length<=1) return;

int newPos = 0; //새롭게 나누어지는 위치

int pivot = rand()%length; // pivot의 위치를 랜덤으로 돌린다.(이게 가장 성능이 좋다.)

Swap(aData, pivot, 0); // pitvot의 위치를 맨앞으로 이동

// pivot을 기준으로 작은값들을 앞으로 이동

for(int i=0;i<length; i++) { 

if(aData[i]<aData[0]) {

newPos++;

Swap(aData, newPos,i);

}

}

Swap(aData,0, newPos); // pivot값 원래대로

// 이제 작거나 같은값 정렬
Sort(aData, newPos);

// 큰값들 재정렬
Sort(aData+newPos+1, length-newPos-1);
}