[정렬] 퀵정렬

안녕하세요.

그 동안 회사일과 학업일이 넘 바빠 뜸했는데요~

포스팅할것은 정렬 중 유명한 퀵정렬입니다.

 

 

 

퀵정렬이란?

 

정렬할 데이터 중 피벗이라는 특정 값을 정해 그것을 기준으로 두 부분으로 나눈후 정렬하는 것.

 

뭐라고 하는거냐!

생략하지 말고 얘기해랏

 

 

1. 먼저 아래의 데이터 중에 임의로 30을 뽑아 피벗으로 지정합니다.

 

 

 

2. 피벗(30)을 기준으로 30보다 작은 원소들은 왼쪽에, 큰 원소들은 오른쪽에 모아둡니다.

 

 

 

 

 

3. 모아둔 부분을 퀵정렬을 이용해 정렬합니다.

 

 

 

퀵정렬의 원리에 대해 알아봤는데요.

이렇게 그림으로 그려보면 간단하지만 궁금한게 생깁니다.

첫번째, 피벗 30을 기준으로 어떻게 비교해 작은건 왼쪽, 큰건 오른쪽으로 나눌까요? <-퀵정렬의 핵심

두번째, 피벗을 정하는 기준은 무엇일까요?

 

 

 

 

 

퀵정렬 풀이

 

일단 두번째 문제였던 피벗을 정하는 기준은

보통은 주어진 데이터배열의 왼쪽에 있는 원소를 피벗으로 정합니다.

퀵정렬의 성능이 좋으려면 피벗을 정하는 것이 중요한데 이건 성능부분에서 보도록 하고

중요한 문제였던 피벗 30을 기준으로 어떻게 비교해 작은건 왼쪽, 큰건 오른쪽으로 나눌까?를 알아보겠습니다.

위에꺼보다 이 부분이 중요하니 꼭 보시길 바랍니다.

 

 

먼저 아래와 같은 데이터 배열이 주어졌다고 가정합니다.

 

Array[] = {30, 50, 7, 40, 88, 15, 45, 52, 22, 33, 77, 99, 10, 60, 1};

 

1. 왼쪽에 있는 첫번째 원소를 피벗으로 정합니다.       2. 피벗 30을 제외한 원소들에서 30옆에 있는 50부터 시작해     왼쪽에서 오른쪽으로 이동하면서 30보다 크거나 같은 원소를 찾고    맨 오른쪽인 1부터 시작해 오른쪽에서 왼쪽으로 이동하면서 30보다 작은 원소를 찾습니다. 왼쪽에서 시작한 50은 30보다 크므로 선택되었고,  오른쪽에서 시작한 1도 30보다 작으므로 선택되었습니다.           3. 위 조건에 맞춰져 찾은 원소를 서로 교환합니다.             4. 왼쪽에서 오른쪽으로 갈때 이제 7을 검사하니 30보다 작으니 다음 오른쪽으로(40) 넘어가고    오른쪽에서 왼쪽으로 갈 때 60을 검사하니 조건에 안맞으니 왼쪽(10)으로 넘어갑니다.    해당 40은 피벗보다 크니까 조건에 맞고 10도 피벗보다 작으니 조건에 맞으니 교환.             5. 위와 같이 왼->오, 오->왼으로 이동하면서 조건에 맞게 교환을 해줍니다.               6. 다시 찾기를 하면 15와 45가 있는데 이미 45가 15보다 오른쪽에 있으므로 교환하지 않고 멈춥니다.           7. 찾기가 멈췄으므로 이 때 15와 30을 교환해준다. 그럼 30을 기준으로 왼쪽은 작은 원소들, 오른쪽은 큰원소가 배치되었습니다.             8. 왼쪽 부분(15~22)과 오른쪽 부분(45~50)을 퀵정렬을 이용해 정렬해줍니다.   8_1. 먼저 15~22배열에서는 왼쪽 15를 피벗으로 잡아줍니다.   8_2. 왼쪽->오른쪽 이동시 피벗보다 크거나 같은것, 오른쪽->왼쪽으로 이동시 피벗보다 작은것을 찾았더니        10과 22인데 10이 더 작으므로 교환이 없습니다. 멈추고 10과 피벗인 15를 교환해줍니다.        8_3. 15이후로 정렬이 되었으므로 10~7까지 퀵정렬을 해줍니다.       8_4. 10을 피봇으로 잡고 찾기!   8_5. 10을 기준으로 1과 7 모두 정렬되있기 때문에 10과 7 교환.   8_6. 7을 피벗으로 잡으면 왼쪽 1에서 7보다 크거나 작은 원소가 없고, 오른쪽 1에서 7보다 작은 원소가 찾아졌으므로 7과 교환     요기까지 왼쪽 정렬 완료입니다.     9. 오른쪽 정렬로 돌아가 45~50까지 퀵정렬을 해줍니다. 방법은 8번과 같습니다.   이런식으로 정렬한 것이 퀵 정렬입니다.

 

 

 

