C++ 퀵 정렬

1. pivot 을 정하기 -> O(1)

2. 작거나 같은 값을 정렬 -> O(n)  만큼 걸린다. 

3. 각각을 퀵정렬 한다. 

퀵정렬은 O(n log n ) 

하지만 최악의 경우는 O(n^2) 이 된다 이유는 pivot 을 잘 잡아야 한다. 중간값을 잘 잡아야 한다. 

---------------------------------------------------------------------------------------

pivot 보다

작은 값을 왼쪽에 

큰 값을 오른쪽에 두고 

4 7 8 9 1 2 3 9 1 10

4가 pivot 이면 

1 2 3 1 / 4 / 7 8 9 10 

왼쪽 오른쪽은 같은 방법으로 계산하면 된다. 

#include <iostream>

using namespace std;

int getRigth(int arr[],int start, int end, int pivot,int result[])

{

int inx=0;

for(int i = start;i<=end;i++)

{

if(arr[i] > pivot)

result[inx++] = arr[i];

}

return inx;

}

int getLeft(int arr[],int start, int end, int pivot,int result[])

{

int inx =0;

for(int i = start;i<=end;i++)

{

if(arr[i]<=pivot)

result[inx++]= arr[i];

}

return inx;

}

void quickSort(int arr[],int start, int end)

{

if(start >= end)

return;

int pivot = arr[start];

int left[50000],right[50000];

int left_cnt = getLeft(arr,start+1,end,pivot,left);

int right_cnt = getRigth(arr,start+1,end,pivot,right);

for(int i=0;i<left_cnt;i++)

{

arr[start+i] = left[i];

}

arr[start+left_cnt]= pivot;

for(int i =0;i<right_cnt;i++)

{

arr[start+left_cnt+1+i]=right[i];

}

quickSort(arr,start,start+left_cnt-1);

quickSort(arr,start+left_cnt+1,end);

}

int main()

{

int num;

int number[100000];

cin>>num;

for(int i =0;i<num;i++)

cin>>number[i];

quickSort(number,0,num-1);

for(int i=0;i<num;i++)

cout<<number[i]<<" ";

return 0;

}