선택 정렬(Selection Sort)

개요

삽입 정렬(Insertion Sort)은 선택 정렬(Selection Sort)와 유사하지만, 조금 더 효율적인 알고리즘이다.

삽입 정렬은 최선의 경우에는 O(N)이라는 속도를 가지고 있다.

처리 과정

데이터: [4, 6, 2, 7, 8, 5, 0, 1]

처음에는 2번째 원소부터 시작한다.

1회전

1. 6과 4를 비교, 6이 더 큼으로 교환하지 않는다.
2. 2와 6을 비교, 2가 더 작음으로 바꿀 준비를 한다.
3. 2와 4를 비교, 2가 더 작음으로 그 앞에 위치한다.
   => [2, 4, 6, 7, 8, 5, 0, 1]

1회전 결과

[2, 4, 6, 7, 8, 5, 0, 1]

2회전

1. 7과 6를 비교, 7이 더 큼으로 교환하지 않는다.
2. 8과 7을 비교, 8이 더 큼으로 교환하지 않는다.
3. 5와 8을 비교, 8이 더 작음으로 교환할 준비를 한다.
4. 5와 7을 비교, 5가 더 작음으로 교환할 준비를 한다.
5. 5와 4를 비교, 4가 더 작음으로 그 뒤에 위치한다.
   => [2, 4, 5, 6, 7, 8, 0, 1]

2회전 결과

[2, 4, 5, 6, 7, 8, 0, 1]

3회전

1. 0과 8을 비교, 0이 더 작음으로 교환할 준비를 한다.
2. 0과 7을 비교, 0이 더 작음으로 교환할 준비를 한다.
3. 0과 6을 비교, 0이 더 작음으로 교환할 준비를 한다.
4. 0과 5을 비교, 0이 더 작음으로 교환할 준비를 한다.
5. 0과 4을 비교, 0이 더 작음으로 교환할 준비를 한다.
6. 0과 2을 비교, 0이 더 작음으로 그 앞에 위치한다.
   => [0, 2, 4, 5, 6, 7, 8, 1]

3회전 결과

[0, 2, 4, 5, 6, 7, 8, 1]

4회전

1. 1과 8을 비교, 1이 더 작음으로 교환할 준비를 한다.
2. 1과 7을 비교, 1이 더 작음으로 교환할 준비를 한다.
3. 1과 6을 비교, 1이 더 작음으로 교환할 준비를 한다.
4. 1과 5을 비교, 1이 더 작음으로 교환할 준비를 한다.
5. 1과 4을 비교, 1이 더 작음으로 교환할 준비를 한다.
6. 1과 2을 비교, 1이 더 작음으로 교환할 준비를 한다.
7. 1과 0을 비교, 0이 더 작음으로 그 뒤에 위치한다.
   => [0, 1, 2, 4, 5, 6, 7, 8]

4회전 결과

[0, 1, 2, 4, 5, 6, 7, 8]

코드(python)

주석 미포함

datas = [4, 6, 2, 7, 8, 5, 0, 1]

flag = False
c = 1

for i in range(1, len(datas)):
    prev = i - 1
    for j in range(i, 0, -1):
        if (datas[j] > datas[prev]) or (prev < 0):
            break
        else:
            print(f"{datas[j]}가 {datas[prev]} 보다 작음 데이터 교환")
            print(datas, '=>', end=' ')

            datas[j], datas[prev] = datas[prev], datas[j]
            print(datas)
            flag = True
        
        prev -= 1
    
    if flag:
        print(f"\n{c}회전: {datas}")
        flag = False
        c += 1

주석 포함

datas = [4, 6, 2, 7, 8, 5, 0, 1]

flag = False
c = 1

for i in range(1, len(datas)):
    # j = 현재 위치
    # prev = 이전 위치
    prev = i - 1
    # 현재 위치부터 0번째까지
    for j in range(i, 0, -1):
        # 현재 위치의 데이터가 이전 위치의 데이터보다 크면 교환하지 않음
        # 이전 위치인 prev가 1보다 작으면(데이터 벗어남) 데이터 교환(첫 번째라는 의미)
        if (datas[j] > datas[prev]) or (prev < 0):
            break
        else:
            print(f"{datas[j]}가 {datas[prev]} 보다 작음 데이터 교환")
            print(datas, '=>', end=' ')
            # 만약 현재 데이터가 이전 데이터보다 작으면 데이터 교환
            datas[j], datas[prev] = datas[prev], datas[j]
            print(datas)
            flag = True
        # 다음 데이터 비교를 위해 prev - 1
        prev -= 1
    
    if flag:
        print(f"\n{c}회전: {datas}")
        flag = False
        c += 1

