선택 정렬(selection sort)

<위키백과 참조>

 

선택 정렬(selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

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

비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.

선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

 

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

선택 정렬 - 위키백과, 우리 모두의 백과사전

 

 

<구현>

입력	출력
6 13 5 11 7 23 15	5 7 11 13 15 23

위 표대로 입력이 주어질때, 오름차순으로 정렬하는 프로그램을 선택정렬을 통해 구현해보자.

import java.util.*;

public class Main {
    public static int[] solution(int n, int[] arr){
        for(int i=0;i<n-1;i++){
            int min = arr[i];
            int target = arr[i];
            int idx = i;

            for(int j=i+1;j<n;j++){
                min = Math.min(min, arr[j]);
                if(min == arr[j]) idx =j;
            }
            if(idx!=i){
                arr[i] = min;
                arr[idx] = target;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      int n = kb.nextInt();
      int[] arr = new int[n];

      for(int i=0;i<n;i++){
          arr[i] = kb.nextInt();
      }
      for(int e : solution(n,arr)){
          System.out.print(e + " ");
      }
    }
}

 

좀더 코드를 줄여보면,

    public static int[] solution(int n, int[] arr){
        for(int i=0;i<n-1;i++){
            int idx = i;
            int target = arr[i];

            for(int j=i+1;j<n;j++){
                if(arr[j]<arr[idx]) idx =j;
            }
            arr[i] = arr[idx];
            arr[idx] = target;
        }
        return arr;
    }

위처럼 solution 메소드를 수정할수 있다.

 

 

<설명>

선택 정렬 설명

2중 for문을 사용해서 정렬을 한다.

outter for문은 배열(arr)의 각 요소(i부터 n-1까지)에 접근하고, inner for문에서는 i+1부터 n까지 접근한다.

innerFor문에서는 i를 제외한 나머지 요소들 중에서 최소값을 구해서(Math.min()) min변수에 대입한다.

arr[i]과 min(arr[idx])의 위치를 바꾼다.