Selection sort (선택 정렬)

 

🌸  선택 정렬 정의

 

선택정렬은 순회하는 인덱스에 어떤 원소로 대체할지 선택하는 정렬 알고리즘입니다.

 

1

4

7

3

2

5

정렬전 배열

1

4

7

3

2

5

배열을 순회하며 최소값 찾기

 

현재 인덱스를 i라고 가정한 후 설명을 진행합니다.

i 는 변경 될 인덱스며 , i 에서 마지막 인덱스 까지 순회합니다. 현재 인덱스에 해당하는 값은 1 이며 i ~ 마지막 인덱스, 즉 0 ~ 5까지의 값중 1보다 작은 값은 없으므로 선택될 인덱스 또한 i 입니다. 따라서 현재 인덱스 0의 값 1과 가장 작은 값인 1 자기자신과 위치를 변경합니다. (변동 없음)

 

1

4

7

3

2

5

i = 1

다시 i 부터 마지막 인덱스를 순회하며 자신보다 작으면서 최소값을 찾아 위치를 변경합니다. 해당 값은 4번 인덱스 이므로 1 번인덱스 (4)와 4번인덱스 (2)를 교체합니다.

1

2

7

3

4

5

i = 2

1

2

3

7

4

5

i = 3

1

2

3

4

7

5

i = 4

1

2

3

4

5

7

i = 5 (마지막 인덱스)

 

현재 인덱스를 기준으로 마지막 인덱스까지 루프를 한번더 태우므로 선택정렬의 시간복잡도는 O(n^2) 입니다.

 

package sort.selection_sort;

import java.util.Arrays;

/**
 * 선택 정렬
 */
public class SelectionSort {

    /**
     * i 와 j 값 변경
     * 각 인덱스로 접근하므로 시간복잡도는 상수시간을 갖는다. O(1)
     * @param array
     * @param i
     * @param j
     */
    public static void swapElements(int [] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * start 인덱스 부터 시작해서 끝까지 순회중 가장 작은 값을 리턴한다.
     * @param array
     * @param start
     * @return
     */
    public static int indexLowest(int [] array, int start) {
        int lowIndex = start;

        for(int i = start;i < array.length;i++) {
            if(array[i] < array[lowIndex]) {
                lowIndex = i;
            }
        }
        return lowIndex;
    }

    /**
     * indexLowest 메서드를 통해 얻어온 가장작은값의 인덱스를 현재 인덱스와 변경한다.
     * @param array
     */
    public static void selectionSort(int [] array) {
        System.out.printf("before selection sort : %s\n", Arrays.toString(array));
        for(int i = 0;i < array.length;i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);

            System.out.printf("(i = %d) array : %s\n",i , Arrays.toString(array));
        }

    }
}

 

호출

import sort.selection_sort.SelectionSort;

public class Main {

    public static void main(String[] args) throws Exception {
    
        int [] needSort = {1, 4, 7, 3, 2, 5};
        
        SelectionSort.selectionSort(needSort);
    }
}

 

콘솔

before selection sort : [1, 4, 7, 3, 2, 5]
(i = 0) array : [1, 4, 7, 3, 2, 5]
(i = 1) array : [1, 2, 7, 3, 4, 5]
(i = 2) array : [1, 2, 3, 7, 4, 5]
(i = 3) array : [1, 2, 3, 4, 7, 5]
(i = 4) array : [1, 2, 3, 4, 5, 7]
(i = 5) array : [1, 2, 3, 4, 5, 7]
after selection sort : [1, 2, 3, 4, 5, 7]