버블정렬(Bubble Sort)

정렬알고리즘을 이해하는 가장 쉬운 방법은 시각적으로 보는 것이라 생각한다.

https://blog.kakaocdn.net/dn/wGAhf/btqCKhxBxE3/ZkmJci9sRF2ypGrMQWxfdk/img.gif

 

인접한 요소끼리 대소를 비교해서 큰값을 뒤로 작은값을 앞으로 보낸다고 생각하면 쉽다

위 그림처럼 인접한 요소를 비교해 큰값을 뒤로 보내다 보면 1회차 반복이 끝났을 때 최댓값이 가장 마지막 자리로 가게된다

시간 복잡도는 O(N^2)

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 6,9,8,1,3,4,2,5,7};
	int arrSize = sizeof(arr) / sizeof(int);
	int tmp;
	for (int i = 0; i < arrSize-1; i++) {
		for (int j = i + 1; j < arrSize; j++) {
			if (arr[i] > arr[j]) {
				tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}

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


}