🪴Insertion Sort

orders

★ 앞쪽에 있는 원소들이 이미 정렬되어 있다고 가정하고,

뒤 쪽에 있는 원소를 앞쪽에 있는 원소들 중에 들어갈 적절한 위치를 판단하고 삽입 ★

 

① 정렬할 데이터 준비 (오름차순 가정)

→ 맨 왼쪽 첫번째 데이터 7은 그 자체로 정렬이 되었다고 판단하고, 두번째 데이터인 5가 7의 왼쪽으로 갈지, 오른쪽으로 갈지 판단(=5가 왼쪽의 어느 파트에 들어갈 지 판단)

 

7 5 9 0 3 1 6 2 4 8

 

② 오름차순을 가정하였으므로 5가 7의 왼쪽으로 이동하겠다고 판단!

 

5 7 9 0 3 1 6 2 4 8

 

③ 이어서 9가 어떤 위치로 들어갈 지 판단

→ 9의 경우는 5의 왼쪽으로 들어갈 지, 5와 7사이에 들어갈 지, 아니면 7 오른쪽으로 들어갈 지 들어갈 수 있는 3개의 후보 중에서 판단

→ 맨 왼쪽 데이터부터 비교하면서 비교 대상 데이터보다 작다면 바로 삽입! / 작지 않다면 계속 오른쪽으로 이동하면서 대소 비교 판단

 

5 7 9 0 3 1 6 2 4 8

 

④ 이어서 0이 어떤 위치로 들어갈 지 판단

→ 맨 왼쪽 데이터보다 작으므로 바로 맨 앞에 삽입

 

⑤ 마지막 원소 8까지 반복

about insertion sort

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

 

★ selection sort에 비해 구현 난이도가 높은 편이지만, 일반적으로 selection sort보다 더 효율적으로 동작한다.

 

★ 선택정렬과 마찬가지로 반복문이 두 번 중첩되어 사용. 단, 주어진 리스트의 데이터가 거의 미리 정렬되어 있는 상태라면, 매우 빠르게 동작 (최선의 경우 O(N)) 그러나 else문에 걸리지 않고 두 번째 for문을 끝까지 도는 최악의 상황을 가정한다면, 1 + 2 + .... + (N-1) = (N*(N-1))/2로 이는 Big-O Notation에 의해 O(N^2)로 표현된다. (선택정렬과 동일)

 

★ selection sort와 비교하면, selection sort의 경우 계속 the smallest element를 찾기 위해 계속 만들어지는 subarray에서 계속 대소 비교하며 찾아야 하지만, insertion sort 같은 경우 이미 정렬된 subarray를 계속 update 해가기에 selection sort보다 조금 더 효율적이라고 할 수 있다. (the selection sort repeatedly searches remaining items to find the smallest element and moves it to the correct location. whereas the insertion sort builds the final sorted list by transferring one element at a time)

 

★ selection sort vs. insertion sort

selection sort	insertion sort
finds the minimum/maximum number from the list and sort it in ascending/descending order	inserts the value in the presorted array to sort the set of values in the array
an unstable sorting algorithm	a stable sorting algorithm
for best case, worst case, and average case - time complexity O(N^2)	best-case time complexity is O(N) when the array is already sorted in ascending order. O(N^2) in worst & average case
the number of comparison operations performed in this algorithm is more than the swapping performed	the number of comparison operations performed in this algorithm is less than the swapping performed
it is less efficient than insertion sort	it is more efficient than selection sort
the location where to put the element is previously known we search for the element to insert at that position	here the element is known beforehand, and we search for the correct position to place them
the selection sort is used when - a small list to be sorted - the cost of swapping does not matter - checking of all the element is compulsory - cost of writing to memory matters like in flash memory	the insertion sort is used when - the array has a small number of elements - only few elements left to be sorted
in-place comparison sorting algorithm	insertion sort is adaptive(efficient) for data sets that are already substantially sorted; time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
the inner loop) iterates over the unsorted elements	the inner loop) iterates over the sorted elements

insertion code / image

★ pesudo-code

(sorting an array of size 'n' in 'ascending order')

① iterate from arr[1] to arr[n] over the array (not arr[0])

② compare the current element(key) to its predecessor

③ if the key element is smaller than its predecessor, compare it to the elements before. move the greater elements one position up to make space for the swapped element

 

★ key element를 subarray에 어떤 방식으로 insertion이 진행되는 지에 따라 약간씩 알고리즘 구체적 진행 과정이 다르다.

 

★ algo1) python (바로 앞의 predcessor와 비교하면서 비교 대상이 이미 정렬된 원소보다 크다면 바로 break 탈출!)

(subarray에 삽입하는 방식이 계속 부등식으로 비교하면서 계속적 swap 진행)

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

for i in range(1,len(array)): #starting from the 2nd element
    for j in range(i,0,-1):
        if array[j] < array[j-1]:
            array[j],array[j-1] = array[j-1],array[j] #swap if going left
        else: #just break if not going left
            break
print(array)

 

※ 그림 참고 ※

---

★ algo2) python

(subarray에 삽입하는 방식이 다름: subarray일부를 오른쪽으로 쏠려 놓고 삽입)

 

→ 위 그림에서 i에 해당하는 newItem을 놔두고, 일단 subarray의 오른쪽 끝쪽 loc부터 왼쪽으로 진행하면서 차례대로 newItem보다 크다면 계속 오른쪽으로 옮긴다. 그 다음에 다 오른쪽으로 옮겨두고 첫 왼쪽 남은 자리에 newItem을 할당하는 방식!

 

→ 위 algo1과 다르게 swap을 없애고, newItem보다 큰 원소들을 오른쪽 한 쪽으로 미루어두고 newItem을 빈 쪽 왼쪽에 할당하는, 즉 swap을 아예 없앤 알고리즘!

import sys
input=sys.stdin.readline
N,K=map(int,input().split())
A=list(map(int,input().split()))

for i in range(1,N):
    loc = i-1
    newItem = A[i]

    while(0<=loc and newItem < A[loc]):
        A[loc+1] = A[loc]
        loc-=1

    if (loc+1 != i):
        A[loc+1] = newItem

 

※ 그림 참고 ※

examples

🪴 <BOJ B1 24051 알고리즘 수업 - 삽입 정렬 1>

Q. 지정 저장 횟수에의 저장 원소 출력. insertion sort algo 2 유형

 

🪴 <BOJ B1 24052 알고리즘 수업 - 삽입 정렬 2>

Q. 24051 위 문제와 완전히 똑같은 유형. 다만 k번째 swap 직후 발생한 배열 내용 출력

 

🪴 <BOJ G5 24053 알고리즘 수업 - 삽입 정렬 3>

Q. 24051 / 24052 위 두 문제와 완전히 똑같은 유형. 다만 subarray 오른쪽으로 한 개씩 미는 move & newItem을 왼쪽 빈 공간에 넣는 move 중에서 도중에 변환 결과의 배열이 원래 배열과 같은 지 check

 

 

---

geeksforgeeks

이코테 2021