퀵 정렬은 전형적인 분할 정복( Divide and Conquer) 알고리즘이다. 오름차순을 기준으로 피벗을 두고 왼쪽에는 작은값, 오른쪽에는 큰갑을 두어 나눈후에 나눠진 두 부분에 대해서도 똑같이 피벗을 두고.. 계속 나눠 더이상 나눌수없을때까지 나누다보면 정렬이 된다라는게 퀵정렬이다.
■ 구현
[QuickSort.h]
#pragma once
class QuickSort
{
public:
enum SORTOPTION { SORTOPTION_GREATER, SORTOPTION_LESS };
private:
int length = -1;
int* arr = nullptr;
SORTOPTION option = SORTOPTION_GREATER;
public:
QuickSort();
~QuickSort();
private:
void Swap(int* a, int * b);
void Sort_Inner(int left, int right);
int Partition_Greater(int left, int right);
int Partition_Less(int left, int right);
public:
void Sort(int* arr, const int& length, SORTOPTION option = SORTOPTION_GREATER);
};
|
[QucikSort.cpp]
#include "QuickSort.h"
QuickSort::QuickSort()
{
}
QuickSort::~QuickSort()
{
}
void QuickSort::Swap(int * a, int * b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void QuickSort::Sort_Inner(int left, int right)
{
if (left > right)
return;
int pivot = 0;
if (this->option == SORTOPTION_GREATER)
pivot = Partition_Greater(left, right);
else
pivot = Partition_Less(left, right);
Sort_Inner(left, pivot - 1);
Sort_Inner(pivot + 1, right);
}
int QuickSort::Partition_Greater(int left, int right)
{
int pivot = right + 1;
while (true)
{
if (this->arr[left] > this->arr[pivot])
{
while (left != right)
{
if (this->arr[right] < this->arr[pivot])
{
Swap(&this->arr[left], &this->arr[right]);
break;
}
right--;
}
}
if (left == right)
break;
left++;
}
if (this->arr[left] > this->arr[pivot])
{
Swap(&this->arr[left], &this->arr[pivot]);
}
return left;
}
int QuickSort::Partition_Less(int left, int right)
{
int pivot = right + 1;
while (true)
{
if (this->arr[left] < this->arr[pivot])
{
while (left != right)
{
if (this->arr[right] > this->arr[pivot])
{
Swap(&this->arr[left], &this->arr[right]);
break;
}
right--;
}
}
if (left == right)
break;
left++;
}
if (this->arr[left] < this->arr[pivot])
{
Swap(&this->arr[left], &this->arr[pivot]);
}
return left;
}
void QuickSort::Sort(int * arr, const int & length, SORTOPTION option)
{
if (arr == nullptr)
return;
this->arr = arr;
this->length = length;
this->option = option;
Sort_Inner(0, length-2);
}
|
딱히 설명할 코드는 아닌거 같다.. 오름차순 내림차순을 한 클래스에서 처리하다보니 조금 길어보일뿐 사실은 정말 짧다.
■ 실행
[Main.cpp]
#include <iostream>
#include "QuickSort.h"
using namespace std;
#define LENGTH 10
int main()
{
QuickSort quickSort;
int arr[LENGTH] = { 3, 4, 2, 1, 6, 7, 5, 8, 9, 0 };
quickSort.Sort(arr, LENGTH, QuickSort::SORTOPTION_GREATER);
for (int i = 0; i < LENGTH; ++i)
{
cout << arr[i] << ", ";
}
return 0;
}
|
■ 소스 코드
댓글 없음:
댓글 쓰기