print 내용

2가 6 보다 작음 데이터 교환
[4, 6, 2, 7, 8, 5, 0, 1] => [4, 2, 6, 7, 8, 5, 0, 1]
2가 4 보다 작음 데이터 교환
[4, 2, 6, 7, 8, 5, 0, 1] => [2, 4, 6, 7, 8, 5, 0, 1]

1회전: [2, 4, 6, 7, 8, 5, 0, 1]
5가 8 보다 작음 데이터 교환
[2, 4, 6, 7, 8, 5, 0, 1] => [2, 4, 6, 7, 5, 8, 0, 1]
5가 7 보다 작음 데이터 교환
[2, 4, 6, 7, 5, 8, 0, 1] => [2, 4, 6, 5, 7, 8, 0, 1]
5가 6 보다 작음 데이터 교환
[2, 4, 6, 5, 7, 8, 0, 1] => [2, 4, 5, 6, 7, 8, 0, 1]

2회전: [2, 4, 5, 6, 7, 8, 0, 1]
0가 8 보다 작음 데이터 교환
[2, 4, 5, 6, 7, 8, 0, 1] => [2, 4, 5, 6, 7, 0, 8, 1]
0가 7 보다 작음 데이터 교환
[2, 4, 5, 6, 7, 0, 8, 1] => [2, 4, 5, 6, 0, 7, 8, 1]
0가 6 보다 작음 데이터 교환
[2, 4, 5, 6, 0, 7, 8, 1] => [2, 4, 5, 0, 6, 7, 8, 1]
0가 5 보다 작음 데이터 교환
[2, 4, 5, 0, 6, 7, 8, 1] => [2, 4, 0, 5, 6, 7, 8, 1]
0가 4 보다 작음 데이터 교환
[2, 4, 0, 5, 6, 7, 8, 1] => [2, 0, 4, 5, 6, 7, 8, 1]
0가 2 보다 작음 데이터 교환
[2, 0, 4, 5, 6, 7, 8, 1] => [0, 2, 4, 5, 6, 7, 8, 1]

3회전: [0, 2, 4, 5, 6, 7, 8, 1]
1가 8 보다 작음 데이터 교환
[0, 2, 4, 5, 6, 7, 8, 1] => [0, 2, 4, 5, 6, 7, 1, 8]
1가 7 보다 작음 데이터 교환
[0, 2, 4, 5, 6, 7, 1, 8] => [0, 2, 4, 5, 6, 1, 7, 8]
1가 6 보다 작음 데이터 교환
[0, 2, 4, 5, 6, 1, 7, 8] => [0, 2, 4, 5, 1, 6, 7, 8]
1가 5 보다 작음 데이터 교환
[0, 2, 4, 5, 1, 6, 7, 8] => [0, 2, 4, 1, 5, 6, 7, 8]
1가 4 보다 작음 데이터 교환
[0, 2, 4, 1, 5, 6, 7, 8] => [0, 2, 1, 4, 5, 6, 7, 8]
1가 2 보다 작음 데이터 교환
[0, 2, 1, 4, 5, 6, 7, 8] => [0, 1, 2, 4, 5, 6, 7, 8]

4회전: [0, 1, 2, 4, 5, 6, 7, 8]

시간 복잡도

최선의 경우에는 교환하지 않고 한 번씩만 비교하고 그냥 넘어가기 때문에 O(N)의 시간 복잡도를 가진다.
하지만 최악의 경우에는 모든 숫자가 역순으로 되어있어 모두 교환하는 작업이 이루어 질 때 O(N^2)의 시간이 걸린다.

공간 복잡도

주어진 배열 안에서 교환하기 때문에 O(N)이다.

장점

1. 어느정도 정렬이 되어있으면 매우 빠르다.
2. 선택 정렬이라 버블 정렬에 비해 빠르다.
3. 메모리가 절약되고 안정적이다.

단점

1. 최악의 경우에는 매우 오래걸린다.
2. 데이터의 길이가 길수록 비 효율적이다.

ref

https://gyoogle.dev/blog/algorithm/Insertion%20Sort.html