선택 정렬(Selection Sort)

선택정렬이란 ?

정렬되지 않은 자료에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식이다. 

사진 출처 : 위키 백과

정렬 과정

1.주어진 리스트 중에 최솟값을 찾는다.

2.그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).

3.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

속도는 ?

O(n ​2 ​​) 이다.

소스코드

import java.util.Scanner;

public class SelectionSort {
    static int length;
    static int array[];

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in); // 문자 입력을 인자로 Scanner 생성
        length = Integer.parseInt(scan.nextLine()); // 키보드 문자 입력
        array = new int[length];

        for (int i = 0; i < length; i++) {
            array[i] = scan.nextInt();
        }

        selectionSort();

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

    static public void selectionSort() {
        int i, j;
        for (i = 0; i < length; i++) {
            int tmp = i;
            for (j = i + 1; j < length; j++) {
                // 최소 값을 찾는다.
                if (array[tmp] > array[j]) {
                    tmp = j;
                }
            }
            // 맨 처음 tmp 값과 다를 경우 최소 값을 찾았기 때문에 교환 발생
            if (i != tmp) {
                int temp = array[tmp];
                array[tmp] = array[i];
                array[i] = temp;
            }

        }
    }
}

아 역시 몇번 짜보니까 금방했다.

계속 노력해야겠다.