선택정렬(Selection sort) Java 구현

Java 선택정렬(selection sort)

이번주에 정보처리기사 시험이 있기도 하고,

정렬 문제 같은 경우 Java로 구현을 한번씩 해보고 싶기도 해서 선택정렬을 필두로

삽입정렬, 버블정렬 병합정렬, 퀵정렬, 힙정렬을 해보고자 한다.

선택정렬

• 선택정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다

임의의 배열 arr = [6, 4, 8, 3, 1, 9, 7]이 있을때 선택정렬 알고리즘의 순서는

arr[0]값 6을 지정하고 arr[1]부터 arr[6]까지 스캔 후 가장 작은 값인 1과 교환하게 된다.

정렬을 마친 부분을 제외하고 이 알고리즘을 계속해서 지속한다

스텝별로 정리를 해보자면

step 1. [1, 4, 8, 3, 6, 9, 7] <

step 2. [1, 3, 8, 4, 6, 9, 7]

step 3. [1, 3, 4, 8, 6, 9, 7]

step 4. [1, 3, 4, 6, 8, 9, 7]

step 5. [1, 3, 4, 6, 7, 9, 8]

step 6. [1, 3, 4, 6, 7, 8, 9]

총 6단계를 거쳐 정렬이 완료된다.

알고리즘의 원리는

첫번 째, 정렬되지 않은 배열에서 최소값을 구한다.

두번 째, 최소값과 정렬되지 않은 배열의 첫 번째 element와 교환한다.

static void selectionSort[int[] a, int n]{ // selectionSort함수에 배열a와 배열길이 n값
    for(int i =0; i<n-1; i++){
        int min = i; //정렬되지 않은 배열 최소 엘리먼트의 인덱스 저장
        for(int j= i+1; j<n;j++){
            if(a[j] < a[min]){
                min = j; // 배열에서 최소값의 인덱스 저장
            }
        }
        swap(a, i, min); //swap(배열, 인덱스 1, 인덱스 2) --> 인덱스 1과 인덱스 2에 위치한 값 교환
    }
}

시간복잡도는 O(n^2)