선택정렬 코드 실행

선택정렬에 대해서 배워보았다.

버블정렬이 두개의 값을 비교해서 더큰값을 뒤로 옮기는 것을 반복한다면,

선택정렬은 전체를 비교해서 가장 작은값의 인덱스를 찾아,  그 값을 0번째 인덱스부터 차례대로 정렬해 나가는 방식이다.

버블정렬 1회전을 하면 가장 큰값을 마지막 인덱스에서 알 수 있고, 

선택정렬 1회전을 하면 가장 작은값을 첫번째 인덱스에서 알 수 있다.

 

선택정렬 코드

package class01;

public class Test03 {

	public static void main(String[] args) {
		
		int[] array = new int[5];
		array[0] = 7;
		array[1] = 5;
		array[2] = 9;
		array[3] = 2;
		array[4] = 1;
		
		for (int a=0; a<array.length-1; a++) {
			int minIdx = a;
			for (int i=a+1; i<array.length; i++) {
				if(array[minIdx]>array[i]) {
					minIdx =i;
				}			
			}
		int temp = array[a];
		array[a] = array[minIdx];
		array[minIdx]=temp;
		}
		
		for (int datas : array) {
			System.out.print(datas + " ");
		}
	}
}

 

디버깅 표

맨작

디버깅표를 보면 인덱스 전체를 탐색해서 인덱스 0자리부터 제일 작은값을 채워넣는다.

* 장점

   - 선택정렬 또한 버블정렬과 마찬가지로 구현이 쉬운편에 속하는 정렬법이다.

   - 정렬을 위한 비교 횟수는 많지만 실제로 교환하는 횟수는 적기 때문에

     많은 교환이 일어나야 하는 자료상태에서 효율적으로사용될 수 있다.

   - 버블정렬과 비교했을 때, 똑같은 O(N^2) 시간복잡도를 갖지만, 실제로 시간을 측정해보면

     버블정렬에 비해서는 조금 더 빠른 정렬 방식이다.

 

* 단점

항상 O( N^2) 이라는 시간복잡도를 갖기 때문에 시간이 오래걸리는 정렬 방식이다.