정렬알고리즘(C++) / 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

버블 정렬 애니메이션 출처 -  https://cloudstudying.kr/lectures/395

 

버블정렬은 가장 쉽고 코드가 단순한 정렬 알고리즘이다. 두 값을 비교하여 정렬하며 이동한다. 

하지만 시간복잡도가 느려 실제로는 잘 사용되지 않는다.

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이란 이름이 붙여졌다. 

양방향으로 번갈아 수행하면 칵테일 정렬이다. 

 

시간 복잡도 & 공간 복잡도

• 시간 복잡도 : O(n^2)
• 공간 복잡도 : O(n) 

 

코드(C++) - 백준 2750

/2750 버블정렬
#include<iostream>
using namespace std;

int main() {
	//입력
	int N;
	cin >> N;
	int arr[1001];
	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		arr[i] = num;
	}

	for (int i = N - 1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
            	//swap
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}

		}
	}
    //출력
	for (int i = 0; i < N; i++) {
		cout << arr[i] << "\n";
	}

	return 0;
}

 

무작위 배열수의 버블 정렬

 

참고 - 위키 백과

https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

거품 정렬 - 위키백과, 우리 모두의 백과사전