Insertion Sort

Insertion Sort

Sorting Problem

Input: A sequence of n numbers <\(a_{1}, a_{2}, ..., a_{n}\)> Output: A permutation (reordering) of the input sequence, <\(b_{1}, b_{2}, ..., b_{n}\)>, such that \(b_{1} \leq b_{2} \leq ... \leq b_{n}\) Instance: <7, 10, 4, 5, 2>

Background

Consider the following observations:

• A list with one element is sorted
• In general, if we have a sorted list of k items we can insert a new item to create a sorted list of size \((k+1)\) For example, consider this sorted array containing of eight sorted entries.

[5, 7, 12, 19, 21, 26, 33, 40]

Suppose we want to insert 14 into this array leaving the resulting array sorted

1. Starting at the back, if the number is greater than 14, copy it to the right
2. Once an entry less than 14 is found, insert 14 into the resulting vacancy (swap)

Algorithm

For any unsorted list:

• Treat the first element as a sorted list of size 1 Then, given a sorted list of size \(k-1\)
• Insert the \(k^{th}\) item in the unsorted list into the sorted list
• The sorted list is now of size \(k\)

Implementation & Time Complexity

template <typename Type>
void Insertion_Sort(Type *_array, int _n){
  for(int i=1; i<_n; i++){//
    for(int j=i; j>0; j--){//
      if(_array[j-1]>_array[j]){
        std::swap(_array[j-1], _array[j]);//
      }
      else{
        break;
      }
    }
  }
}

From inside to out: \(\Theta(1) O(i) O(n^2)\)

• Total: \(O(n^2)\)

Avoid Expensive Swapping

Now, swapping is expensive, so we could just temporarily assign the new entry

• this reduces assignments by a factor of 3
• speeds up the algorithm by a factor of 2 To minimize implementation time, instead of swap, we try for ‘tmp’ variable. For asymptotic analysis, there is no difference.

Pseudo Code

Insertion-Sort(A)

for j=2 to A.length
    key = A[j]
    // Insert A[j] into the sorted
    i = j - 1
    while i>0 and A[i] > key
      A[i + 1] = A[i]
      i = i - 1
    A[i + 1] = key

(without Swap): Implementation

template <typename Type>
void Insertion_Sort_without_Swap(Type *_array, int _n){
  for(int i=1; i< _n; i++){
    Type tmp = _array[i];
    for(int j=i; j>0; j--){
      if(_array[j-1]>tmp){
        _array[j]=_array[j-1];
      }
      else{
        _array[j]=tmp;
        break;
      }
    }

    if(_array[0]>tmp){
      _array[0]=tmp;
    }
  }
}

source “K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 7-1 삽입 정렬 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...