버블정렬 알고리즘 개선하기

기본 버전

#define swap(type,x,y) do{type t = x; x = y; y = t;} while(0)

void buuble(int a[],int n)
{
    for (int i = 0; i < n - 1; i++){
        for (int j = n - 1; j > i; j--)
            if (a[j - 1] > a[j]) 
                swap(int, a[j - 1], a[j]);
    }
}

기본버전은 요소-1만큼 반복문이 돌아가며 한번의 반복이 끝나 i가 1이 늘어나면,

확정 된 0번 인덱스의 자리를 제외하고(j > i까지이기 때문) 나머지 자리에서의 비교,교환이 계속 이루어진다.

 

다시 얘기하면 뒤에 값들이 정렬이 되어있는 상태라도 계속 비교 교환을 한다는 얘기다.

 

알고리즘 개선 - 1

#define swap(type,x,y) do{type t = x; x = y; y = t;} while(0)

void buuble(int a[],int n)
{
    for (int i = 0; i < n - 1; i++) {
        int ExChange = 0;

        for (int j = n - 1; j > i; j--)
        {
            if (a[j - 1] > a[j]) {
                swap(int, a[j - 1], a[j]);
                ExChange++;
            }
        }

        if (ExChange == 0) break;
    }
}

{1,3,6,4,7,8,9}라는 배열이 있다고 해보자.

i가 0일때 한번 정렬을 하고나면 4가 앞쪽으로 정렬되면서 {1,3,4,6,7,8,9} 로 정렬이 완성된다.

 

하지만 기본버전은 코드상 i가 1이되면 확정이 된 자리는 0번 인덱스 뿐이기 때문에,

두번째 반복문은 요소의 끝부터 i+1 인덱스까지 비교하며 계속 돌아간다.

 

이것을 개선하기위해 두번째 for문에 들어가기 전에 Exchange라는 변수에 0을 대입해준다.

두번째 for문 안에서 swap이 이루어지면 Exchange 변수를 1늘려준다.

 

만약 두번째 for문을 돌면서 교환이 한번도 이루어지지 않았다는 이야기는 뒤의 숫자들이 다 정렬을 마친 상태라는 뜻이기 때문에 반복문을 빠져나온다.

 

위의 예시에서 i가 1일때까지는 반복문이 돌지만 교환은 한번도 이루어지지 않기 때문에 

i가 2까지 증가하지 않고 그대로 반복문을 빠져나온다. 

 

알고리즘 개선 - 2

#define swap(type,x,y) do{type t = x; x = y; y = t;} while(0)

void buuble(int a[],int n)
{
    int k = 0;
    while (k < n - 1)
    {
        int last = n - 1;
        for (int j = n - 1; j > k; j--)
        {
            if (a[j - 1] > a[j])
            {
                swap(int, a[j - 1], a[j]);
                last = j;
            }
        }
        k = last;
    }
}

 

알고리즘 개선 - 1의 코드는 정렬이 끝났다면 for문을 탈출하는 코드였다.

하지만 뒤에 정렬 할 요소들이 남아있다면 개선 전의 알고리즘과 똑같이 끝까지 돌며 검사를 했다.

 

이번 알고리즘은 굳이 다 검사하지 않아도 자리가 확정된 위치를 알려줌으로서 루프를 조금 덜 돌게한다.

 

개선-1과 비슷한 구조인데, k가 요소 -1보다 작을때까지 루프를 돈다.

 

두번째 for문이 시작하기전에 last에 n-1을 넣어준다.

스왑이 일어나면 last에 스왑이 일어난 인덱스가 들어가고

두번째 for문이 끝나면 k에 last(스왑이 일어난 인덱스)가 들어간다.

 

두번째 for문의 조건은 j가 k보다 클때까지 돌기 때문에

만약 3번 인덱스에서 스왑이 일어나고 2,1,0번 인덱스에서는 스왑이 일어나지 않았다면

k에  3번 인덱스가 들어가기 때문에  다음 루프를 돌때 0,1,2번을 검사하지 않는것이다.

 

그리고 시작할때 last에 n-1을 넣어주기때문에 만약 교환이 한번도 일어나지 않는다면

(k == n-1)이 되기 때문에  while문이 끝이난다.

 

허접한 그림으로 그려보면 이렇다.