[알고리즘] 버블 정렬 알고리즘

버블 정렬 알고리즘

첫번째 데이터와 두번째 데이터를 비교하고 두번째와 세번째 데이터를 비교하고 세번째와 네번째를 비교해 (중략) 1회전 반복이 끝나면 가장 큰 데이터가 맨 뒤로 가기 때문에 모든 반복을 돌고나면 오름차순 정렬이 되는 알고리즘이다.

 

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

 

첫번째 반복문에서 i는 0부터 n-1까지 반복한다. 두번째 반복문에서 j는 0부터 n-1-i까지 반복한다.

a[j]와 a[j+1]를 비교했을 때 a[j]가 크다면 이 둘을 swap해준다. 1회전이 끝나면 가장 큰 데이터가 맨 뒤로 가기 때문에 그 다음 회전은 끝에서 두번째 데이터까지만 반복하여 비교하면 된다. 그렇기에 j<n-1-j이다.

 

EX)

초기 상태 [ 21  34  4  54  29  17 ]인 데이터 배열로 반복문을 돌 때 마다 배열을 보자면

[ 21  4  34  29  17  54 ] 빨간 숫자는 정렬이 끝나 제외된 숫자

[ 4  21  17  29  34  54 ]

[ 4  17  21  29  34  54 ]  = 정렬 끝