[알고리즘] 삽입정렬

3. 삽입정렬

data 정렬시 앞의 data들은 이미 정렬이 완료되었다는 가정으로, 비교연산 등 순회과정을 진행할때마다 적당한 위치에 data를 정렬하는 방식이다.

정렬이 되어있다고 가정하기 때문에 순회과정에서 특정 조건을 만족할 경우, 곧바로 순회를 종료한다. 이 관점에서 특정 조건에서는 삽입정렬이 매우 효율적으로 적용될 수 있다.

예를 들어, 오름차순으로 data를 정렬한다고 가정해보자.

특정 지점의 data(아래 코드에서 array[i])는 한 순회를 할 때마다, 앞서 정렬된 data들과 비교과정을 거친다.

이미 정렬되어있는 배열상태에서 비교연산을 하므로, 특정 조건을 만족한다면(array[i]가 array[i+1]보다 작은 경우, 즉 오름차순 조건이 만족되는 경우) 곧바로 연산을 종료할 수 있다.

3-1. 시간복잡도 관점

시간복잡도 관점에서 O(N^2)이므로 다소 불리한 방법의 알고리즘이긴 하다.

그러나 삽입정렬은 앞선 정렬과는 달리 특정 조건, 즉 필요시에만 data를 바꾸는 정렬이다.

다만, 동일한 O(N^2)의 정렬 알고리즘에서는 가장 빠르고 효율적이며, 특히 데이터가 이미 정렬되어있는 상태에서 사용할 경우 그만큼 빠르게 원하는 결과를 얻을 수 있는 방법이다.

##selected array
## 1 2 3 4 5 6 7 8 9 10

array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
arrayLength = len(array)

for i in range(0, arrayLength-1):
    j = i
    while array[j] > array[j+1]:
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp
        j = j-1

print(array)

3-2. 참조강의

삽입정렬
https://www.youtube.com/watch?v=16I9Z7bS1iM&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=4