[JAVA] 알고리즘 : 정렬- 선택정렬

 

선택 정렬

 

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

 

 

 

import java.util.*;

public class Main {
    public int[] solution(int n, int[] arr){
        for(int i=0; i<n-1; i++){
            int idxMin=i; // 1.
            for(int j=i+1; j<n; j++){ // 2.
                if(arr[j]<arr[idxMin]) idxMin=j; // 3.
            }
            // 4. swap(arr[idxMin], arr[i])
            int tmp=arr[i];
            arr[i]=arr[idxMin];
            arr[idxMin]=tmp;
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr =new int[n];
        for(int i=0; i<n; i++) arr[i] = sc.nextInt();
        for(int x : T.solution(n,arr)) System.out.print(x+" ");
    }
}

 

1. 위치(index)를 선택해준다.

 

2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 한다.

 

3. 오름차순이므로 현재 선택한 자리에 있는 값(arr[idxMin])보다 순회하고 있는 값(arr[j]) 이 작다면, 위치를 

갱신해준다.

 

4. 2번 반복문이 끝난 뒤에는 index에 1번에서 선택한 위치에 들어가야하는 값의 위치를 갖고있으므로 서로 교환해준다.