[알고리즘] 선택 정렬 (Selection Sort, 개념과 장단점, 과정, 자바 코드 구현, 시간복잡도, 공간복잡도)

목차

• 선택 정렬이란?
• 선택 정렬 과정
• 선택 정렬 구현 (자바 코드)
• 시간복잡도
• 공간복잡도
• 정렬 알고리즘 비교

 

---

1. 선택 정렬이란?

정렬되지 않은 값들 중에서 최솟값(혹은 최댓값)을 찾고, 정렬되지 않은 값 중 제일 앞에 위치한 값과 교체한다. 정렬되지 않는 값들 중 제일 앞쪽 위치, 즉 해당 순서에 원소를 넣을 위치가 이미 정해져 있다.

 

(특징)

• 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)이다.
• 비교 횟수는 많지만, 실제 교환되는 횟수는 적다. 따라서 똑같은 O(n^2)의 시간복잡도를 가지는 버블 정렬보다 적은 시간이 소요된다.

 

(장점)

• 알고리즘이 단순하고, 구현이 쉽다.
• 정렬된 배열을 반대로 재정렬할 때 효율이 좋다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

(단점)

• 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다.
• 중복된 값이 있을 경우, 기존 요소의 순서가 바뀔 수 있는 불안정성을 지닌다.

 

---

2. 선택 정렬 과정

1) 정렬되지 않는 값들 중 최솟값(혹은 최댓값)을 찾는다.

 

2) 정렬되지 않는 값들 중 제일 앞에 위치한 값과 교체한다.

 

3) 정렬되지 않는 값들에 대해 (1)번 과정부터 다시 반복한다.

 

 

https://www.geeksforgeeks.org/c-program-for-selection-sort/

 

---

3. 선택 정렬 구현 (자바 코드)

import java.util.*;
import java.io.*;

class Main {
    public static void main (String[] args) throws IOException {
        int[] arr = {5, 2, 9, 100, 70, 11};
        int n = arr.length;

        // 내림차순 정렬
        int minIdx, tmp;
        for (int i = 0; i < n; i++) {
        	minIdx = i;

            for (int j = i + 1; j < n; j++) {
                if (arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }

            tmp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = tmp;
        }

        System.out.println(Arrays.toString(arr));
    }
}

---

4. 시간복잡도

데이터의 개수가 n일 때,

• 첫번째 루프에서 비교 횟수 : 1 ~ (n-1) => n-1번
• 두번째 루프에서 비교 횟수 : 1 ~ (n-2) => n-2번
  ...
• n번째 로프에서 비교 횟수 : 1 => 1번

 

(n-1) + (n-2) + ... + 2 + 1 = n * (n-1) / 2 이다.

따라서 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)이다.

 

---

5. 공간복잡도

데이터의 개수가 n일 때,

 

주어진 배열 내에서 교환이 이뤄지므로 공간복잡도는 O(n)이다.

 

---

6. 정렬 알고리즘 비교 (시간복잡도)