[기본 정렬 알고리즘 #3] 선택 정렬

📌 기본 정렬 알고리즘

- 버블 정렬
- 삽입 정렬
- 선택 정렬 ✔
- 참고, 공간복잡도

 

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

---

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  • 1. 주어진 데이터 중, 최소값을 찾음
  • 2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
  • 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

 

2. 어떻게 코드로 만들까?

---

for stand in range(len(data) - 1):
  lowest = stand
  for index in range(stand + 1, len(data)):
    if data[lowest] > data[index]:
      lowest = index
  swap (lowest, stand)

 

3. 알고리즘 구현

---

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

import random

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

[4, 11, 24, 25, 34, 39, 49, 54, 64, 84]

 

 

4. 알고리즘 분석

---

• 반복문이 두 개 O(n^2)
  • 실제로 상세하게 계산하면, n*n(n-1)/2