[정렬 알고리즘] 버블정렬

🏆 목차.

1. 버블정렬이란?
2. 버블정렬 코드
3. 결론

 

🛒 버블정렬이란?

 

버블정렬(Bubble Sort)은 모든 정렬 알고리즘 중 가장 비효율적인 정렬 방법입니다.

하나의 숫자와 바로 뒤에 숫자를 비교한 뒤, 앞의 숫자가 작다면 둘의 위치를 바꾸며 정렬을 반복합니다.

 

그림으로 설명하자면 다음과 같습니다.

 

버블정렬 그림설명

 

버블정렬은 두 값을 비교해서 큰 값을 뒤로 보냅니다.

배열에 4 5 3 7 8 1 9 2 10 6이라는 원소가 있다면 첫 번째 패스에서 다음과 같은 과정을 거칩니다.

 

4와 5를 비교, 교환 없음.
5와 3을 비교, 5와 3 교환.
5와 7을 비교, 교환 없음.
7과 8을 비교, 교환 없음.
8과 1을 비교, 8과 1 교환.
8과 9를 비교, 교환 없음.
9와 2를 비교, 9와 2 교환.
9와 10을 비교, 교환 없음.
10과 6을 비교, 10과 6 교환

 

결과적으로 첫 번째 패스에서 10이 가장 뒤로 가게 됩니다.

 

🎨 버블정렬 코드

 

#include <iostream>

using namespace std;


int main() {
	
	int n[10] = {4,5,3,7,8,1,9,2,6,10};
	
	int temp;
	for(int i = 0 ; i < 10 ;i++)
	{
		for(int j = 0 ; j< 9-i;j++)
		{
			if(n[j] > n[j+1])
			{
				temp = n[j];
				n[j] = n[j+1];
				n[j+1] = temp;
			}
		}
	
	}
	for(int i = 0 ; i < 10 ; i++)
	{
		cout<<n[i]<<" ";
	}

}

 

위 코드의 핵심은 반복문입니다.

	for(int j = 0 ; j< 9-i;j++)

 

다음과 같이 9-i를 한 이유는 한 번의 패스가 끝나면 정렬이 되지 않은 값 중 가장 큰 값이 뒤로 가기 때문에 다시 검사할 필요가 없기 때문입니다.

 

	temp = n[j];
	n[j] = n[j+1];
	n[j+1] = temp;

 

해당 코드를 통해 원소를 교환할 수 있습니다.

 

🎯 결론

 

버블정렬이 모든 정렬 알고리즘 중 제일 비효율적인 이유는 원소의 교환을 매번 반복하기 때문입니다.

선택정렬의 경우 원소의 교환은 반복문이 끝나고 한번 진행됩니다.

하지만 버블정렬의 경우 매번 교환이 되기 때문에 선택정렬보다 더 비효율적인 정렬알고리즘입니다.

두 번의 중첩된 반복문으로 인해 시간복잡도는 O(n^2)입니다.