정렬 알고리즘 - 버블,선택,삽입 O(N²)시간복잡도 - 10장

기본적으로 오름차순으로 정렬합니다. 

버블 정렬

모든 정렬 알고리즘중 매우 간단하고 이해하기 쉬운 정렬 알고리즘이다.

이해와 구현이 쉬운 만큼 성능에는 아쉬움이 존재한다.

 

버블 정렬의 과정

매번 옆의 요소와 비교를 하며 오름차순으로 정렬하고 있다. 

한번의 정렬과정에서 3241을 2314라는 정렬결과를 보여준 것.(정렬이 끝난것은 아님)

 

그림을 보면 알겠지만 한번 정렬이 완성된 상태에서 제일 큰 요소가 제일 뒤에 위치한다는것을 알 수 있다.

이렇듯 한번의 정렬에서 요소중 가장 큰 값을 뒤로 보낸다는 특징이 존재한다. 

 

간단하니 바로 코드를 통해 확인한다.

template <typename T>
class Sort
{
public:
	static void BubbleSort(T* ptr, int len);
};

template <typename T>
void Sort<T>::BubbleSort(T* ptr, int len)
{
	int i, j;
	int temp;

	for (i = 0; i < len - 1; ++i)
	{
		for (j = 0; j < len - 1 - i; ++j) // 맨 뒤요소는 한번정렬때마다 하나씩 정렬이되므로.
		{
			if (ptr[j] > ptr[j + 1])
			{
				temp = ptr[j];
				ptr[j] = ptr[j + 1];
				ptr[j + 1] = temp;
			}
		}
	}
}

코드는 간단하다. 두번째 반복문에서 j < len - 1 - i 의 경우. 위 그림에서 한번의 정렬때 제일 큰 값이 맨 뒤로 보내진다는 버블정렬의 특징이기에 코드가 저런 것.

 

버블 정렬의 성능평가 : O(N²)

선택 정렬

선택 정렬은 정렬의 기준(오름차순,내림차순)에 맞게 가장 부합한 요소를 하나 선택해서 옮기는 정렬이다.

위 그림에서는 별도의 정렬 결과라는 정렬 대상과 같은 크기의 임시 메모리가 필요해보이지만

저런 방식보다는 더 간단한 방법이 있다.

이렇게. 요소하나를 선택해 제일 앞으로 보내고 원래 자리에 있던 요소와 자리를 교체하면 된다.

 

즉

 

"정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 그 자리에 있던 데이터는 빈자리에 가져다 놓음"

 

어떻게 보면 버블정렬에서 한번의 정렬마다 맨 뒤로 보내는것과 비슷하다. 선택정렬은 맨 앞으로 보내는 과정.

 

코드를 통해 확인해본다.

template <typename T>
void Sort<T>::SelectionSort(T* ptr, int len)
{
	int i, j;
	int temp, minIdx;

	for (i = 0; i < len - 1; ++i) 
	{
		minIdx = i;
		for (j = i + 1; j < len; ++j) // 맨앞은 정렬되었으므로. i + 1.
		{
			if (ptr[j] < ptr[minIdx]) // 최소값 찾는 과정.
				minIdx = j;
		}

		temp = ptr[i];
		ptr[i] = ptr[minIdx];
		ptr[minIdx] = temp;
	}

}

 

버블정렬은 맨 뒤는 한번의 정렬때마다 정렬이 되었으므로 len - 1 - i까지 반복을 하였고.

선택정렬은 맨 앞이 한번의 정렬때마다 정렬이 되므로 j = i + 1부터 시작하는 것.

 

선택정렬의 성능 평가 : O(N²)

삽입 정렬

삽입 정렬은 요소를 앞에 보낸다는 과정에서 선택정렬과 비슷해보이지만 정확히는 다르다.

삽입 정렬은 요소 하나를 선택하고 내 앞에 요소들이 정렬이 되어있다는 가정하에 원소를 비교해가며

내가 들어갈 자리를 찾는 과정이다.

 

이렇듯. 요소하나를 선택해 앞의 요소들(정렬이 되어있다고 가정)과 원소를 비교해가며 자기자리를 찾는다.

 

내앞의 요소들과 비교를 하면서 요소가 나보다 크다면 뒤로. 작다면 비교를 멈추고 교환. (정렬완료 영역)

 

코드를 통해 확인해본다.

template <typename T>
void Sort<T>::InsertionSort(T* ptr, int len)
{
	int i, j;
	int tmpData;
	for (i = 1; i < len; ++i)
	{
		tmpData = ptr[i];
		for (j = i - 1; j >= 0; --j)
		{
			if (ptr[j] > tmpData) // 비교대상 한칸 뒤로 밀기.
				ptr[j + 1] = ptr[j]; // 교환.
			else
				break;
		}
		ptr[j + 1] = tmpData;
	}
}

 

 

중요한것은 바깥 반복문이 i가 1부터돈다는 것.

그 이유가 정렬된 영역과 정렬의 대상과의 요소 비교를 위한 것.

j를 보면 i - 1. 즉 내 앞에 요소부터 0인덱스 맨앞까지 계속해서 비교한다는 것을 알 수 있다.

 

예로들어 3 4 2 1이라는 데이터를 대상으로 처음 정렬한다고 하면 tmpData는 4가.

안쪽 반복문의 ptr[j]는 3이 된다. 비교했을때 더 크지않으므로 break.

 

ptr[j + 1]은 4. tmpData는 4. 그대로 값이 대입된다.

 

삽입 정렬의 성능 평가 : O(N²)

 

삽입 정렬의 경우에는 대부분이 이미 정렬되어 있는 경우는 빠르게 동작한다.

(앞의 요소와 비교할때 참이 아니라면 바로 break하므로.)

하지만 최악의 경우에는 매번 앞의 요소를 끝까지 비교해야하므로 O(N²)