[JAVA] 선택정렬 (Selection Sort)

선택정렬은 한 번의 배열 탐색에서 가장 작은 원소의 위치를 찾고, 그 위치와 배열의 가장 첫 번째 원소부터 차례로 바꿔주는 방식을 사용하는 정렬 방식이다. (오름 차순)

오름차순으로 정렬할 때, 원소를 처음부터 탐색하면서 작은 수를 찾고 그 수를 배열의 첫 번째 원소와 자리를 변경한다.

import java.util.Arrays;
class SelectionSort {
  
  public static void main(String[] args) {
    
   	int []arr = {3,4,6,8,7,5,0,2};
    
    for(int i = 0; i < arr.length - 1; i++) { //arr.length -1: 마지막 요소는 자연스럽게 정렬됨
      //현재 탐색에서 가장 앞의 원소를 초기 값으로 설정
      int minIndex = i;
      //탐색을 진행하며 가장 작은 값을 찾음
      for(int j = i+1; j < arr.length; j++) {
        if(arr[minIndex] > arr[j]) 
          minIndex = j;
      }  
        //탐색이 완료되면 가장 작은 값을 가장 앞의 원소와 가장 작은 원소의 위치를 바꿈
      int temp = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = temp;
    }
    System.out.println(Arrays.toString(arr));
    
  }
  
}

버블 정렬처럼 직관적으로 이해가 편하고, 불필요하게 원소를 교체하는 작업이 없기 때문에 버블 정렬보다 일반적인 상황에서 빠른 성능을 보이지만 시간 복잡도가 O(n^2) 이기 때문에 실전에서 사용하기는 힘들다.

출처 url: https://sskl660.tistory.com/80

[Java]선택 정렬(Selection Sort)