정렬 알고리즘 : 선택정렬(selection sort)

선택 정렬 (selection sort)

● 버블 정렬의 자리바꿈 횟수를 줄임으로써 성능을 개선한 알고리즘, 선택정렬의 비교횟수는 버블 정렬과 같다.

● 과정

- 첫 번째 항목을 기준으로 다른 항목들을 비교하여 가장 작은 항목을 기준 항목과 자리바꿈으로써 정렬하는 방법

● 선택정렬 class

/**
 * 선택 정렬
 * @author silverDragon
 *
 */
public class SelectionSort {

	private int arr[];
	
	private int tail;
	
	SelectionSort() {}
	
	public SelectionSort(int[] arr) {
		this.arr = arr;
	}

	public int[] sorting() throws IllegalAccessException {
		
		if ( arr == null)
			throw new IllegalAccessException("array is null");
		
		for ( int fistLoop=0; fistLoop < arr.length ; fistLoop ++ ) {
			tail = fistLoop;
			for ( int secondLoop = fistLoop+1; secondLoop < arr.length ; secondLoop++ )
				if ( arr[secondLoop] < arr[tail])
					tail = secondLoop;
			change(fistLoop, tail);
		}
		
		return arr;
	}


	private void change(int replaceIndex1, int replaceIndex2) {
		int temp = arr[replaceIndex1];
		arr[replaceIndex1] = arr[replaceIndex2];
		arr[replaceIndex2] = temp;
	}

}

● 선택정렬 단위 테스트

public class SelectionSortTest {

	
	@Test
	public void test선택정렬_확인() throws IllegalAccessException {
		
		int[] arr = {5,3,1,2,4};
		
		SelectionSort sort = new SelectionSort(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++]);
		
	}
	
	@Test(expected=IllegalAccessException.class) 
	public void test선택정렬_익셉션체크() throws IllegalAccessException {
		new SelectionSort(null).sorting();
	}

}

ps : 과정을 그림을 그려서 보여주면 이해가 빨라지지만, 그림 그리는 것을 매우 귀찮아 하므로...ㅠ_ㅠ......:)

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