코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.
정렬(Sorting) : 리스트의 원소들을 특정 순서로 정리하는 것
sorted, .sort()를 쓰면 되는데 왜 정렬을 배워야 할까?
- 정렬을 배우면서 문제 해결의 기초를 다질 수 있다.
- 모든 개발자가 알아야 하는 기본적인 알고리즘이다.
1. 선택 정렬 (Selection Sort)
가장 먼저 생각이 날 수 있는 자연스러운 정렬 알고리즘이며 각 위치에 어떤 값이 들어갈 지 찾는다.
가장 작은 값을 찾아서 0번 인덱스에 놓고,
두번째로 작은 값을 찾아서 1번 인덱스에 놓고,
세번째로 작은 값을 찾아서 2번 인덱스에 놓고
.
.
.다시 말하면 0번 인덱스에 들어갈 값을 찾고, 1번 인덱스에 들어갈 값을 찾고 이런식으로 반복하면 된다.
선택 정렬 동작 과정
list1 = [4, 2, 7, 1, 9, 3]
0번 인덱스에 들어갈 값을 찾는다.
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (0)
ㄴ 현재 인덱스 (0)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[4, 2, 7, 1, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)순회 결과 0번 인덱스에 들어갈 값은 3번 인덱스의 값이다. 따라서 3번인덱스와 1번인덱스를 바꿔준다.
list1 = [1, 2, 7, 4, 9, 3]
1번 인덱스에 들어갈 값을 찾는다.
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (1)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (3)
...
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (1)
ㄴ 현재 인덱스 (5)순회 결과 1번 인덱스의 값보다 작은 값이 없으므로 수정하지 않는다.
list1 = [1, 2, 7, 4, 9, 3]
2번 인덱스에 들어갈 값을 찾는다.
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (2)
ㄴ 현재 인덱스 (2)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 7, 4, 9, 3]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)순회 결과 2번 인덱스에 들어갈 값은 5번 인덱스의 값이다. 따라서 2번 인덱스와 5번 인덱스를 바꿔준다.
list1 = [1, 2, 3, 4, 9, 7]
3번 인덱스에 들어갈 값을 찾는다.
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (3)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (3)
ㄴ 현재 인덱스 (5)순회 결과 3번 인덱스의 값보다 작은 값이 없으므로 수정하지 않는다.
list1 = [1, 2, 3, 4, 9, 7]
4번 인덱스에 들어갈 값을 찾는다.
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (4)
ㄴ 현재 인덱스 (4)
[1, 2, 3, 4, 9, 7]
ㄴ 최솟값 인덱스 (5)
ㄴ 현재 인덱스 (5)순회 결과 4번 인덱스에 들어갈 값은 5번 인덱스의 값이다. 따라서 4번 인덱스와 5번 인덱스를 바꿔준다.
list1 = [1, 2, 3, 4, 7, 9]
5번 인덱스는?
값이 총 6개이므로 이제 5번인덱스에는 가장 큰 값이 채워져있다. 정렬을 종료하면 된다.
2. 삽입 정렬 (Insertion Sort)
각 값이 어떤 위치에 들어갈 지(삽입) 찾는다.
삽입 정렬 동작 과정
list = [4, 2, 7, 1, 9, 3]
1번 인덱스의 값이 들어갈 자리를 찾는다.
# 1
[4 , (2), 7, 1, 9, 3]
# 2
[4 , (2), 7, 1, 9, 3]
ㄴ 비교 인덱스(0)
[( ) , 4(2), 7, 1, 9, 3] # 4가 2보다 크므로 4를 오른쪽으로 옮긴다.
# 3
[2, 4, 7, 1, 9, 3] # 2를 빈 자리에 채운다.list = [2, 4, 7, 1, 9, 3]
2번 인덱스의 값이 들어갈 자리를 찾는다.
# 1
[2, 4, (7), 1, 9, 3]
# 2
[2, 4, (7), 1, 9, 3]
ㄴ 비교 인덱스(1)
[2, 4, (7), 1, 9, 3] # 4는 7보다 작기 때문에 그냥 넘어간다.인덱스 1 이하의 값은 이미 정렬이 되어있기 때문에 더이상 비교하지 않는다.
list = [2, 4, 7, 1, 9, 3]
3번 인덱스의 값이 들어갈 자리를 찾는다.
# 1
[2, 4, 7, (1), 9, 3]
# 2
[2, 4, 7, (1), 9, 3]
ㄴ 비교 인덱스 (2)
[2, 4,( ), 7(1), 9, 3] # 7이 1보다 크므로 7을 오른쪽으로 옮긴다.
# 3
[2, 4, ( ), 7(1), 9, 3]
ㄴ 비교 인덱스 (1)
[2, ( ), 4, 7(1), 9, 3] # 4가 1보다 크므로 4를 오른쪽으로 옮긴다.
# 4
[2, ( ), 4, 7(1), 9, 3]
ㄴ 비교 인덱스 (0)
[( ), 2, 4, 7(1), 9, 3] # 2가 1보다 크므로 2를 오른쪽으로 옮긴다.
# 5
[(1), 2, 4, 7, 9, 3] # 비교 할 값이 없기 때문에 1을 빈자리에 채운다.list = [1, 2, 4, 7, 9, 3]
4번 인덱스의 값이 들어갈 자리를 찾는다.
# 1
[1, 2, 4, 7, (9), 3]
# 2
[1, 2, 4, 7, (9), 3]
ㄴ 비교 인덱스 (3)
[1, 2, 4, 7, (9), 3] # 7은 9보다 작기 때문에 그냥 넘어간다.인덱스 3 이하값은 이미 정렬이 되어 있으므로 더이상 비교하지 않는다.
list = [1, 2, 4, 7, 9, 3]
5번 인덱스의 값이 들어갈 자리를 찾는다.
#1
[1, 2, 4, 7, 9, (3)]
#2
[1, 2, 4, 7, 9, (3)]
ㄴ 비교 인덱스(4)
[1, 2, 4, 7, ( ), 9(3)] # 9가 3보다 크므로 9를 오른쪽으로 옮긴다.
# 3
[1, 2, 4, 7, ( ), 9(3)]
ㄴ 비교 인덱스 (3)
[1, 2, 4, ( ), 7, 9(3)] # 7이 3보다 크므로 7을 오른쪽으로 옮긴다.
# 4
[1, 2, 4, ( ), 7, 9(3)]
ㄴ 비교 인덱스 (2)
[1, 2, ( ), 4, 7, 9(3)] # 4가 3보다 크므로 4를 오른쪽으로 옮긴다.
# 5
[1, 2, ( ), 4, 7, 9(3)]
ㄴ 비교 인덱스 (1)
[1, 2, (3), 4, 7, 9] # 2는 3보다 작으므로 빈 자리에 3을 채운다.list = [1, 2, 3, 4, 7, 9]
정렬이 완료되었다.
3. 정렬 알고리즘 비교
이 사이트에서 정렬 알고리즘의 퍼포먼스를 다양한 환경에서 살펴볼 수 있다.
정렬 문제에는 절대적인 답은 없으며, 상황에 따라 장단점을 파악할 수 있어야 한다.
4. 구현해보기
선택정렬, 삽입정렬을 구현해보았다.
# 선택정렬 구현하기 (자리의 주인을 찾는다.)
def selection_sort(my_list):
for i in range(len(my_list)):
min_idx = i
for j in range(i + 1, len(my_list)):
if my_list[min_idx] > my_list[j]:
min_idx = j
my_list[i], my_list[min_idx] = my_list[min_idx], my_list[i]
# 삽입정렬 구현하기 (삽입할 자리를 찾는다.)
def insertion_sort(my_list):
for i in range(1, len(my_list)):
value = my_list[i]
insertion_idx = i
for j in range(i-1, -1, -1):
if my_list[j] < value:
break
my_list[j+1] = my_list[j]
insertion_idx = j
else:
my_list[insertion_idx] = value
if __name__ == '__main__':
testcase = [4, 2, 7, 1, 9, 3]
testcase2 = [4, 2, 7, 1, 9, 3]
print(testcase)
print(testcase2)
selection_sort(testcase)
insertion_sort(testcase2)
print(testcase)
print(testcase2)# 콘솔 출력
[4, 2, 7, 1, 9, 3]
[4, 2, 7, 1, 9, 3]
[1, 2, 3, 4, 7, 9]
[1, 2, 4, 4, 7, 9]