선택 정렬(selection sort)

1) 선택 정렬(selection sort) 이란?

다음과 같은 순서를 반복하며 정렬하는 알고리즘

- 주어진 데이터 중에서 최소값을 찾음

- 해당 최소값을 데이터 제일 앞에 위치한 값과 교체함

- 제일 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복하여 교체함

 

Selection sort - Wikipedia

 

2) 알고리즘 구현

 

▼ 파이썬

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for idx in range(stand + 1, len(data)):
            if data[lowest] > data[idx]:
                lowest = idx
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

1. for stand in range(len(data) - 1) 로 반복

2. lowest = stand 로 놓고

3. for idx in range(stand + 1, len(data)) 로 반복 (stand + 1 이후부터 반복)

4. 내부 반복문 안에서 data[lowest] > data[idx] 이면, lowest = idx

5. data[lowest] 와 data[stand] 자리 바꿈

 

결과

import random

data = random.sample(range(100), 10)
print(selection_sort(data))

 

 

▼ 자바

void selectionSort(int[] arr) {
    int idxMin, tmp;
    for(int i = 0; i < arr.length - 1; i++) {		// 1.
        idxMin = i;
        for(int j = i + 1; j < arr.length; j++) {	// 2.
            if(arr[j] < arr[idxMin]) {		// 3.
                idxMin = j;
            }
        }
        // 4. swap (arr[idxMin], arr[i]
        tmp = arr[idxMin];
        arr[idxMin] = arr[i];
        arr[i] = tmp;
    }
    System.out.println(Arrays.toString(arr));
}

 

 

3) 알고리즘 분석

- 반복문이 두 개인 형태이므로, O(n^2)

   실제로 상세하게 계산하면, {n*(n-1)}/2

 

 

 

참고)

1. Selection sort - Wikipedia

Selection sort - Wikipedia

2. 패스트캠퍼스 '코딩 알고리즘 온라인 완주반'

3. 선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview (gyoogle.dev)

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview