[자료구조] 선택 정렬 (Selection Sort)

선택 정렬(Selection sort)

1. 요소들 중에서 가장 작은 값을 찾아서 배열의 첫번째 요소와 교환.
2. 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고, 이를 두번째 요소와 교환.
3. 앞에서부터 하나씩 정렬.
4. (요소의 수 -1) 만큼 반복.

출처: C언어로 쉽게 풀어쓴 자료구조

 

 

코드

import java.util.Scanner;

// 선택 정렬
public class SelectionSort {
    public void sort(int[] array) {
        for (int i=0; i < array.length-1; i++) {
            int minIndex = i;
            for (int j=i+1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
        }
        for(int n : array) {
            System.out.print(n + " ");
        }
    }
}

// 테스트
class Test {
    public static void main(String[] args) {
        System.out.print("정렬할 수를 입력하세요 ex) 1,4,5,3 >> ");
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] s = input.split(",");
        int[] array = new int[s.length];
        for(int i=0; i<s.length; i++) {
            array[i] = Integer.parseInt(s[i]);
        }
        SelectionSort selection = new SelectionSort();
        selection.sort(array);
    }
}

 

실행 결과

정렬할 수를 입력하세요 ex) 1,4,5,3 >> 1,8,4,6,7,2,4,3,5,10,12
1 2 3 4 4 5 6 7 8 10 12