Bubble Sorting(버블 정렬)

Posted by ITPangPang
2016. 4. 10. 22:08 기타/자료구조(자바)


버블 정렬란?


{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[] = {6104201};
        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[] = {6104201};
        
        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[] = {6104201};
        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[] = {6104201};
        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를 통한 버블정렬을 구현해보았습니다.

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

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

 

'기타 > 자료구조(자바)' 카테고리의 다른 글

Binary Search(이진탐색)  (0) 2016.04.10