버블정렬

버블정렬:

오름차순이 기준일 때, 인접한 원소를 비교하여 큰 수를 뒤로 보내는 것을 반복하는 정렬

 

1) 원리

• 선택정렬과 달리 버블정렬은 정렬이 완료 된 것(bar 오른쪽)과 아닌 것(bar 왼 쪽)을 나누는 기준인 bar가 시작할 때 맨 뒤에 있다고 생각합니다.
• 그리고 나서 앞에서 부터 자신의 옆의 원소 (첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소, 세 번째와 네 번째 ..) 를 비교하며
• bar가 있는 곳 까지 정렬기준에 맞게 자리를 바꿔주면서 큰 것을 뒤로 보내는 정렬을 해나갑니다.
• 이렇게 앞에서 부터 비교하면서 최대값을 계속 뒤로 밀고 있으므로 한 loop를 돌고 나면 (오름차순 일 때) 최대값이 맨 뒤로 가게 됩니다.
• 이렇게 이렇게 원소 하나의 자리를 찾아 주었다면 bar를 한 칸 앞으로 이동시킵니다.
• 전체 loop가 끝나고 나면 정렬이 완료됩니다.

2) 구현

1. n개의 원소가 있다면 n번 아래의 과정을 반복합니다. 그러면 bar가 있는 맨 뒤에 최대값이 위치하게 됩니다.
2. 맨 앞에서부터 자신 옆의 원소값과 비교하면서 정렬기준에 따라 값을 서로 바꿔줍니다.
3. 맨 뒤에 최대값이 위치하면 그 다음 2과정이 끝나는 지점은 한 칸 앞이 됩니다.

#include <stdio.h>

int main(){
	//버블정렬의 구현 
	/* 10(입력) 개의 숫자를 정렬
	1 5 6 8 3 4 5 9 2 10 (입력)을 선택 정렬하면
	1 2 3 4 5 5 6 8 9 10 을 출력
	*/
	int n;
	int data[100];//정렬해야할 원소들이 들어갈 배열 선언
	
	scanf("%d", n);
	for(int i=0; i<n; i++){
		scanf("%d", &data[i]);
	}//정렬해야 할 원소 개수와 원소들 입력받기
	
	//본격적인 버블정렬 시작
   	//배열의 첫 번째 요소(element)와 두 번째 요소를 비교함으로써 시작합니다.
 	//첫 번째 요소가 두 번째 요소보다 크면, 두 요소의 위치를 바꿉니다. (swap)
 	//이후 두 번째 요소와 세 번째 요소를 비교하고, 이를 마지막까지 반복합니다.
 	//위와 같은 방식을 통해서 가장 큰 요소가 가장 마지막으로 밀려납니다.
	for(int i=0; i<n; i++){//n번 반복하겠다. 
		//j를 뒤로 하나씩 밀면서 j와 j+1의 크기를 비교합니다. 
		// 주의!! j 범위는 0~n-i-2가 되어야 합니다. 
		for(int j=0; j<n-i-1; j++){
			if(data[j] > data[j+1]){
				int temp;
				temp = data[j];
				data[j] = data[j+1];
				data[j+1] = temp;
			}
		}
	}
	// 버블정렬 끝

	//결과 출력
	for(int i=0; i<n; i++){
		printf("%d", data[i]);
	}
	printf("\n");
		
}

3) 시간 복잡도

1. 비교 횟수

   • 외부 loop는 n번
   • 내부 loop는 한 번 외부 loop를 마칠 때 마다 비교 대상이 하나씩 줄기 때문에 n-1, n-2, n-3,..., 2, 1 = n(n-1)/2

2. 데이터가 정렬될 때 이동하는 횟수

   • 주어진 데이터가 모두 역순으로 정렬되어 있어서 내부 loop 한 번 돌 때 마다 모두 교환해 주어야 한다면, 한 번 교환 시 3번의 이동이 필요하므로, 3*(n(n-1)/2)
   • 주어진 데이터가 이미 정렬되어 있는 상태라면 비교 후 한 번도 교환을 해주지 않아도 된다.

3. 시간복잡도

데이터의 개수가 n개라고 했을 때,

첫 번째 최대값 찾기 비교횟수 : 1 ~ n-1 => n-1

두번째 최대값 찾기 비교횟수 : 2 ~ n-1 => n-2

.

.

.

(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

이기때문에 O**(n2)만큼의 시간복잡도를 가집니다.

 

Reference

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

https://zeddios.tistory.com/20