[C/C++] 선택 정렬같은 버블 정렬 구현(선택정렬 + 버블정렬)

선택 정렬(selection sorting)은 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 정렬 방식으로 가장 작은 숫자와 가장 작은 숫자의 위치를 기억했다가 마지막 수까지 비교가 끝나면 마지막에 교환을 해줍니다.

 

버블 정렬(bubble sort)은 이웃한 데이터들을 비교하며 가장 큰 데이터를 가장 뒤로 보내는 정렬 방식으로 이웃한 데이터와 비교하여 계속해서 교환하는 방식입니다.

 

그런데 선택 정렬도아닌 버블 정렬도 아닌, 두 알고리즘을 합쳐서 구현한 알고리즘이 있습니다.

 

예를 들어 다음과 같이 1부터 10까지의 수를 무작위로 섞어놓은 배열이 있습니다.

값	5	6	10	4	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

선택 정렬의 경우 [0] 인덱스와 [1], [2], . . . [9] 인덱스까지 계속 비교를 하고 마지막에 교환을 합니다.

버블 정렬의 경우 [0] 인덱스와 [1] 비교 후 즉시 교환, 다시 [1] 인덱스와 [2] 비교 후 즉시 교환하는 방식입니다.

 

그러나 이 알고리즘의 경우 선택 정렬처럼 비교를 하면서 버블 정렬처럼 교환이 계속 일어납니다.

 

먼저 5와 6을 비교하였을 때 뒤에 있는 6이 더 큰 숫자이므로 교환이 일어나지 않습니다.

다음은 5과 10을 비교하였을때 뒤에 있는 10이 더 큰 숫자이므로 역시 교환이 일어나지 않습니다.

다음은 5과 4를 비교하였을때 앞에 있는 5가 더 큰 숫자이므로 두 숫자는 교환이 일어납니다.

 

값	4	6	10	5	3	8	7	1	2	9
위치	[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]

 

교환이 되면 [3] 인덱스까지 비교했으므로 계속해서 [0] 인덱스인 4와 [4] 인덱스인 3을 비교합니다.

 

즉, 비교는 선택 정렬처럼, 교환은 버블 정렬처럼 합니다.

 

이웃한 인덱스 끼리의 교환이 아니라서 선택 정렬 같기도 합니다. 하지만, 각 인덱스를 비교하여 값이 작은 것이 확인될 때마다 교환했기 때문에 정확히 따지면 버블 정렬이라고 할 수 있습니다.

 

#include <stdio.h>

int main(){
	//1~10 무작위 배열
	int arr[10] = {5, 6, 10, 4, 3, 8, 7, 1, 2, 9};
	int i, j, temp;
	
	for(i=0;i<9;++i){
		for(j=i+1;j<10;j++){
			//비교 후 바로 교환 
			if(arr[i]>arr[j]){
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
	
	//출력 
	for(i=0;i<10;++i){
		printf("%d ", arr[i]);
	}
	
	return 0;
}

 

결과값:

1 2 3 4 5 6 7 8 9 10

 

 

버블 정렬의 시간 복잡도(or 빅오)는 O(N^2)입니다.