select sort

• select sort는 정렬 알고리즘의 일종이다.
• 제자리 정렬(in-place sorting) 알고리즘의 하나
  • 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
• 정렬 방식
  1. 첫 번째 값과 두 번째 값을 비교한다.
  2. 두 번째 값이 더 작으면 첫 번째 값과 두 번째 값을 바꾼다. (첫 번째 값이 더 작으면 바꾸지 않는다.)
  3. 첫 번째 값과 세 번째 값을 비교한다.
     ...
  4. 두 번째 값과 세 번째 값을 비교한다.
     ...

구현해 보기

import random

# 랜덤 데이터 만들기
aList = list(range(1, 21))
random.shuffle(aList)

print(aList)
=> [1, 6, 20, 10, 12, 3, 17, 13, 19, 7, 14, 9, 11, 5, 2, 18, 8, 16, 4, 15]

def select_sort(aList):
    # 0부터 aList의 길이 만큼 반복
    for i in range(len(aList)):
        # j(i+1)부터 aList의 길이만큼 반복
        for j in range(i, len(aList)):
            # 현재 위치와 다음 위치의 값을 비교
            if aList[i] > aList[j]:
                # 기존의 값이 더 크면 교체
                aList[i], aList[j] = aList[j], aList[i]
    return aList
    
select_sort(aList)
-> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

딕셔너리의 경우

import string
import random

# 랜덤 데이터 만들기
aList = []
atozList = list(string.ascii_uppercase)
random.shuffle(atozList)
randnum = [random.randint(20,70) for i in range(28)]

for n, i in zip(atozList, randnum):
    a = {"name": n, "age": i}
    aList.append(a)
aList
->
[{'name': 'K', 'age': 36},
 {'name': 'X', 'age': 22},
 {'name': 'L', 'age': 56},
 {'name': 'T', 'age': 64},
 {'name': 'P', 'age': 54},
 {'name': 'Z', 'age': 56},
 {'name': 'B', 'age': 52},
 {'name': 'C', 'age': 39},
 {'name': 'O', 'age': 65},
 {'name': 'D', 'age': 39},
 {'name': 'J', 'age': 24},
 {'name': 'I', 'age': 26},
 {'name': 'V', 'age': 29},
 {'name': 'A', 'age': 45},
 {'name': 'W', 'age': 48},
 {'name': 'E', 'age': 60},
 {'name': 'S', 'age': 67},
 {'name': 'N', 'age': 52},
 {'name': 'G', 'age': 55},
 {'name': 'U', 'age': 43},
 {'name': 'F', 'age': 53},
 {'name': 'R', 'age': 46},
 {'name': 'H', 'age': 70},
 {'name': 'M', 'age': 56},
 {'name': 'Q', 'age': 42},
 {'name': 'Y', 'age': 50}]

def select_sort_dict(dataList, key):
    for i in range(len(dataList)):
        for j in range(i, len(dataList)):
            # if aList[i] > aList[j]:
            if key(dataList[i]) > key(dataList[j]):
                dataList[i], dataList[j] = dataList[j], dataList[i]
    return dataList

# key에다가 lambda 함수를 이용하여 name 전달 (name을 기준으로 정렬하겠다)
print(select_sort_dict(aList, lambda x: x['name']))
-> [{'name': 'A', 'age': 22}, {'name': 'B', 'age': 27}, 
{'name': 'C', 'age': 44}, {'name': 'D', 'age': 20}, 
{'name': 'E', 'age': 29}, {'name': 'F', 'age': 35}, 
{'name': 'G', 'age': 63}, {'name': 'H', 'age': 49}, 
{'name': 'I', 'age': 62}, {'name': 'J', 'age': 30}, 
{'name': 'K', 'age': 38}, {'name': 'L', 'age': 53}, 
{'name': 'M', 'age': 25}, {'name': 'N', 'age': 39}, 
{'name': 'O', 'age': 54}, {'name': 'P', 'age': 46}, 
{'name': 'Q', 'age': 52}, {'name': 'R', 'age': 27}, 
{'name': 'S', 'age': 46}, {'name': 'T', 'age': 35}, 
{'name': 'U', 'age': 55}, {'name': 'V', 'age': 34}, 
{'name': 'W', 'age': 54}, {'name': 'X', 'age': 55}, 
{'name': 'Y', 'age': 53}, {'name': 'Z', 'age': 63}]

ref

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html