정렬 알고리즘 : 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort)

● 가장 기본적인 정렬방법으로서 서로 인접한 자료들을 서로 자리바꿈하면서 뒤에서부터 정렬되는 방법.

● 과정

1. 두 개의 항목을 비교한다.
2. 오른쪽 항목이 작으면 자리바꿈을 한다.
3. 오른쪽으로 한 자리 이동한다.
4. 가장 오른쪽에 한 항목을 비교할 때까지 앞의 3단계를 반복한다.

● Sort 인터페이스

/**
 * 소팅 interface
 * @author choiyongeun
 *
 */
public interface Sort {
	
	public int[] sorting();
	
}

● BubbleSort 클래스

public class BubbleSort implements Sort{

	private int[] sortArr;
	
	BubbleSort(){}
	
	public BubbleSort(int[] arr) {
		this.sortArr = arr;
	}
	
	public int[] sorting() {
		int arrLength = sortArr.length;
		
		for (int fisrtLoop=0 ; fisrtLoop < arrLength ; fisrtLoop++ )
			for ( int secondLoop = fisrtLoop+1 ; secondLoop < arrLength ; secondLoop++ )
				if( sortArr[fisrtLoop] > sortArr[secondLoop] )
					swap(fisrtLoop, secondLoop);
		
		return this.sortArr;
	}

	private void swap(int swapIndex1, int swapIndex2) {
		int temp = sortArr[swapIndex1];
		sortArr[swapIndex1] = sortArr[swapIndex2];
		sortArr[swapIndex2] = temp;
	}

}

● BubbleSort 단위테스트

public class BubbleSortTest {

	@Test
	public void test버블정렬() {
		
		int[] arr = {10,3,2,6,4,5,7,1,8};
		
		Sort sort = new BubbleSort(arr);
		
		arr = sort.sorting();
		
		int i=0;
		assertEquals(1, arr[i++]);
		assertEquals(2, arr[i++]);
		assertEquals(3, arr[i++]);
		assertEquals(4, arr[i++]);
		assertEquals(5, arr[i++]);
		assertEquals(6, arr[i++]);
		assertEquals(7, arr[i++]);
		assertEquals(8, arr[i++]);
		assertEquals(10, arr[i++]);

	}

}

더욱 가독성을 높인다면 아래와 같이 할 수 있겠네요^^

@Test
public void test버블정렬() {
    //given
    int[] expected = {1,2,3,4,5,6,7,8,10}
    int[] unsortedArr = {10,3,2,6,4,5,7,1,8};

    //when
    Sort sort = new BubbleSort(unsortedArr);

    //then
    assertThat(sort.sorting(), is(expected));
}

버블 정렬이 가장 손쉬운 정렬 방식 답게 구현이 매우 쉽다.

하지만 성능은 다른 정렬 알고리즘 보다 떨어진다.

* 참조자료 : 자바 자료구조론