[알고리즘] 04. Java 정렬 알고리즘 - 선택 정렬

 

 

 

 

 

안녕하세요🖐️

 

이번시간에는 정렬 알고리즘 중 하나인 선택 정렬에 대해 간단히 알아보는 시간을 갖겠습니다~

 

 

 

 

---

선택 정렬 (Selection Sort)

선택 정렬은 버블 정렬처럼 간단하고 이해하기 쉬운 정렬 알고리즘 중 하나입니다. 주어진 배열을 처리할 때, 이 알고리즘은 전체 배열을 차례대로 탐색하면서 각 단계마다 남아 있는 요소 중 최솟값을 찾습니다(오름차순 정렬 시). 찾은 최솟값을 현재 위치의 값과 바꿔치기하며, 이러한 절차를 배열이 전부 정렬될 때까지 지속적으로 수행합니다.

 

선택 정렬의 작동방식을 순서대로 나열하면 아래와 같은 과정을 진행합니다. (오름차순)

1. 배열의 첫 번째 위치를 최소값의 위치로 가정합니다.
2. 현재 위치 이후의 배열에서 실제 최소값의 위치를 찾습니다.
3. 현재 위치의 값과 찾은 최솟값의 위치에 있는 값을 교환합니다.
4. 다음 위치로 이동하여 배열의 끝까지 같은 과정을 반복합니다.
5. 배열의 모든 원소가 정렬될 때까지 전체 과정을 반복합니다.

 

다음 예시로 선택 정렬이 어떻게 진행되는지 확인해 보겠습니다.

Int[] array = {4, 7, 2, 5, 1, 3, 6};

이런 배열이 있다고 가정해 보겠습니다. 이 배열을 오름차순으로 선택 정렬을 진행하게 되면 아래와 같이 정렬이 진행됩니다.

선택 정렬 예시

1. 배열 전체를 검사하여 최솟값(여기서는 1)을 찾습니다. 1은 다섯 번째 위치에 있으므로, 첫 번째 원소인 4와 위치를 교환합니다. 
   • 결과 배열: {1, 7, 2, 5, 4, 3, 6}
2. 첫 번째 원소를 제외한 나머지 배열에서 최솟값을 찾습니다. 이 경우 2가 두 번째로 작은 값입니다. 2는 현재 세 번째 위치에 있으므로, 두 번째 원소인 7과 위치를 교환합니다.
   • 결과 배열: {1, 2, 7, 5, 4, 3, 6}
3. 두 번째 원소를 제외한 나머지 배열에서 최솟값인 3을 찾습니다. 3은 다섯 번째 위치에 있으므로, 세 번째 위치에 있는 7과 위치를 교환합니다.
   • 결과 배열: {1, 2, 3, 5, 4, 7, 6}
4. 세 번째 원소를 제외한 나머지 배열에서 최소값인 4를 찾습니다. 4는 다섯 번째 위치에 있으므로, 네 번째 원소인 5와 위치를 교환합니다.
   • 결과 배열: {1, 2, 3, 4, 5, 7, 6}
5. 네 번째 원소를 제외한 나머지 배열에서 최소값인 5는 이미 올바른 위치에 있으므로, 교환할 필요가 없습니다.
   • 결과 배열: {1, 2, 3, 4, 5, 7, 6}
6. 마지막으로, 최소값인 6과 7을 비교합니다. 6이 더 작으므로 이들의 위치를 교환합니다.
   • 결과 배열: {1, 2, 3, 4, 5, 6, 7}

 

 

 

 

---

선택 정렬 실습

아래의 실습 예제와 함께 선택 정렬을 구현해 보겠습니다.

 

- 실습 예제 -

public class SelectionSort {

    void selectionSort(int[] arr) {
        int n = arr.length;

        // 배열의 각 위치에 대해 반복
        for (int i = 0; i < n - 1; i++) {
            // 현재 위치 i를 최소값의 위치로 초기화
            int minIndex = i;
            // 현재 위치 이후의 배열을 순회하며 최소값의 위치를 찾음
            for (int j = i + 1; j < n; j++) {
                // 현재 선택된 최소값보다 더 작은 값을 찾으면, 최소값의 위치를 갱신
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 최소값이 현재 위치의 값이 아니라면 위치를 교환
            if (minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
    	// SelectionSort 클래스 인스턴스 생성
        SelectionSort ss = new SelectionSort();

        int[] arr = {4, 7, 2, 5, 1, 3, 6};

        //SelectionSort 클래스의 selectionSort 메소드 접근
        ss.selectionSort(arr);

        // 정렬된 배열 출력
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

- 출력 결과 -

1 2 3 4 5 6 7

 

 

 

 

 

---

시간복잡도

선택 정렬의 시간 복잡도는 아래와 같습니다.

 

 

- 최악의 경우 시간 복잡도: O(n^2)

배열의 각 원소에 대해 남은 배열 부분의 최솟값을 찾아 위치를 교환해야 하므로, 모든 원소에 대해 이 과정을 반복합니다. 원소의 순서와 관계없이, 각 원소마다 나머지 원소들과 비교가 이루어져야 합니다.

 

- 최선의 경우 시간 복잡도: O(n^2)

선택 정렬은 주어진 배열의 정렬 상태와 관계없이, 각 원소를 나머지 원소들과 비교하여 최소값을 찾는 과정을 반복합니다. 따라서 최선의 경우에도 n−1, n−2,..., 1번의 비교가 필요하여 시간 복잡도는 변하지 않습니다.

 

- 평균 시간 복잡도: O(n^2)

원소들이 무작위로 배치되어 있는 평균적인 상황에서도, 모든 원소에 대해 남은 배열 부분과의 비교가 필요합니다.

 

 

선택 정렬은 그 구현의 단순성으로 인해 초보 프로그래머에게 알고리즘의 기본 개념을 가르치는 데 자주 사용됩니다. 하지만, 선택 정렬 역시 버블 정렬과 마찬가지로 비효율적인 시간 복잡도를 가지고 있어 대규모 데이터셋에는 적합하지 않습니다. 실제 응용에서는 더 효율적인 정렬 알고리즘들이 선호됩니다.

 

 

* 시간 복잡도에 대한 내용은 아래 글에서 확인할 수 있습니다.

[알고리즘] 복잡도란? (시간복잡도, 공간복잡도)

[알고리즘] 복잡도란? (시간복잡도, 공간복잡도)

 

 

 

 

 

 

 

 

이상으로 정렬 알고리즘 중 하나인 선택 정렬에 대해 알아보는 시간을 마치겠습니다!

 

읽어주셔서 감사합니다 😊

 

---

소스 코드 바로가기