버블정렬(Bubble Sort)

버블정렬(Bubble Sort)

원리는 매우 간단합니다.

다음과 같은 수열이 있다고 가정합니다.

3, 2, 4, 5, 1, 9, 10, 8, 6, 7

Step1. 

맨 우측의 6과 7일 비교하여 앞쪽의 수가 뒷쪽의 수보다 크면 위치를 바꾸어줍니다.

지금의 수열에서는 6이 더 작기 때문에 아무런 교환도 하지 않고 다음으로 넘어갑니다.

Step2.

다음은 8과 6을 비교하여 왼쪽의 수가 오른쪽보다 크면 위치를 바꾸어줍니다.

8은 6보다 크기 때문에 자리를 바꾸어줍니다.

결과는 아래와 같이 되었습니다.

3, 2, 4, 5, 1, 9, 10, 6, 8, 7

8과 6의 자리가 바뀌었습니다.

이 과정을 수열의 처음 끝까지 도달할때까지 반복합니다.

그렇게되면 1이 가장 처음에 위치하게 됩니다.

과정은 아래와 같습니다.

3 2 4 5 1 9 10 8 6 7

3 2 4 5 1 9 10 6 8 7

3 2 4 5 1 9 6 10 8 7

3 2 4 5 1 6 9 10 8 7

3 2 4 5 1 6 9 10 8 7

3 2 4 1 5 6 9 10 8 7

3 2 1 4 5 6 9 10 8 7

3 1 2 4 5 6 9 10 8 7

1 3 2 4 5 6 9 10 8 7

처음까지 한번 싸이클이 돌면 첫번째 수열은 정렬이 완료된 것으로 다시 맨 끝에서부터 비교 과정을 반복합니다.

이전과 동일하게 맨끝에서부터 앞 뒤 두개의 숫자를 비교하며 자리를 바꿔주는 과정을 반복하면 됩니다.

단 첫번째 숫자는 정렬이 완료되었기 때문에 두번째 수(3)까지 비교과정을 반복하면 됩니다.

다시 말하면 첫번째 숫자 1은 정렬이 완료된 상태이기 때문에 이번 반복과정에서는 비교할 필요가 없으므로 첫번째 숫자는 제외하고,

두번째 수인 3까지만 비교를 수행하면 됩니다.

버블정렬을 구현함에 있어 각자의 스타일대로 로직을 구성하면 되겠습니다.

첫번째는 재귀(Recursioin)를 이용한 방법입니다.

       public void bubbleSortingRecursion() {

              for(int i=arr.length-1;i>completeIndex; i--) {

                     int j = i-1;

                     if(arr[j] > arr[i]) {

                           int temp = arr[j];

                           arr[j] = arr[i];

                           arr[i] = temp;

                           temp = 0;

                     }

              }

              completeIndex++;

              

              if(completeIndex >= arr.length-1) {

                     return;

              }else {

                     bubbleSortingRecursion();

              }

       }

두번째는 이중for문을 이용한 방법입니다.

public void bubbleSortingDubbleFor() {

              int arrLength = arr.length - 1;

              for(int j=0; j<arrLength; j++) {

                     for(int i=arr.length-2; i>=j; i--) {

                           if(arr[i] > arr[i+1]) {

                                  int temp = arr[i];

                                  arr[i] = arr[i+1];

                                  arr[i+1] = temp;

                                  temp = 0;

                           }

                     }

              }

       }

로직에 대한 정답은 정해져 있지 않습니다.

해당 알고리즘에 대해 완벽한 이해만 있다면 작가가 글을 쓰듯이

있는 그대로를 프로그래밍 언어에 맞추어 옮겨 쓰기만 하면 된다고 생각하시면 됩니다.

마치 책을 읽고 독후감을 쓸때 그 책을 잘 읽고 이해한 독서였다면 독후감때

본인이 생각한 그대로를 글로 옮기는 것이 어렵지 않듯.. 같습니다.

그날 있었던 일을 일기로 옮기는것이 어렵지 않듯이 원리와 방법에 대해서 이해만 하신다면

있는 그대로를 프로그래밍 언어로 옮기시면 됩니다.

어떤 틀이나 형식에 구속되지 마세요.

정답은 없습니다.

위의 코드도 제가 제 방식대로 만든것이고요.

자신의 스타일대로 로직을 만들고 검증과 테스트만 거치면 된답니다.

코드에 대한 궁금한 점이나 개선해야할 의견을 주실 분은 댓글 주세요.