코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.

정렬(Sorting) : 리스트의 원소들을 특정 순서로 정리하는 것

sorted, .sort()를 쓰면 되는데 왜 정렬을 배워야 할까?

1. 정렬을 배우면서 문제 해결의 기초를 다질 수 있다.
2. 모든 개발자가 알아야 하는 기본적인 알고리즘이다.

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]