자료의 정렬(1) - 버블, 선택, 삽입 정렬

 

버블 정렬(Bubble Sort)

인접한 원소 간 비교를 통해 교환하는 과정을 반복하는 정렬 방법입니다.

알고리즘 수행 과정에서 키값이 큰 원소가 점점 뒤로 가는 모습이 마치 거품이 점점 커지는 모습과 닮았다는 의미에서 붙여진 이름입니다.

직관적으로 이해할 수 있고 구현이 간단하지만 O(N^2)의 시간복잡도를 가지고 있습니다.

for(int i=1; i<=N; i++)
{
	for(int j=2; j<=N; j++)
 	{
		if(inp[j] < inp[j-1]) // swap
 		{
			tmp = inp[j];
			inp[j] = inp[j-1];
			inp[j-1] = tmp;
 		}
 	}
 }

 

선택 정렬(Selection Sort)

주어진 리스트의 원소 중에서 최솟값을 찾아 맨 앞에 위치한 값과 교체하는 과정을 반복하는 정렬 방법입니다.

리스트의 원소가 N개일 때 O(N^2)의 시간복잡도를 가지고 있습니다.

버블 정렬은 뒤쪽부터 정렬되었지만 선택 정렬은 앞쪽부터 정렬되는 특징을 가지고 있습니다.

for(int i=1; i<N; i++)
{
	min = i; // index
	for(int j=i+1; j<=N; j++)
 	{
		if(inp[j] < inp[min]) min = j;
 	}
	tmp = inp[i];
	inp[i] = inp[min];
	inp[min] = tmp;
}

삽입 정렬(Insertion sort)

주어진 리스트의 원소를 한 개씩 삽입하는 과정을 반복적으로 수행하는 정렬입니다.

카드를 번호 순으로 정렬할 때 이미 정렬된 카드에 새로운 카드를 끼워 넣는 연산을 시행하여

리스트의 앞쪽부터 정렬됩니다.

리스트의 원소를 앞에서부터 이미 정렬된 배열 부분과 비교하여 그 원소의 위치를 찾아 삽입하는 방식입니다.

리스트의 원소가 N개일 때 O(N^2)의 시간복잡도를 가집니다.

for(int i=2; i<=N; i++)
{
	int j = i;
	while(j > 1 && inp[j-1] > inp[j])
 	{
		tmp = inp[j];
		inp[j] = inp[j+1];
		inp[j+1] = tmp;
		j--;
 	}
 }