선택 정렬(Selection Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

선택 정렬(Selection Sort)

• 잘못된 위치에 들어가 있는 원소를 찾아서 그것을 올바른 위치에 넣는 원소 교환 방식으로 정렬
• 가장 작은 원소를 찾아 첫 번째 위치의 원소와 교환
• 두 번째로 작은 원소를 찾아 두 번째 위치의 원소와 교환
• 첫 번째 원소를 키로 지정하고 뒤 원소와 비교해서 작은 값을 앞으로 보내는 방식
• 두 번째 원소를 키로 지정하고 뒤 원소와 비교해서 작은 값을 앞으로 보내는 방식
• 정렬될 때 까지 과정 반복
• 초기 : 5, 2, 8, 3, 1
• 1라운드
  • 키는 첫 번째 원소
  • 2, 5, 8, 3, 1 (5와 2교환)
  • 1, 5, 8, 3, 2 (2와8, 3을 비교 했지만 2가 작기 때문에 교환하지 않고, 2와 1교환)
• 2라운드
  • 1, 5, 8, 3, 2
  • 키는 두 번째 원소
  • 1, 3, 8, 5, 2 (5와 8을 비교 했지만 5가 더 작아서 그대로 두고 5와 3을 비교해서 두 원소 위치 교환)
  • 1, 2, 8, 5, 3 (네 번째 위치 원소까지 비교 했으니 다섯 번째 위치 원소와 비교 3과 2의 위치 교환)
• 3라운드
  • 1, 2, 8, 5, 3
  • 키는 세 번째 원소
  • 1, 2, 5, 8, 3 (8과 5 비교해서 위치 교환)
  • 1, 2, 3, 8, 5 (네 번째 위치 원소까지 비교 했으니 다섯 번째 위치 원소와 비교 5와 3 위치 교환)
• 4라운드
  • 1, 2, 3, 8, 5
  • 키는 네 번째 원소
  • 1, 2, 3, 5, 8 (8과 5 비교, 두 원소 위치 교환)
  • 완성

선택 정렬 예제 코드

• SelectionSort.java

public class SelectionSort {
    public static void main(String[] args) {
        int [] arr = {5,2,8,3,1};
        selectionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    static void selectionSort(int[] arr) {
        int temp;
        // 총 라운드 : 배열 크기 - 1 번 진행
        for(int i = 0; i < arr.length-1; i++) {
            // i 다음부터 끝까지 비교
           for(int j = i+1; j < arr.length; j++) {
                if(arr[i] > arr[j])  {
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
}