선택 정렬(Selection Sort)

동빈나 실전 알고리즘 강좌(Algorithm Programming Tutorial) 참고

https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz

실전 알고리즘 강좌 (Algorithm Programming Tutorial)

선택 정렬(Selection Sort)

가장 작은 것을 선택해서 제일 앞으로 보내자

순차적으로 숫자를 하나씩 읽어가면서 가장 작은 수를 저장한시가 뒤 앞의 큰 숫자와 자리를 바꾸면서 정렬하는 알고리즘

시간 복잡도 : O(N^2)

 

package algorithmProgramming;

public class SelectionSort {

    public static void main(String[] args) {
        // SelectionSort 선택정렬
        // "가장 작은 것을 선택해서 제일 앞으로 보내자"

        int[] numbers = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
        int minIndex = 0;

        for (int i = 0; i < numbers.length; i++) { 
            int min = 9999; // min은 변수 j를 갖는 for문 들어가기 직전에 배열에 없는 가장 큰 수로 초기화 되어야 함
            for (int j = i; j < numbers.length; j++) { 
                if (numbers[j] < min) { 
                    min = numbers[j]; 
                    minIndex = j; 
                }
            }
            // 찾은 min을 numbers[i]와 자리바꾸기 => 작은 수 앞 쪽으로 이동
            int tmp = numbers[i]; 
            numbers[i] = min; // min이 9999로 초기화가 되어 안쪽 for문을 돌면서 무조건 값이 변하게 됨
            numbers[minIndex] = tmp; 
        }

        for (int i = 0; i < numbers.length; i++) {
            System.out.print(numbers[i] + " ");
        }

    } // main

}

 

오름차순 정렬 완료