1. 거품정렬(bubble sort)

알고리즘 관련 첫 포스팅이 되겠네요. 프로그래머에게 있어서 알고리즘은 참 중요한 부분이죠? 오늘은 알고리즘에 있어서 가장 기본이라고 할 수 있는 bulbble sort에 대해서 알아보겠습니다. 우선 그림을 통해서 한번 확인해보도록 하겠습니다. 

출처: wikibooks.org

 

지금 위의 그림을 보시면 한번 loop 돌때마다 하나의 최대값이 올라오게 됩니다. 하나씩 거품이 올라오는 형상을 따서 bubble sort라는 이름이 붙여졌다고 하네요. 머릿속으로 그림이 어느정도 그려지시나요? 그러면 pseudo code를 한번 살펴보겠습니다.

 

 

코드를 보면서 이해를 한번 해보겠습니다.

do
  swapped = false
  for i = 1 to indexOfLastUnsortedElement
    if leftElement > rightElement
      swap(leftElement, rightElement)
      swapped = true
while swapped

     . do-while 구문을 사용해서 swapped가 false가 될 때까지 loop를 돕니다. 이 loop이 시작에는 swapped를 false로 둡니다.

     . 이 loop 안에는 또 하나의 loop가 존재합니다. 이 loop는 정렬이 완료된 것을 제외한 곳까지 loop를 돌립니다.

     . 왼쪽의 element가 오른쪽의 element보다 크면 두 element를 swap 해주고, swapped는 true가 됩니다.

     => 즉, 내부 loop를 돌때, 더이상 swap 할 것이 없다면 이미 정렬이 완료되었다고 보고 sorting을 종료합니다.

 

실제 데이터가 어떻게 정렬되는지 느린 그림으로 보시죠.

출처: wikipedia.org

 

이해가 되셨나요? 이렇기 때문에 최선의 경우는 이미 정렬이 완료되어 있는 경우 한번 순회로 종료 할 수 있기 때문에 n으로 정렬이 가능하지만, 대부분의 경우에 n²이 됩니다. 거의 실사용되지는 않지만 쉽기 때문에 항상 알고리즘 처음에 나오는것 같습니다.

마지막으로 java 코드로 구현을 해보겠습니다. 구현하기 전 테스트 코드를 먼저 작성합니다.

package algorithm;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

public class SortTest {
     private int[] original_array = {6, 7, 5, 8, 9, 0, 1, 3, 2, 4};
     private int[] sorted_array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
     @Test
     public void bubbleSortTest() {
          Sort.bubbleSort(original_array);
          assertThat(original_array, is(sorted_array));
     }
}

     . 간단하게 0~9까지 랜덤 배열을 만들고 정렬된 배열을 만들어서 sorting을 하고 난 후 같은지 비교하는 코드입니다.

그럼 Sort 클래스를 만들고 bubbleSort를 static 메소드로 만들어봅시다.

package algorithm;

public class Sort {

     public static void bubbleSort(int[] original_array) {
          boolean swapped;
          int indexOfLastUnsortedElement = original_array.length-1;
          do {
               swapped = false;
               for (int i=0; i<indexOfLastUnsortedElement; i++) {
                    if (original_array[i] > original_array[i+1]) {
                         int tmp = original_array[i];
                         original_array[i] = original_array[i+1];
                         original_array[i+1] = tmp;
                         swapped = true;
                    }
               }
               indexOfLastUnsortedElement--;
          } while (swapped);
     }
}

pseudo code와 동일하게 만들었기 때문에 별도의 설명은 필요 없을것 같습니다. 그 동안 밀렸던 포스팅을 위해서 열심히 다시 달려봐야겠네요. 다들 즐코딩하세요:)

 

 

출처: wikipedia.org

 

저작자표시

'Algorithm' 카테고리의 다른 글

4. 병합정렬(Merge Sort)  (0)	2016.07.19
3. 빠른정렬(Quick Sort) - 1  (0)	2016.07.09
2. 삽입정렬(Insertion Sort)  (0)	2016.07.03