선택 정렬 & 삽입 정렬

정렬

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다.

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

 

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

1. 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 가장 앞의 데이터와 바꾼다.
2. 앞선 1번의 과정을 반복한다.
3. 정렬되지 않은 데이터가 하나가 남은 경우 처리하지 않아도 완성이 된다.

array = [7, 3, 5, 4, 2, 6, 1, 0]

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)

 

선택 정렬의 시간 복잡도

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

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

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

이는 빅오 표기법에 따라서 O(N**2)이라고 작성한다.

 

삽입 정렬

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

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

1. 앞쪽의 원소는 이미 정렬되어 있다고 가정하고 다음 데이터가 어디 위치로 들어갈지 판단한다.
2. 다음 데이터를 왼쪽 데이터와 비교하여 위치를 판단한다. (현재 위치가 자기 위치일 때까지 왼쪽 데이터와 비교)

array = [7, 3, 5, 4, 2, 6, 1, 0]

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)

 

삽입 정렬의 시간 복잡도

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

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

• 최선의 경우 O(N)만큼의 시간 복잡도를 가진다.

 

Reference