[알고리즘] 선택 정렬(Selection Sort)

알고리즘을 이해하자 하자 하자 하자!

 

 

 

Table of Contents

 

선택 정렬의 이해

방식

선택 정렬은 크게 3단계로 동작합니다.

1.  지정 : 정렬 후 원소를 집어넣을 위치(인덱스)를 집합에서 지정합니다. (첫번째 인덱스 → 마지막 인덱스 순)
2.  탐색 : 지정한 인덱스에 들어갈 원소를 탐색합니다. (가장 큰 수 / 가장 작은 수)
3.  정렬 : 탐색한 원소를 지정한 인덱스에 집어넣습니다. (기존 인덱스에 있던 원소와 탐색한 요소 교환)

 

분류

선택 정렬은 정렬 유형 3가지에 해당합니다.

• 비교 정렬 : 정렬 연산이 두 값을 비교하는 것을 기반으로 일어남

• 제자리 정렬 : 주어진 메모리 공간 외에 추가적인 공간을 필요로 하지 않는 정렬 방식
  • 원소의 정렬이 내부적으로 이뤄지며, 원소 외부의 필요한 변수나 메모리가 거의 없음을 의미함
• 불안정 정렬 : 입력 순서와 동일하지 않게 정렬 (중복 원소 존재 시 원소의 순서를 보장하지 않음)

 

선택 정렬의 구현

알고리즘 내부 동작 흐름

선택 정렬을 활용해 배열 {3, 9, 1, 7, 5} 를 오름차순 {1, 3, 5, 7, 9}로 정렬할 시 내부 원소의 정렬 흐름 예시입니다.

 

[범례]

* 현재 지정한 인덱스

* 지정한 인덱스에 위치할 원소

* 정렬이 완료된 원소

* 지정한 인덱스가 가지고 있던 원소(순서 바꿔치기)

 

 

[알고리즘 동작 단계 : 총 3단계]

1. 인덱스 지정(배열의 0부터 n까지 순회) → 예제에서 i로 가정
2. 인덱스에 들어올 값 탐색(가장 작은 수) → 예제에서 idx로 가정
3. 가장 작은 수와 현재 지정한 인덱스에 있는 수를 교환

3

9

1

7

5

 

지정 인덱스는 0을 가리킵니다. ( i = 0)

 

3

9

1

7

5

 

지정한 인덱스를 제외한 "다음 인덱스부터 끝까지" 순회하며 가장 작은 수를 찾습니다. (순회하는 인덱스를 j로 가정)

 

[가장 작은 수를 찾는 법]

1. 현재 지정 인덱스의 원소보다 작은 수를 찾습니다.
2. 작은 수를 찾으면, 가장 작은 수를 가리키는 변수의 인덱스를 갱신합니다. (idx = j)
3. 순회 종료 시 (j의 루프가 종료 시) 지정 인덱스에 들어올 원소의 현 위치가 idx에 저장됩니다.

따라서 idx는 가장 작은 수인 1의 위치인 2가 저장됩니다. (idx = 2)

 

1

9

3

7

5

 

찾은 원소와 지정 인덱스에 있던 원소를 교환합니다.

과정에서 지정 인덱스에 있던 기존 원소를 저장할 임시 변수를 선언합니다. (temp)

아래와 같은 교환 과정을 거칩니다.

int temp = arr[i] // 지정 인덱스에 있던 기존 원소 저장
arr[i] = arr[idx] // 지정 인덱스에 탐색한 값(가장 작은 수) 저장
temp = arr[idx] // 탐색한 값이 있던 기존 위치에 지정 인덱스의 기존 원소 저장

 

1

9

3

7

5

 

지정 인덱스 i = 0에서 가장 작은수인 1의 저장이 완료되었습니다.

 

1

9

3

7

5

 

지정 인덱스를 i = 1로 옮겨 다음 수를 탐색합니다.

 

1

9

3

7

5

 

다음으로 가장 작은 수인 원소 3과 그 위치인 idx = 2의 탐색이 완료되었습니다.

 

1

3

9

7

5

 

찾은 원소와 지정 인덱스에 있던 원소를 교환합니다.

 

1

3

9

7

5

 

지정 인덱스 i = 1에서 두번째로 작은 수인 3의 저장이 완료되었습니다.

 

1

3

9

7

5

 

지정 인덱스를 i = 2로 옮겨 다음 수를 탐색합니다.

이하 과정은 반복되므로 도표만 참고하셔서 원소가 어떻게 교환되는지 참고해주세요.

 

 

1

3

9

7

5

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

1

3

5

7

9

 

 

슈도 코드

method sort(배열의 길이, 정렬할 배열) { // 배열을 오름차순으로 정렬한다.
        for (int i = 0; i < 배열 길이-1; i++){
            /* 1. 지정 : 요소의 위치를 지정할 인덱스를 지정 */
            인덱스는 loop에 맞춰 1씩 증가

            /* 2. 탐색 : 지정한 인덱스에 들어갈 요소를 탐색(가장 작은 수) */
            for (int j = i+1; j < 배열 길이; j++){
                 if (idx에 있는 현 요소보다 탐색한 요소가 작을 시)
                 해당 요소의 인덱스를 idx에 저장
            } // for문 종료 시 : 가장 작은 요소의 인덱스가 idx에 저장된다.

            /* 3. 정렬 : 지정한 인덱스에 들어올 요소(가장 작은 수)와
            지정한 인덱스에 있는 현 요소를 교환 */
            임시 변수 = 지정 인덱스의 기존 원소 
            지정 인덱스 = 탐색한 가장 작은 값
            교환한 가장 작은 값의 기존 위치 = 지정 인덱스의 기존 원소
        }
        return 정렬 완료된 배열
    }

 

구현 (java)

public int[] solution(int n, int[] arr) { // 배열을 오름차순으로 정렬한다.
        for (int i = 0; i < n-1; i++){
            /* 1. 지정 : 요소의 위치를 지정할 인덱스를 지정 */
            int idx = i; // 인덱스는 loop에 맞춰 1씩 증가

            /* 2. 탐색 : 지정한 인덱스에 들어갈 요소를 탐색(가장 작은 수) */
            for (int j = i+1; j < n; j++){
                if (arr[j] < arr[idx]) // idx에 있는 현 요소보다 탐색한 요소가 작을 시
                    idx = j; // 해당 요소의 인덱스를 저장한다.
            } // for문 종료 시 : 가장 작은 요소의 인덱스가 idx에 저장된다.

            /* 3. 정렬 : 지정한 인덱스에 들어올 요소(가장 작은 수)와
            지정한 인덱스에 있는 현 요소를 교환 */
            int tmp = arr[i]; // 현 인덱스에 있는 요소는 들어올 요소(가장 작은수)와 위치를 교환
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }

 

시간복잡도

• 탐색
  • 2개의 for문 실행  
  • 지정 인덱스를 도는 외부 for문 : n-1번
  • 선택한 값을 찾는 내부 for문 : n-1번, n-2번, n-3번 ... 3번, 2번, 1번 = (n-1)*(n-2) / 2
• 비교 수
  • 임시 변수를 이용한 3번의 이동 작업 (기존 원소 -> temp -> 바뀐 원소) : 3(n-1)
• 시간복잡도 : 최선, 평균, 최악의 비교횟수가 동일합니다. 
  • 최선 : T(n) = O(n^2)
  • 평균 : T(n) = O(n^2)
  • 최악 : T(n) = O(n^2)

 

# 구현 코드

클릭 시 깃허브로 연결됩니다.