선택정렬(SelectionSort)

선택정렬(SelectionSort)  

1. 처음부터 끝까지 검색하여 최소값을 찾아 1번째 값과 바꾼다.

2. 2번째부터 끝까지 검색하여 2번째 최소값을 찾아 2번째 값과 바꾼다.

3. 3번째부터 끝까지 검색하여 3번째 최소값을 찾아 3번째 값과 바꾼다.

4. 이것을 반복하며 정렬한다.

오름차순인 경우 최소값이 차례차례 앞에서부터 누적되는 정렬 방법이다.

7 5 6 1 9

n개의 배열이 있을 때 i는 비교 기준값, j는 비교 대상값

먼저 기준값 i은 첫번째 칸부터 끝 칸 n까지 검색해야 하는데 한칸을 이미 차지하고 있으므로 끝 칸까지의 개수는 n-1이 된다. 즉, 1부터 n-1까지 검색하여 최소값을 찾는다.

최소값인 i가 맨 왼쪽에 위치하면 j는 그 다음칸부터 검색해야 하니 i+1부터 n까지 검색하여 최소값을 찾는다.

package algorithm;

public class SelectionSort {

public static void main(String[] args) {

int[] data = {7, 5, 6, 1, 9};

int temp = 0; // swap용 임시 변수

for(int i = 0; i < data.length-1; i++) { // i는 0부터 data 배열개수-1까지 

for(int j = i + 1; j < data.length; j++) { // j는 i+1에서 data 배열개수까지

if(data[i] > data[j]) {  // 기준값 i보다 비교값 j가 작으면 기준값 위치로 j가 가야한다.

temp = data[i]; // swap 알고리즘

data[i] = data[j];

data[j] = temp;

}

}

}

System.out.println("=== 선택정렬 ===");

for(int i=0;i<data.length;i++) {

System.out.print(data[i]+" ");

}

}

}

=== 선택정렬 ===

1 5 6 7 9