버블 정렬(Bubble Sort)

소개

Bubble Sort는 인접한 두 수를 비교하여 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 

의 시간복잡도를 갖습니다. 다른 정렬 알고리즘에 비해 속도가 상당히 느린 편이지만, 코드가 단순하기 때문에 자주 사용됩니다.

 

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

1회전
첫 번째 자료 7을 두 번째 자료 4와 비교하여 교환하고, 두 번째의 7과 세 번째의 5를 비교하여 교환하고, 세 번째의 7과 네 번째의 1을 비교하여 교환하고, 네 번째의 7과 다섯 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 네 번 비교한다. 그리고 가장 큰 자료가 맨 끝으로 이동하므로 다음 회전에서는 맨 끝에 있는 자료는 비교할 필요가 없다.
2회전
첫 번째의 4을 두 번째 5와 비교하여 교환하지 않고, 두 번째의 5와 세 번째의 1을 비교하여 교환하고, 세 번째의 5와 네 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 세 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 두 번째에 놓인다.
3회전
첫 번째의 4를 두 번째 1과 비교하여 교환하고, 두 번째의 4와 세 번째의 3을 비교하여 교환한다. 이 과정에서 자료를 두 번 비교한다. 비교한 자료 중 가장 큰 자료가 끝에서 세 번째에 놓인다.
4회전
첫 번째의 1과 두 번째의 3을 비교하여 교환하지 않는다.

 

소스코드

#include <iostream>
using namespace std;

void BubbleSort(int arr[], int max) {
	
	int n = max;
	for (int i = 0; i < n-1; i++) { //배열의 처음 부터 끝까지
		for (int j = 0; j < n-i-1; j++) { // 현재 배열 부터 끝가지 i개씩 줄어들면서 계속 for문
			if (arr[j] > arr[j + 1]) { //현재 값이랑 현재 다음값비교 현재값이 크면
				swap(arr[j], arr[j + 1]); // 둘이 위치 변경
			}
		}
	}
 }
int main() {
	int x[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
	int size2 = sizeof(x) / sizeof(x[0]);
	BubbleSort(x, size2);

	for (int i = 0; i < size2; i++) {
		cout << x[i] << " ";
	}

	return 0;
}

 

결과 값