day04-과제)선택정렬

• 선택정렬(Selection Sort)

 

선택정렬이란 해당 자리를 선택하고, 그 자리에 오는 값을 찾는 정렬이다.

선택정렬은 삽입정렬과 마찬가지로 정렬의 대상이 되는 데이터 외에  추가적인 공간이 필요하지 않기 때문에 '제자리정렬'이기도 하다 

 

---

 

• 선택 정렬의 과정(오름차순 기준 설명)

 

1. 주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 1~3 과정을 반복한다.

 

---

• 선택정렬 구현하기

package homework;

import java.util.Random;

public class SelectionSort {
	public static void main(String[] args) {
		//======랜덤 숫자 배열생성=========
		Random rand = new Random();
		int[] data = new int[10];
		for (int i = 0; i < data.length; i++) {
			//10개 정수 데이터 랜덤으로 생성
			data[i]=rand.nextInt(10)+1;
		}
		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.println("]");
		
		//======선택정렬 알고리즘=========
		
		
		for (int i = 0; i < data.length-1; i++) {
			//마지막 자리는 자동으로 확정되므로 data.length-1만큼 반복
			int indexMin=i;//자리를 선택할 변수
			for (int j = i+1; j < data.length; j++) {
				//확정된 자리를 제외한 나머지 숫자중 가장 작은 숫자를 찾기위한 반복
				if(data[j]<data[indexMin]) {
					indexMin=j;
					//오름차순이므로 현재 선택한 자리에 있는 값보다 data[j]의 값이 작다면, 위치(index)를 갱신.
				}
			}
			//두번째 반복문이 끝난 후 i자리에 있는 숫자와 indexMin자리에 있는 숫자를 교환
			int tmp = data[indexMin];
			data[indexMin] = data[i];
			data[i] = tmp;

			
		}
		//======선택 정렬후 배열=========
		
		System.out.print("[");
		for(int v:data) {
			System.out.print(v+" ");
		}
		System.out.println("]");
	}
}

출처: https://devuna.tistory.com/28 [튜나 개발일기]