선택 정렬(Selection Sort) - 자바(JAVA)

Selection Sort

---

선택 정렬(Selection Sort)은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞으로 이동시키는 과정을 반복하여 리스트를 정렬하는 방식입니다.

동작 과정

---

• 주어진 리스트에서 가장 작은 값을 찾습니다.
• 가장 작은 값과 리스트의 맨 앞의 원소를 교환합니다
• 정렬된 영역을 제외하고 나머지 리스트에서 가장 작은 값을 찾습니다.
• 다시 가장 작은 값과 정렬되지 않은 부분의 맨 앞 원소를 교환합니다.
• 이러한 과정을 리스트의 모든 원소가 정렬될 때까지 반복합니다.
  
  

 

예시 코드

---

public class SelectionSort {

    /**
     * i 와 j의 위치에 있는 값을 바꿉니다. (가장 작은 값인 array[j]와 array[i]의 값을 교환)
     */
    public static void swapElements(int[] array , int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

    }

    /**
     * start로부터 시작하는 최솟값의 위치를 찾고(start 포함)
     * 배열의 마지막 위치로 갑니다.
     */

    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;
    }

    /**
     * 선택 정렬을 사용하여 요소를 정렬합니다.
     */

    public static void selectionSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int j = indexLowest(array, i);
            swapElements(array, i, j);
        }
    }

    

    public static void main(String[] args) {
        int[] array = {10, 5, 7, 9, 1, 8, 2, 100, 42, 26, 32, 8, 11};
        selectionSort(array);
        System.out.println(Arrays.toString(array));

    }

    /**
     *     응답 값 [1, 2, 5, 7, 8, 8, 9, 10, 11, 26, 32, 42, 100]
     */
}

 

 

시간복잡도 및 효율성

---

선택 정렬은 안정적인 정렬 알고리즘이 아니며, 시간 복잡도는 O(n^2)입니다. 이는 리스트의 크기가 증가함에 따라 연산 횟수가 제곱적으로 증가한다는 의미입니다. 따라서 대량의 데이터를 정렬해야 할 때는 다른 더 효율적인 알고리즘을 사용하는 것이 좋습니다.