[Python] 선택 정렬(selection sort)

 

선택 정렬이란?

• 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식

      

• 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식(오름차순일 경우)

 

 

과정

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

 

        1. 주어진 데이터 중 최소값을 찾는다.

        2. 해당 최소값을 데이터 맨 챂에 위치한 값과 교체한다.

        3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복한다.

 

selection sort 특징

• 자료 이동 횟수가 미리 결정된다.
• 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.
• 코드가 간단하고 적은양의 데이터에서 효과적이다.
• 시간복잡도는 O(n^2)이다.

 

 

Python Code

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

 

 

selection sort 확인하기

import random

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

selection_sort(data_list)
print(data_list)

 

 

 

 

 

---

Reference

selection sort gif