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

정렬(sorting)

핵심 항목(key)의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

정렬 알고리즘을 통해 데이터를 정렬하면 검색에 용이

정렬 알고리즘의 핵심 요소는 교환, 선택, 삽입

 

버블 정렬(bubble sort)

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복

비교와 교환 작업을 패스라고 표현

어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 의미

 

bubble sort version2 에서는 각각의 패스에서 비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태이기에, 다음 패스에서 수행할 범위를 제한해 줄 수 있다. 

■ 버블 정렬 프로그램

import java.util.Arrays;

public class BubbleSort {

    public static void bubbleSort(int[] a){
        for(int i=0; i<a.length; i++){
            int exchg = 0 ;
            //패스
            for(int j=(a.length-1) ; j > i ; j--){
                if(a[j-1] > a[j]){
                    swap(a, j, j-1);
                    exchg++;
                }
                if(exchg == 0)  //더 이상의 교환이 이루어지지 않으니 종료
                    break;
            }
        }
    }

    //bubbleSort를 개선한 버전
    public static void bubbleSortV2(int[] a){
        int k = 0;   //a[k]의 앞 쪽 정렬은 끝난 상황

        int n = a.length;
        while(k < n-1){
            int last = n-1;     //마지막 요소를 교환한 위치
            for(int j=n-1; j > k; j--){
                if(a[j-1] > a[j]){
                    swap(a, j, j-1);
                    last = j;
                }
            }   //패스
            k = last;   //다음 패스에서 수행할 범위를 줄여준다.
        }
    }

    public static void swap(int[] a, int idx1, int idx2){
        int tmp = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = tmp;
    }

    public static void main(String[] args) {
        int[] x = {22, 5, 11, 32, 120, 68, 70};
        int[] x2 = {1, 3, 9, 4, 7, 8, 6, 10};
        bubbleSort(x);
        bubbleSortV2(x2);
        System.out.println("bubble sort : " + Arrays.toString(x));
        System.out.println("bubble sort version 2 : " + Arrays.toString(x2));
    }
}