삽입정렬

작동방식

위의 동영상에서 알 수 있듯, 삽입정렬은 오른쪽에 있는 요소를 자신보다 작거나 같은 요소를 만나기 전까지 왼쪽으로 쭉 swap하는 것이다.

코드(python3)

def swap(list, a, b) :
  temp = list[b]
  list[b] = list[a]
  list[a] = temp

def insertSort(arr) :
  for i in range(len(arr) - 1) :
    if (arr[i] > arr[i+1]) :
      swap(arr, i, i+1)
      for z in range(i, 0, -1) :
        if ( arr[z-1] > arr[z] ) :
          swap(arr, z-1, z)
        else :
          break

시간복잡도

최선의 경우 🚀​

배열이 이런식으로 되어있는 상태에서는 그냥 좌우만 비교하면 되고 swap은 일어나지 않는다. [원소의 개수 – 1] 만큼 비교가 일어나기 때문에 시간복잡도는 O(n)이 된다.

최악의 경우 🚡​

배열이 위처럼 되어있다면, 14 -> 12 / 11 -> 14 -> 12 / 10 -> 14 -> 12 -> 11 …. 이렇게 쭉 swap이 일어날 것이다. 그래서 swap하는 횟수는 1 + 2 + 3 + 4 + 5 + … + 9이 되고, 누적 합 공식에 의해서 {n(n-1) \over 2} = O(n^2)가 된다. 가급적 배열의 크기가 큰경우에는 안쓰는게 좋을것 같다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

Peak 찾기

Peak 찾기