퀵 정렬 구현 및 테스트

  퀵 정렬 

가장 끝 원소를 기준으로 그보다 작은 원소를 왼쪽에 큰 원소를 오른쪽으로 옮겨 정렬한다.

 

퀵 정렬 알고리즘

끝 원소를 기준으로 작은 원소를 좌측에 큰 원소를 우측으로 옮기고 좌측 배열과 우측 배열에 대해 같은 과정을 반복한다.

 

퀵 정렬 알고리즘

QuickSort(A[], p, r)
{
    if (p < r) then
    {
        q ← Partition(A, p, r)
        QuickSort(A, p, q - 1)
        QuickSort(A, q + 1, r)
    }
}

Partition(A[], q, r)
{
    배열 A[p...r]의 원소들을 A[r]을 기준으로 양쪽으로 재배치하고
    A[r]이 자리한 위치를 리턴한다.
}

 

※ 퀵 정렬의 시간 복잡도는 모든 원소들이 한쪽으로 몰리는 최악의 경우 Ο(n²), 평균적으로 Ο(nlogn)이 된다.

 

퀵 정렬 구현

배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다.

 

QuickSort.hpp

#pragma once
#include "../Common.h"

void QuickSort(int arr[], int p, int r, bool printData = false, int n = 0);
int Partition(int arr[], int p, int r);

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="printData">중간 결과 출력 여부</param>
void QuickSort(int arr[], int n, bool printData = false)
{
	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	QuickSort(arr, 0, n - 1, printData, n);
}

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
/// <param name="printData">중간 결과 출력 여부</param>
/// <param name="n">배열의 길이</param>
void QuickSort(int arr[], int p, int r, bool printData, int n)
{
	if (r - p < 1)
	{
		return;
	}

	int q{ Partition(arr, p, r) };

	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	QuickSort(arr, p, q - 1, printData, n);
	QuickSort(arr, q + 1, r, printData, n);
}

/// <summary>
/// 주어진 배열들을 병합한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="p">배열의 시작 인덱스</param>
/// <param name="r">배열의 끝 인덱스</param>
int Partition(int arr[], int p, int r)
{
	int i{ p }, j{ p };
	while (i < r && j < r)
	{
		if (arr[j++] < arr[r])
		{
			Common::Swap(arr, i, j - 1);
			i++;
		}
	}
	Common::Swap(arr, i, r);

	return i;
}

 

arr = [ 10, 8, 6, 4, 2, 9, 7, 5, 3, 1 ], n = 10 을 입력하여 실행한 과정은 다음과 같다.

2 4 6 8 10 9 7 5 3 1
1 4 6 8 10 9 7 5 3 2
1 2 6 8 10 9 7 5 3 4
1 2 3 4 10 9 7 5 6 8
1 2 3 4 7 5 6 8 10 9
1 2 3 4 5 6 7 8 10 9
1 2 3 4 5 6 7 8 9 10

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 0s ( 98ms )

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