선택 정렬

선택 정렬은 여러 개의 데이터가 있을 때 매번 가장 작은 것을 선택하여 앞으로 보내는 과정을 반복해서 수행하여 데이터를 정렬하는 것이다. 가장 원시적이며, 쉬운 방법이다.

정렬해야 할 데이터는 다음과 같다.

1. 전체 데이터 중 가장 작은 데이터인 '0'을 선택 후 맨 앞에 있는 데이터 7과 위치를 바꾼다.
   

2. 처리되지 않는 데이터 중 가장 작은 데이터인 '1'을 가장 앞의 데이터 5와 위치를 바꾼다.
   

3. 그 전과 마찬가지로 처리되지 않는 데이터 중 가장 작은 데이터인 '2'을 가장 앞의 데이터 9와 위치를 바꾼다.
   

이 과정을 반복 수행하면 정렬이 된다.

#정렬해야 할 배열
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(arr)):
    min_index = i #맨 처음 인덱스를 최솟값으로 설정
    for j in range(i+1, len(arr)):
        if arr[min_index] > arr[j]:  #만약 j가 최솟값보다 작다면
            min_index = j  #j를 최솟값으로 설정
    arr[i], arr[min_index] = arr[min_index], arr[i] #전부 비교 후, 최솟값과 현재 인덱스와 스왑

print(arr)
#출력값: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

선택 정렬의 시간 복잡도

선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 이 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다. 따라서 빅오 표기법으로 표기하면 O(N^2)이다.

삽입 정렬

삽입 정렬은 선택 정렬처럼 동작 원리를 직관적으로 이해하기 쉬운 알고리즘이다. 물론 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높지만, 시간 측면에서 더욱 효율적인 알고리즘이다.

특히 삽입 정렬은 "데이터가 거의 정렬 되어 있을 때" 매우 효과적이며, 선택 정렬은 현재 데이터의 상태와 상관없이 거의 모든 원소를 비교 후 위치를 바꾸는 반면에 삽입 정렬은 전혀 아니다.

다음의 우리가 정렬해야 할 데이터를 보자.

1. 우선 삽입 정렬은 선택 정렬과 다르게 두 번째 데이터에서 시작한다.
   
   두 번째 데이터 '5'가 어떤 위치로 들어갈지 판단한다. 그 전의 데이터인 '7'의 왼쪽 혹은 오른쪽으로 들어가는 경우만 존재한다. 정렬을 오름차순으로 해야하므로, 7의 왼쪽에 삽입된다.

2. 이어서 다음 원소 '9'가 어떤 자리에 삽입되어야 하는지 판단한다. 위치는 총 3가지며, '9'는 이전 데이터 '5'와 '7'보다 크기 때문에 원래 자리에 둔다.
   

3. 이어서 다음 원소 '0'이 어느 위치에 삽입될건지 판단한다. '0'은 '5', '7', '9'와 비교했을 때 가장 작기 때문에 첫 번째 원소인 '5'의 왼쪽 자리에 위치한다.
   

4. 이 작업을 계속 반복한다.
   

이 작업을 N-1번 반복하면 모든 데이터가 정렬된다.

삽입 정렬의 특징은 정렬이 이루어진 원소는 항상 오름차순을 유지하고 있다. 다시 말해 특정 데이터의 왼쪽에 있는 데이터들은 이미 정렬된 상태이므로 자기보다 작은 데이터를 만났다면 더 이상 데이터를 비교할 필요없이 그 자리에 삽입된다.

#정렬해야 할 배열
arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(arr)):
    for j in range(i, 0, -1):
        if arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]
        else:
            break

print(arr)
#출력값: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N^2)이다. 하지만 삽입 정렬은 현재 리스트가 거의 정렬되어있는 상태라면 매우 빠르게 동작한다. 가장 빠른 정렬인 퀵 정렬보다 빠를 때도 있다.