[알고리즘]버블 정렬

이번에도 기초적인 것으로 버블 정렬이다.

우선 소스를 보면

bubbleSort(int array[], int arrayNum)

{

for(int i = arrayNum - 2; i >=0; --i)

{

for(int j = 0; j <= i; ++j)

{

if(array[j] > array[j+1])

{

array[j] += array[j+1];

array[j+1] = array[j] - array[j+1];

array[j] = array[j] - array[j+1];

}

}

}

}

알고리즘을 설명하면

버블 정렬은 배열의 끝으로 최대값을 보내고

최대값이 들어간 부분은 제외하고 다시 최대값을 끝으로

보내는 것을 반복하는 것이다.

예를 들면,

4 10 3 6 2 라는 배열이 주어진다면

4& 10 3 6 2 // 초기값

// &앞과 뒤의 값을 비교해서 큰 수를 뒤로보냄

4 10& 3 6 2 // 먼저 나온 for문의 첫번째 루프

4 3 10& 6 2

4 3 6 10& 2

4 &3 6 2 *10 // 별표 이후는 고정값

3 4 &6 2 *10 // 두번째 루프

3 4 6 &2 *10

3 &4 2 *6 10

3 4 &2 *6 10 // 세번째 루프

3 &2 *4 6 10

2 *3 4 6 10 // 네번재 루프

이번에는 예가 긴데, 버블정렬은 삽입정렬과는 달리 항상 n(n-1)/2

번의 연산을 해야하기 때문이다.

버블정렬은 가장 큰 수가 맨 뒤로 가는 구조로 마치 물방울이 떠오르는 것처럼 보여서 '버블' 정렬이라고 부른다