[ 알고리즘 ] 선택 정렬

요즘 다시 알고리즘 공부를 시작하려고 하여
백준에서 문제를 풀어나가며 알고리즘을 따로 정리, 기술하는 방향으로 계획하고 있다.
그 중 정렬 알고리즘을 먼저 살펴보려고 하며,
오늘은 기본 중 하나인 선택 정렬를 알아보고자 한다.

---

선택 정렬 ( Selection Sort )

 

선택 정렬은 간단하지만 비효율적인 정렬 알고리즘 중 하나로, 배열에서 가장 큰 or 가장 작은 값을 찾아 현재 위치에 배치하는 과정을 반복하여 정렬된다.

 

순서는 다음과 같다.

 

1. 정렬되지 않은 부분에서 최솟값 or 최댓값 찾기

 

2. 현재 위치와 최솟 값 or 최대 값 교환

 

3. 다음 위치로 이동하며 반복

---

 

다음 그림과 같이 예시로 알아보자

5개의 정수 값을 가진 배열 Array가 존재한다.

이를 오름차순으로 왼쪽부터 최솟값을 찾아 정렬하고자 한다.

 

---

 

기본 형태

4

5

3

1

2

 

---

1회차

 

첫번 째 위치인 4를 기준

4

5

3

1

2

 

 

차례로 5, 3, 1, 2 와 비교

4

5

3

1

2

 

 

최솟값을 찾아 위치를 교환

4

5

3

1

2

 

 

1회차 완료

1

5

3

4

2

 

---

 

2회차

 

두번 째 위치인 5를 기준

1

5

3

4

2

 

 

차례로 3, 4, 2 와 비교

1

5

3

4

2

 

 

최솟값을 찾아 위치를 교환

1

5

3

4

2

 

 

2회차 완료

1

2

3

4

5

 

 

2회차만에 정렬되어 정렬된 배열은 다음과 같다.

1

2

3

4

5

---

전체 코드

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int [] arr = {6,4,2,1,3,5};
        selectionSort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }

    private static void selectionSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        int minIndex;
        for(int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for(int j = i + 1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            if(minIndex != i) {
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

 

 

구현은 쉽고 직관적이긴 하나,  선택 정렬은 앞서 말했듯 입력 배열에 관계없이(2회차에 정렬이 되었더라도)
외부 반복문에서 n -1 회, 내부 루프에서 n - 1, n - 2, ..., 1번 비교함으로
시간복잡도는 항상 O(n^2) 으로 비효율적이다.