2018년 7월 5일 목요일

퀵 정렬 ( Quick sort )

■ 설명

퀵 정렬은 전형적인 분할 정복( 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;
}

■ 소스 코드 

댓글 없음:

댓글 쓰기