2) 알고리즘 : 정렬 - 버블정렬(Bubble Sort)

버블 정렬

- 당장 옆에 값과 비교

- 1회차가 끝나면 가장 큰수가 가장 뒤에 정렬돼있다.

 

 

5 3 4 1 2 6

 

1회차

3 5 4 1 2 6

3 4 5 1 2 6

3 4 1 5 2 6

3 4 1 2 5 6

3 4 1 2 5 6

 

2회차 - 맨 뒤에 정렬된 6 제외한 나머지 앞 5개의 수만 비교

 

=> 6 + 5 + 4 + 3 + 2 + 1 (등차수열)

=> n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거)

=> n*n

=> 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가

 

시간복잡도 빅오 : O(N^2)

데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘

 

*시간복잡도는 선택정렬과 같지만, 실제 수행 시간은 버블정렬이 더 느리다.

매번 바로 옆의 값과 비교하며 스와핑을 해주기 때문!

 

 

#include <iostream>
#include <array>
using namespace std;

int main(void) {

	int array[6] = { 5,3,4,1,2,6 };
	int temp;
	for (int i = 0; i < 6; i++) {
		for(int j = 0; j < 5 - i; j++) { //맨 뒤의 값은 정렬되었기 때문에 - i로 빼준다
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;
			}
		}
	}

	for (int i = 0; i < 6; i++) {
		cout << array[i] << " ";
	}
	
	return 0;


}