< 문제 >
- 개요
선택정렬(Selection Sort)
정의 : 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
-
예상 결과
예제배열이 버블정렬되는 과정을 출력하여라. 출력은 각 회전마다 한번씩 한다. 예상 결과는 하기 코드 실행시 예상되는 결과 값이다. -
예제배열{ 7, 9, 4, 3, 1 }
1 9 4 3 7
1 3 4 9 7 1 3 4 9 7
1 3 4 7 9 - 예제배열{ 15, 2, 24, 5, 11, 3 }
2 15 24 5 11 3
2 3 24 5 11 15
2 3 5 24 11 15
2 3 5 11 24 15
2 3 5 11 15 24
< 정답풀이 >
public class Test06 {
public static void main( String[] args ) {
// 시작시간 기록
long startTime = System.currentTimeMillis();
// 정렬할 배열
int array[] = { 7, 9, 4, 3, 1 };
// int array[] = { 15, 2, 24, 5, 11, 3 };
// int array[] = { 7, 9, 4, 3, 1 };
process( array );
// 종료시간 기록
long endTime = System.currentTimeMillis() - startTime;
System.out.println( "소요시간 : " + endTime + "ms." );
}
/**
*
* <PRE>
*
* 주어진 배열이 선택정렬되는 과정 출력
*
* </PRE>
*
*/
public static void process( int array[] ) {
int size = array.length;
int cnt = 0;
// STEP 1. 전체 배열길이 -1만큼 반복한다.
while ( cnt < size - 1 ) {
int stack = 0; // 임시변수
int pickedInx = cnt; // 정렬 대상 위치(가변값)
int min = array[cnt]; // 정렬 대상 값(가변값)
/*
* STEP 2.최소값과 최소값의 위치를 확인한다.
* 정렬 시작위치는 아직 정렬되지 않은 값들의 위치에서 시작한다.
*/
for ( int inx = cnt + 1 ; inx < size ; inx++ ) {
if ( array[inx] < min ) {
min = array[inx];
pickedInx = inx;
}
}
// STEP 3. 선택정렬을 수행한다.
stack = array[cnt];
array[cnt] = array[pickedInx];
array[pickedInx] = stack;
System.out.println( Arrays.toString( array ) );
cnt++;
}
}
}