버블 정렬

 

다음 숫자들을 오름차순 정렬하시오

>1 10 5 8 7 6 4 3 2 9

 

 

버블정렬

옆에 있는 값과 비교하여 작은 수를 앞으로 보내는 정렬 방법을 버블 정렬이라고 한다.

구현은 가장 쉽지만 가장 비효율적이라 할 수 있다.

 

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int min,index,temp;
	int arr[10] = {1,10,5,8,7,6,4,3,2,9};
	for(int i=0; i<10; i++){
		for(int j=0; j<9-i; j++){
			if(arr[j+1]<arr[j]){
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	for(int i=0; i<10; i++)
		cout << arr[i] << ' ';
	return 0;
}

 

이또한 실행이 잘 되는 것을 알 수 있다.

사진 삭제

사진 설명을 입력하세요.

시간복잡도

버블 정렬의 시간복잡도는 O(N^2)이다.

 

버블 정렬은 선택 정렬과 비교하여 각 싸이클 마다 가장 큰 값이 뒤로 보내지게 된다.

컴퓨터 내부적인 연산이 가장 비효율적으로 일어나게 되어 수행시간이 가장 느린 안좋은 알고리즘이다. 시간복잡도는 선택 정렬과 동일하다.

 

한 싸이클에 숫자가 하나씩 제외되니 선택 정렬과 같은 원리이다.