[알고리즘] 버블 정렬 (Bubble Sort) 알고리즘

정렬 알고리즘 중에

하나인 버블 정렬

입니다.

이번 포스팅 에서는

버블 정렬에 대해서

최대한 알기 쉽게

써보도록 하겠습니다.

버블 정렬이

왜 버블인지 약간

이해가 안됬는데..

아무래도 바닷속

공기 방울을

예로 들면

공기방울이 수면위로

점점 올라가듯이

가장 큰 값이

점점 올라가면서

정렬되는 과정과

비슷해서

이렇게 지은 것 같네요.

이처럼 버블 정렬은

순차적으로 비교하면서

큰 값이 점점 뒤로

정렬되는 알고리즘

입니다.

설명 하기에 앞서서

아래 그림처럼

색깔에 따라

보시면 됩니다.

계속 루프를 돌면서

순서대로 인접해 있는 값을

비교해 정렬을 시작합니다.

루프가 한번 끝나면

제일 큰 값이 제일 뒤로

가게 됩니다.

그럼 제일 큰 값을

고정 하고 이 값을 뺀

나머지 값들을 다시

반복해서 비교해

줍니다.

모든 루프를 돌면

아래 처럼 정렬이

완료 됩니다. 

소스코드로 표현하면

대략 아래같이

표현 됩니다.

void BubbleSort(int A[], int N) { bool Sorted = false; for (int Pass = 1; (Pass < N) && (!Sorted); ++Pass) { Sorted = true; for(int Current = 0; Current < N-Pass; ++Current) { if (A[Current] > A[Current+1]) { int Temp = A[Current]; A[Current] = A[Current+1]; A[Current+1] = Temp; Sorted = false; } } } }

참조

C.C++ 로

배우는 자료구조론

버를 정렬의

복잡도는

아래와 같습니다.

버블 정렬도

간단하기는 하지만

역시 효율적이지는

않습니다.

이상 버블 정렬

알고리즘 이었습니다.