선택 정렬, 삽입 정렬

선택 정렬

가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸고

계속 반복하며 정렬하는 방법

 

 

파이썬으로 구현한 선택 정렬 코드

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

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)

 

이 코드에서 스와프를 사용했는데

스와프는 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 역할을 한다.

 

 

스와프 코드

array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

결과

[5,3]

 

선택정렬의 시간 복잡도

연산 횟수는 N+(N-1)+(N-2).....+2 이므로  O(N^2) 만큼의 시간 복잡도를 가지고 있다.

이해하기 어려우면 for 반복문이 두 번 사용됐으니까 이런 결과가 나왔다 생각하면 된다.

 

 

삽입 정렬

특정 데이터를 적절한 위치에 삽입하는 알고리즘이다.

삽입 정렬은 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 생각한다.

정렬된 데이터 리스트에서 적절한 위치를 찾고, 그 위치에 삽입이 된다.

 

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높지만 실행 시간 측면에서 유리하다는 장점이 있고,

데이터가 거의 정렬되어 있을때 매우 효율이 높은 알고리즘이다.

첫 시작은 두 번째부터 시작된다.

그 이유는 첫 데이터는 그 자체로 정렬이 되어있다고 생각하기 때문이다.

1. 7이 들어올 자리를 보고 3보다 크므로 3 뒤에 저장이 된다.

2. 2가 들어올 자리를 보는데 3,7보다 작으므로 3 앞에 저장이 된다.

계속 반복하며 정렬을 한다.

 

파이썬으로 구현한 삽입 정렬 코드

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

for i in range(1, len(array)):
    for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

 

삽입 정렬의 시간 복잡도

반복문이 2번 중첩되어 사용되었다.

시간 복잡도는 O(N^2)이다.