퀵 정렬

거품, 힙 중에서 가장 빠른 알고리즘이다.

분할정복이라는 접근 방식을 이용해서 배열을 정렬하는 재귀적인 알고리즘이다.

 

1. 기준값 하나 선택

2. 그 기준값보다 작은 항목들을 배열의 왼쪽으로

3. 그 기준값보다 큰    항목들을 배열의 오른쪽으로

4. 왼쪽 부분 배열에 퀵 정렬을 재귀적으로 적용

5. 오른쪽 부분 배열에 퀵 정렬을 재귀적으로 적용

 

퀵정렬이 가장 효율적으로 작동하려면 두 부분배열들의 크기가 거의 비슷해야한다.

삼중앙 알고리즘을 쓰는데

첫 번째 중간 마지막 색인의 값들을 취해서 그 셋 중 가운데 값을 기준값으로 사용

 

11 10 16 4 8 12 1 6 0 20 2 9 5

이렇게 있을때 제일앞의 11 중간의 1 마지막의 5를 취하고 그중 가운데에 해당하는 5를 기준값으로 선정

기준값을 밖으로 뺀다

<5>              11 10 16 4 8 12 1 6 0 20 2 9 [ ]

그러면 빈칸이 하나 생기고 그 빈칸이 배열 제일 앞에 오게해야하니(제대로 작동되려면) 제일 앞의 11을 기준값이 있던 자리로 옮김

 

<5>              [ ] 10 16 4 8 12 1 6 0 20 2 9 11

여기까지가 퀵 정렬에 필요한 설정이 끝남

 

이렇게 배열을 설정하고 앞 뒤로 여러번 훑게 된다.

우선 뒤에서 시작한다했을때 기준값보다 작은 값을 발견하면 탐색을 멈추고 그 값과 빈칸을 바꾼다.

이제 다시 반대 방향으로 훑어나가다 기준값보다 큰 값을 만나면 탐색을 멈추고 그 값을 빈칸과 바꾼다.

이 과정을 계속 반복..그리고 마지막 빈칸을 만나면 그곳에 기준값(여기선 5를 넣는다)

 

<- 진행방향

<5>              [ ] 10 16 4 8 12 1 6 0 20 2 9 11

<5>              2 10 16 4 8 12 1 6 0 20 [ ] 9 11

-> 진행방향

<5>              2  [ ] 16 4 8 12 1 6 0 20 10 9 11

계속하다가 빈칸을 좌측이던 우측이던 만나면  빈칸에 기준값을 넣는다!

<5>              2  0 1 4 [ ] 12 8 6 16 20 10 9 11

                    2  0 1 4 5 12 8 6 16 20 10 9 11

그런 다음에 좌, 우  두 부분배열에 대해 각각 퀵정렬을 적용한다.

먼저 왼쪽 부분 배열에 퀵 정렬을 적용하면

2 0 1 4

첫번째 2 마지막 4 중간 0

기준값 2로 선정

<2> [ ] 0 1 4

 

<- 진행방향

<2> [ ] 0 1 4

<2>  1  0 [ ] 4

 

-> 진행방향

<2>  1  0 [ ] 4

빈칸 만났으니..

<2>  1  0 [ ] 4

        1  0 2 4

짠 정렬!

 

 

퀵 정렬 역시 최악의 경우 N^2이지만 상중앙 알고리즘 선택기법을 활용하면 O (n log2 n)

아래는 중간값을 얻기위한 함수

template
int FindMedianOfThree(Array& p_array, int p_first, int p_size, int(*p_compare)(Datatype, Datatype))
{
	int last = p_first + p_size - 1;
	int mid = p_first + (p_size / 2);

	if (p_compare(p_array[p_first], p_array[mid]) < 0 && p_compare(p_array[p_first], p_array[last] < 0))
	{
		if (p_compare(p_array[mid], p_array[last]) < 0)
		{
			return mid;
		}
		else
		{
			return last;
		}
	}
	if (p_compare(p_array[mid], p_array[p_first] < 0 && p_compare(p_array[mid], p_array[last]) < 0))
	{
		if (p_compare(p_array[p_first], p_array[last] < 0))
		{
			return p_first;
		}
		else
		{
			return last;
		}
	}
	if (p_compare(p_array[p_first], p_array[last]) < 0)
	{
		return p_first;
	}
	return mid;	
}

 

 

아래는 퀵 정렬 함수

template
void QuickSort(Array& p_array, int p_first, int p_size, int(*p_compare)(DataType, DataType))
{
 int pivot;
 int last = p_first + p_size - 1;
 int mid;
 int lower = p_first; //하한 색인 즉 왼쪽에서 오른쪽으로 탐색방향
 int higher = last; //상한 색인 즉 오른쪽에서 왼쪽으로 탐색방향

 if (p_size > 1)
 {
  mid = FindMedianOfThree(p_array, p_first, p_size, p_compare);
  pivot = p_array[mid];
  p_array[mid] = p_array[p_first];

  while (lower < higher)
  {
   //상한 색인에서 시작해서 앞쪽으로 칸들을 훑다가 기준값보다 작은 값을 발견하거나
   //하한 색인에 도달하면 멈춤다
   while (p_compare(pivot, p_array[higher]) < 0 && lower < higher)
    higher--; //찾는거에 따라 higher값이 내려간다 점점..나중에 거기서부터 시작하려고..

   if (higher != lower)
   {
    p_array[lower] = p_array[higher];
    lower++; //값을 넣고 증가, 어차피 증가안하면 그 값은 정렬된 값이라 재검색하면 불필요하잖아..
   }

   while (p_compare(pivot, p_array[lower])>0 && lower < higher)
    lower--; //이젠 반대로 간다

   if (higher != lower)
   {
    p_array[higher] = p_array[lower]; //higher에 넣어도 되는 이유가 위에서 이미 higher값은 lower로 옮겨갔다, 즉 빈칸
    higher--; 
   }
  }

  p_array[lower] = pivot; //왜 lower에 넣느냐 higher가 아니라 while의 조건자체가 lower < higher이니까

  //아래는 왼쪽도 또해야하고 오른쪽도 또해야하니까 재귀함수
  QuickSort(p_array, p_first, lower-p_first, p_compare);
  QuickSort(p_array, lower + 1, last - lower, p_compare);
 }
}