Bubble Sorting(버블 정렬)

버블 정렬이란?

{6, 10, 4, 20, 1}

위의 배열을 오름차순으로 정렬 시키면 {1, 4, 6, 10, 20}, 

내림차순으로 정렬시키면 {20, 10, 6, 4, 1}이다

오름,내림차순으로 정렬시키기 위해서 사용하는 방법이 버블소팅으로 이웃한 숫자와 비교하여 뒤쪽으로 보내는 과정을 통하여 배열의 정렬을 완성시킨다

Bubble = 거품, 비눗방울이란 뜻으로 거품이나 비눗방울이 생기면 위로 점점 올라오는것(상승)이 배열을 비교하면서 뒤로넘기는 것 ex) array[0] <-> array[1]과 비슷하여 버블정렬이라 부릅니다

 

실제로 {6, 10, 4, 20, 1}을 오름차순으로 버블 정렬 해보면

이웃한 숫자와 비교하여 자리체인지가 없을때까지 진행한다

 

버블정렬(Java) 

① 배열생성

   배열을 생성한후 잘 들어갔나 확인해보겠습니다

public class Bubble

{    

    public static void main(String[] args)

    {

        int i;

        int array[] = {6, 10, 4, 20, 1};

        for(i=0;i<=array.length-1;i++)

        {

            System.out.print("array["+i+"]="+ array[i]+" ");

        }

    }

}

 

 

 ② for문을 돌리기전 어떻게 구현할지 테스트로 작업해본다(6, 10, 4 한번씩 비교)

     첫번째 : array[0]과 array[1]를 비교하여 array[0]이 array[1]보다 크면 array[0]과 array[1] 체인지(temp사용)

                (6과 10을 비교했을때 6이 작으므로 체인지가 일어나지 않는다)

 

     두번째 : array[1]과 array[2]를 비교하여 array[1]이 array[2]보다 크면 array[1]과 array[2] 체인지(temp사용)

                (10과 4를 비교했을때 10이 크므로 체인지가 일어난다)

                     1)temp에 10을 저장한다

                     2)array[2]의값 4를 array[1]에 저장한다

                     3)temp의 값 10을 array[2]에 저장한다

public class Bubble

{    

    public static void main(String[] args)

    {

        int i;

        int temp;

        int array[] = {6, 10, 4, 20, 1};

        

        if(array[0]>array[1])

        {

            temp = array[0];

            array[0]=array[1];

            array[1]=temp;

        }

        

        for(i=0;i<=array.length-1;i++)

        {

            System.out.print("array["+i+"]="+ array[i]+" ");

        }

        

        System.out.println("");

        

        if(array[1]>array[2])

        {

            temp = array[1];

            array[1]=array[2];

            array[2]=temp;

        }

        

        

        for(i=0;i<=array.length-1;i++)

        {

            System.out.print("array["+i+"]="+ array[i]+" ");

        }

 

    }

}

 

③ for문을 통한 1회전 실행

   위에서 하나하나 테스트 해본것을 그대로 for문에 넣어서 돌려봅니다

public class Bubble

{    

    public static void main(String[] args)

    {

        int i;

        int j;

        int temp;

        int array[] = {6, 10, 4, 20, 1};

        for(i=0;i<=array.length-2;i++)

        {

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

            {

                temp = array[i];

                array[i]=array[i+1];

                array[i+1]=temp;

            }

        }

        

        System.out.println("1회전");

        

        for(j=0;j<=array.length-1;j++)

        {

            System.out.print("array["+j+"]="+ array[j]+" ");

        }

    }

}

for(;array.length-2;)인 이유는 array.length은 배열의 길이가 5인데 배열은 array[0] 1이 아닌 0부터 시작하므로 -1을 해주고

마지막 array[4]는 비교하지 않아도 되므로 -1을 한번더 해주어서 -2를 해줍니다

 

위의 수작업을 통한 1회전 한 결과의 그림과 비교하니 제대로 구현한 것을 알 수 있습니다(1회전후 = 6, 4, 10, 1, 20)

 

④ while문을 통한 무한루프 추가

    무한루프를 추가하는 이유는 정렬이 완료될때까지 무한으로 회전을 시켜야 하기 때문이다

    정렬이 완료된다는 뜻은 더이상의 체인지가 일어나지 않아야 한다.

    그렇다는건 체인지가 일어나지 않은 시점을 잡아서 break;를 통하여 무한루프에서 빠져나오면 된다

    이를 해결하기 위해서 if문에 boolean값을 하나 추가 하여 if문에 걸릴때만 false->true로 바꿔준다.

    그 이유는 무한루프도중 if문에 안걸린다는 이야기는 체인지가 없다는 뜻이기 때문이다

public class Bubble

{    

    public static void main(String[] args)

    {

        int array[] = {6, 10, 4, 20, 1};

        int i;

        int j = 0;

        int k;

        boolean isCheck = false;

        int temp;

 

        while(true)

        {

            j++;

            for(i=0;i<=array.length-2;i++)

            {

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

                {

                    temp = array[i];

                    array[i]=array[i+1];

                    array[i+1]=temp;

                    isCheck = true;

                }

            }

            

            if(isCheck==false)

            {

                break;

            }

            else

            {

                System.out.println(j+"회전");

                for(k=0;k<=array.length-1;k++)

                   {

                       System.out.print("array["+k+"]="+ array[k]+" ");

                       isCheck = false;

                   }

                System.out.println();

            }    

        }

    }

}

 

Java를 통한 버블정렬을 구현해보았습니다.

다른 사이트나 서적을 참고하시면 아마 훨씬 간단하고 정확한 소스들도 있을겁니다.

그러나 먼저 직접 생각하고 구현해본 후에 다른 완성된 소스와 비교하면서 공부한다면 더욱더 도움이 될 것 같습니다.