퀵정렬 코드

#include "stdafx.h" #include <iostream> using namespace std;   const int ARRAY_MAX = 15; int iArray[ARRAY_MAX] = {30, 50, 7, 40, 88, 15, 45, 52, 22, 33, 77, 99, 10, 60, 1}; void QuickSort(int* _pArr, int _n); int Partition(int* _pArr, int _n);   void QuickSort(int* _pArr, int _n) {            if( _n <= 1 )                      return;            int iPivot = Partition(_pArr, _n);              QuickSort( &(_pArr[0]), iPivot);                             // 0번째 원소부터 iPivot-1까지            QuickSort( &(_pArr[iPivot+1]), _n - iPivot - 1);         // iPivot+1부터 _n-1까지   } int Partition(int* _pArr, int _n) {            int i = 1;            int j = _n-1;                       if( _n == 2 )     // 두 개만 남았을 경우 크기 비교한 후 정렬해주고 return            {                      if( _pArr[1] < _pArr[0] )                      {                                 int iTemp = 0;                                 iTemp = _pArr[0];                                 _pArr[0] = _pArr[1];                                 _pArr[1] = iTemp;                      }                      return 0;            }              while(i < j)            {                      // 왼->오른쪽으로 갈 때 피벗보다 값이 작으면                       // 그다음 원소로 넘어가 찾을때까지 while문 돌리기                      while(_pArr[i] < _pArr[0] && i < _n)                                         i++;                      while(_pArr[j] >= _pArr[0] && j > 0)                                 j--;                        if( i < j )     // 아직은 양쪽의 위치가 서로 넘어가질 않았음                      {                                 // _pArr[i], _pArr[j] 교환                                 int iTemp = 0;                                 iTemp = _pArr[i];                                 _pArr[i] = _pArr[j];                                 _pArr[j] = iTemp;                      }                      else                      {                                 // _pArr[0], _pArr[j] 교환, 피벗과 j교체->j가 이제 피벗                                 int iTemp = 0;                                 iTemp = _pArr[0];                                 _pArr[0] = _pArr[j];                                 _pArr[j] = iTemp;                      }            }              return j; }   int _tmain(int argc, _TCHAR* argv[]) {            QuickSort(iArray, ARRAY_MAX);              for( int i = 0; i < ARRAY_MAX; ++i)            {                      cout << iArray[i] << endl;            }            return 0; }

 

 

 

 

퀵정렬 성능

한번의 분할과 두 번의 재귀호출로 구성되고 배열의 분할은 배열의 크기에 비례하는데요.

재귀 호출 시 배열의 크기가 절반으로 줄어든다면 재귀호출의 깊이는 logn번이 되고,

배열의 크기가 1씩 줄어든다면 재귀호출의 깊이는 n번이 됩니다.

 

전체 수행시간

최선 : O(nlogn)

최악 : O()