Day07_array_Test12 : 선택 정렬 (★★)

(Q) 선택 정렬 (Selection sort)

다음 규칙에 따라 정렬을 구현하세요.
30, 10, 20, 50, 40을 저장할 배열을 만듭니다.
배열의 위치를 변경하여 10, 20, 30, 40, 50 순으로 저장될 수 있도록 만든 뒤 출력합니다
배열에서 가장 작은 값을 찾아 가장 왼쪽에 있는 데이터와 교체합니다
교체된 데이터의 위치는 제외하고 나머지 위치에서 가장 작은 값을 찾아 좌측 데이터와 교체합니다
데이터가 완전히 정렬될 때까지 반복합니다

** 다음 사이트를 참고하여 구현하세요

1. 상단 메뉴에서 정렬 방식을 `SEL`(선택 정렬, SELECTION SORT)로 지정합니다
2. 하단 `Create(A)` 버튼을 눌러 데이터 입력란에 `30, 10, 20, 50, 40`을 입력하고 Go를 누릅니다
3. 하단 `Sort` 버튼을 누르면 정렬되는 과정을 시각적으로 확인할 수 있습니다 

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

 

package day07;

public class Day07_array_Test12 {

	public static void main(String[] args) {
		
		// 배열의 생성
		int[] array = new int[] {30, 10, 20, 50, 40};
		
		//정렬 전 출력
		for(int i = 0 ; i < array.length ; i ++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
		
		// 선택 정렬
		for(int j = 0 ; j < array.length ; j ++) {
			for(int i = j ; i < array.length ; i ++) {
				int minIndex = j;			// minIndex를 설정
				int backup = array[minIndex];		// 배열의 minIndex에 저장된 값을 백업
				if(array[minIndex] > array[i]) {	// 만약 minIndex의 값보다 i번째 값이 작다면
					minIndex = i;			// minIndex를 i로 바꾼다 (최소값 위치 찾기)
				}
				backup = array[j];			//데이터 교체 (swap)
				array[j] = array[minIndex];
				array[minIndex] = backup;
			}
		}
		
		// 정렬 후 출력
		for(int i = 0 ; i < array.length ; i ++) {
			System.out.print(array[i] + " ");
		}
	}
}

 

- 1 사이클에 대한 코드를 작성한 후 반복문을 중첩시켜 최종 정렬 코드를 작성

 

 

 

** 선택 정렬 (Selection Sort)

1) 배열의 첫 번째 값을 가장 작은 값(min)으로 가정하여 가장 작은 값의 인덱스(minIndex)를 0으로 한다

2) 배열의 오른쪽 방향으로 비교를 진행하면서 가장 작은 값(min)보다 작은 값이 나오면 그 값의 인덱스를 minIndex에 대입

    한다 (가장 작은 값의 인덱스를 바꾼다)

3) 오른쪽 끝까지 비교를 완료하면 최종 minIndex의 데이터와 첫 번째 데이터를 맞바꾼다  (데이터 교체, Data Swap)

4) 배열의 첫 번째 위치에는 배열 중 가장 작은 값이 위치하게 된다

5) 배열의 두 번째 값을 가장 작은 값(min)으로 가정하여 위의 2) ~ 4) 과정을 반복한다