BOJ 백준 1427 : 소트인사이드

시작하면서

이번 문제는 퀵 소트 카테고리 문제이다. 이번 문제는 PS보다 퀵 소트 구현을 다시 해보고자 풀어본다.

BOJ 1427 - 소트인사이드

​

개념

퀵 정렬(Quicksort)는 찰스 앤터니 리처도 호어가 개발한 정렬 알고리즘이다. 다른 원소와 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n^2)번의 비교를 수행하고, 평균적으로 O(nlogn)번의 비교를 수행한다.

퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높아지기 때문이다), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.

또한, 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(nlogn)알고리즘에 비해 훨씬 빠르게 동작한다. 그리고 퀵 정렬을 정렬을 위해 O(logn)만큼의 memory를 필요로 한다.

​

구현

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

1. 리스트에서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

​

문제 이해

해당 문제는 이해할 내용이 어렵지 않다. 수를 받아서, 해당 숫자 자릿수들을 내림차순으로 정렬해서 출력하면 된다.

​

문제 아이디어

input은 string으로 받고, 해당 string을 int 배열로 변경해서 문제를 풀고자 한다.

​

해결

#include <iostream>
#include <string>

using namespace std;

string Input();
void MakeArray(string input,int *arr, int *size);
void Swap(int *a, int *b);
void QuickSort(int *arr, int start, int end);
void PrintAnswer(int *arr, int size);

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);

	string input = "";
	int arr[10] = { 0, };
	int size = 0;

	input = Input();
	MakeArray(input, arr, &size);
	QuickSort(arr, 0, size - 1);
	PrintAnswer(arr, size);
}

string Input()
{	
	string input;

	cin >> input;

	return input;
}

void MakeArray(string input, int *arr, int *size)
{
	*size = input.size();
	for (int i = 0; i < input.size(); i++)
	{
		arr[i] = input[i] - '0';
	}
}


void Swap(int *a, int *b)
{
	int c;

	c = *a;
	*a = *b;
	*b = c;
}

void QuickSort(int *arr, int start, int end)
{
	if (start >= end)
	{
		return;
	}

	int pivot = start;
	int left  = start + 1;
	int right = end;

	while (left <= right)
	{
		while (left <= end && arr[left] >= arr[pivot])
		{
			left++;
		}

		while (right > start && arr[right] <= arr[pivot])
		{
			right--;
		}

		if (left > right)
		{
			Swap(&arr[pivot], &arr[right]);
		}
		else
		{
			Swap(&arr[left], &arr[right]);
		}
	}

	QuickSort(arr, start, right - 1);
	QuickSort(arr, right + 1, end);
}

void PrintAnswer(int *arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		cout << arr[i];
	}
}

퀵 정렬을 만들 때 주의해야할 점은, 중복된 값이 있을 때 처리해주어야 한다.

...
		while (left <= end && arr[left] >= arr[pivot])
		{
			left++;
		}

		while (right > start && arr[right] <= arr[pivot])
		{
			right--;
		}
...

해당 코드에서 left, right와 pivot의 값을 비교할 때 값이 같을 경우를 넣어주지 않으면 비교가 불가능한 경우가 생겨서 시간초과가 발생한다. 주의해야한다.

​

​

마치며

퀵 정렬은 취업 준비할 때 필수였기 때문에 여러번 만들고 공부했던 부분이었다. 하지만 오랜만에 코드로 다시 짜보니, 머리에 지식은 있어도 예외 처리가 잘 되지 않았다. 복습하기 참 잘했다고 생각한다.