Sandor의 개발 일지

Make real your dreams

2 분 소요

Description

퀵 정렬은 두 개로 분할하여 정렬을 하기 때문에 굉장히 빠르게 정렬을 수행 할 수 있다.
하지만 이미 정렬된 수의 경우 최악의 시간 복잡도를 가지게 된다.
시간 복잡도 = O(N*logN), 최악 = O(N^2) 이다.

pivot을 기준으로 왼쪽에서부터 큰 수 = 파랑을 찾고
오른쪽에서부터 작은 수 = 초록을 찾아 서로 교환한다.
엇갈릴 경우 작은 수 와 pivot을 서로 교환한다.

위 규칙을 두고 한번 수행해보자.

Desc1
우선 pivot 맨 좌측 부터 시작하여 숫자 2가 된다.
2보다 큰 값을 pivot 다음 수부터 찾아보면 5가 나온다.
작은 수는 맨 끝자리부터 찾아가보면 1이 나왔다.
그러면 5와 2의 자리를 서로 바꾼다.

Desc2
이번엔 큰 수 7과 작은 수 1이 나왔다.
서로간의 위치가 엇갈리다 혹은 교차하게 되었다.
그러면 작은 수의 위치와 pivot의 자리를 바꾼다.

Desc3
이제 2를 기준으로 좌측은 2보다 작은 수, 우측은 2보다 큰수로 분할이 되어진다.
이렇게 정상적으로 나뉘면 정렬이 잘 된것이다.
좌측과 우측을 나눠 계속해서 정렬을 실행한다.
좌측의 pivot은 1이다.

Desc4
원소가 한개만 존재하게되면 건너 뛰면된다.
그러므로 1이 정렬이 되어진다.
이제 우측정렬을 실행한다

Desc5
우측의 pivot은 7이고 큰수 8과 작은 수 6을 자리를 바꾼다.

Desc6
계속해서 pivot은 7이고 큰수 9와 작은 수 5의 자리를 바꾼다.

Desc7
pivot은 7이고 큰수 9와 작은 수 3이 엇갈려 pivot과 작은 수의 자리를 바꾼다.

Desc8
7은 정렬이 이루어 지고 좌측의 pivot 3과 우측의 pivot 9가 만들어진다.
항상 좌측 부터 실행한다.

Desc9
pivot은 3이고 큰 수 4와 작은 수는 찾지 못하여 자기 자신을 가리키게 된다.
그러면 엇갈리게 되어 혼자 자리를 바꾸게되어 3에 대한 정렬이 이루어진다.

Desc10
3의 기준으로 우측정렬이 실행이 되어 pivot은 4가 된다.
3때와 마찬가지로 4 혼자 자리를 바꾸고 정렬이 이루어 진다.

Desc11
4를 기준으로 우측 정렬이 실행이 되어 pivot은 6이 된다.
큰 수를 찾지 못하게 되어 5에서 멈추게 되고 작은 수 5와 겹치게 된다.
엇갈리는 조건과 동일시하여 작은 수 5와 6의 자리를 바꾼다.

Desc12
6의 정렬이 이루어지고 좌측정렬 한 개의 데이터인 5가 정렬이 될 것이다.

Desc13
이제 우측 정렬에서 pivot은 9이고 큰 수가 없어 8, 작은 수도 8이 된다.
엇갈리는 조건으로 실행되어 8과 9의 자리를 바꾸가 9는 정렬이 이루어 진다.

Desc14
이로써 모든 데이터가 정렬이 이루어 진다.

퀵 정렬은 처음에 정렬 방식이 이해하는데 오래 걸려 이렇게 끝까지 정렬되어지는 모습을 찍었다.
하고나면 코드도 간단한 편이고 크게 어려움은 없었다.

Cord

#include <iostream>

#define LENGTH 9 // 배열의 길이

using namespace std;

void quickSort(int* _data, int _start, int _end)
{
	// 원소가 1개 인 경우
	if (_start >= _end) { return; }

	int pivot = _start;
	int left = _start + 1;
	int right = _end;
	int temp;

	while (left <= right)
	{
		// pivot 보다 큰 수 찾기
		while (_data[pivot] > _data[left] && left < _end)
		{
			left++;
		}

		// pivot 보다 작은 수 찾기
		while (_data[pivot] < _data[right] && right > _start)
		{
			right--;
		}

		// 자리 교환
		if (left >= right)	// 엇갈렸을 때 또는 같을때
		{
			temp = _data[pivot];
			_data[pivot] = _data[right];
			_data[right] = temp;
		}
		else	// 엇갈리지 않았을때
		{
			temp = _data[left];
			_data[left] = _data[right];
			_data[right] = temp;
		}
	}
	quickSort(_data, _start, right - 1);	// 좌측 정렬
	quickSort(_data, right + 1, _end);	// 우측 정렬
}

int main()
{
    int dataArr[LENGTH] = { 2, 5, 7, 8, 4, 9, 3, 1, 6 };

	// 퀵 정렬 실행
	quickSort(dataArr, 0, LENGTH - 1);

	// 결과 출력
	string result;
	for (int idx = 0; idx < 9; idx++)
	{
		if (idx == 8)
		{
			result += dataArr[idx] + '0';
		}
		else
		{
			result += dataArr[idx] + '0';
			result += ", ";
		}
	}
	cout << "data = {" << result << " }";
	cout << "\n\n\n\n\n\n\n";
	return 0;
}

Result

Result

참고