정렬 알고리즘 (1) [선택 정렬, 삽입 정렬]

https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

 

 

정렬 알고리즘

· 정렬이란 데이터를 특정 기준에 따라 순서대로 나열하는 것

· 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

​

​

1. 선택 정렬 알고리즘

· 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘

​

정렬 되지 않은 데이터

맨 처음 위와 같이 정렬 되어있지 않은 데이터가 존재한다고 가정해보자.

​

처리 되지 않은 데이터 중 가장 작은 값인 '0'을 선택해 가장 앞에 있는 '7'과 교환한다.

​

다시 처리되지 않은 데이터 중 가장 작은 값인 '1'을 처리 되지 않은 데이터 중 맨 앞에 있는 '5'와 교환한다.

​

교환을 반복한다.

​

최종적으로 위 사진과 같이 정렬이 완료된다.

​

마지막 데이터가 하나 남았을 때는 위치를 바꿔도 자기 자신의 자리이기 때문에 처리하지 않아도 성공적으로 정렬이 된다.

​

선택 정렬 코드

array = list(map(int, input().split()))

for i in range(len(array)):
    min_index = i
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]
    print(array)

print("result : ", array)

​

선택 정렬의 시간 복잡도

선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

​

구현 방식에 따라 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 다음과 같다.

N + (N-1) + (N-2) + ... + 2

(맨 마지막 원소는 정렬을 수행해주지 않아도 되기 때문에 끝은 2)

​

이는 (N2+N-2) / 2 로 표기할 수 있는데, 빅오 표기법에 따라 O(N2)으로 표기한다.

​

​

​

2. 삽입 정렬 알고리즘

· 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

· 선택 정렬에 비해 구현 난이도는 높지만, 일반적으로 더 효율적으로 동작한다.

​

정렬 되지 않은 데이터

첫 번째 데이터 '7'은 그 자체로 정렬이 되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다. '7'의 왼쪽으로 들어가거나 오른쪽으로 들어가거나 두 경우만 존재한다.

​

결과적으로 데이터 '5'가 '7'의 왼쪽으로 들어갈 수 있도록 위치를 바꿔준다.

이어서 '9'가 어떤 위치로 들어갈지 판단한다. 제일 왼쪽(첫 번째 화살표)과 두번째 위치(두 번째 화살표) 그리고 3번째 위치(3 번째 화살표) 중에서 한 곳을 선택한다.

즉, '9'는 차례대로 왼쪽에 있는 데이터와 비교해서 왼쪽 데이터보다 더 작다면 둘의 위치를 바꾸고 그렇지 않다면 그 자리에 머문다.

​

마찬가지로 그 다음 데이터인 '0'을 기준으로 왼쪽의 화살표들 중 어느 위치에 들어갈지를 선택한다. '0'의 왼쪽부터 차례대로 비교해서 최종적으로 가장 왼쪽인 데이터 '5'의 왼쪽에 위치에 들어가게 된다. 즉, 매번 위치를 바꿔가면서 가장 첫 번째 위치에 들어간다.

​

이러한 과정을 반복하면 위 사진과 같이 정렬이 완료된다.

​

삽입 정렬 코드

array = list(map(int, input().split()))

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

삽입 정렬의 시간 복잡도

· 삽입 정렬의 시간 복잡도는 O(N2) 이며, 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용된다.

· 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

· 이미 정렬되어 있는 상태에서 다시 삽입 정렬을 수행하면 (즉, 최선의 경우) O(N) 의 시간 복잡도를 가진다.