선택정렬

선택정렬은 각 인덱스에 올 수 있는 값을 기준으로 정렬해나가는 소팅알고리즘입니다.

public static void insertionSort(int[] arr){
    for(int i = 0; i<arr.length;i++){
      int idx = i;
      for(int j = i+1; j<arr.length;j++){
        if(arr[j]<arr[idx]){
          idx = j;
        }
      }
      swap(arr, idx, i);
    }
  }
  public static void swap(int[] arr, int a, int b){
    int tmp = arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
  }

개념

• 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.
• 현재 위치에 저장될 값의 크기가 작녀 크냐에 따라 최소선택정렬, 최대선택정렬로 나눌 수 있습니다.

로직

1. 주어진 배열에서 첫번째 인덱스를 기준으로 삼습니다. 기준은 처음부터 시작합니다.
2. 주어진 배열에서 기준 이후의 값 중 최소값을 찾습니다.
3. 최소값과 기준값을 교체합니다.
4. 기준 이후의 나머지 배열을 같은 방법으로 교체합니다.

int[] arr = {7, 6, 2, 4, 3, 9, 1};

private static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) { // 1
            int standard = i;
            for (int j = i + 1; j < arr.length; j++) { // 2
                if (arr[j] < arr[standard]) standard = j; // 3
            }
          	
          	// 4
            int temp = arr[standard];
            arr[standard] = arr[i];
            arr[i] = temp;

            print(arr);
        }
    }

private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

// 단계별 결과.
1단계 : 1 6 2 4 3 9 7 
2단계 : 1 2 6 4 3 9 7 
3단계 : 1 2 3 4 6 9 7 
4단계 : 1 2 3 4 6 9 7 
5단계 : 1 2 3 4 6 9 7 
6단계 : 1 2 3 4 6 7 9 
7단계 : 1 2 3 4 6 7 9

단계별 결과를 보면 배치할 인덱스를 정해두고 요소를 선택해나감을 알 수 있습니다.

i+1번째 원소부터 가장 작은 값을 선택해 인덱스 값과 비교해가며 위치를 갱신하고 변경하고있음을 알 수 있죠.

정리해보자면

1단계 : n개의 원소 비교

2단계 : n-1개의 원소비교

3단계 : n-2개의 원소비교

...