Page 1 of 1

Understanding Insertion Sort

#1 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10185
  • View blog
  • Posts: 37,603
  • Joined: 27-December 08

Posted 17 June 2010 - 10:09 PM

The concept of Insertion Sort is very intuitive, probably more so than Selection Sort. Basically, we are given an array or List of some sort. We start at element 1 and essentially pull it out of the list. We then move all the elements before it down until we have a place to insert it. So let's go ahead and look at some pseudo-code:
insertionSort(array x){
  if(x.length < 2) end //we have 0 or 1 elements in the array

  for i = 1 to x.length-1, incrementing i = i+1 on each iteration
       temp = x[i] //pull out our element
       j = i-1 //start at the element next to our placehold and work forwards

       //shift the elements to the right until we find 
       //a place to insert
       while j >= 0 AND x[j] > temp
            x[j+1] = x[j] 
            j = j-1
       end while

       x[j+1] = temp //insert our element
  end for
}



We see that with an array, insertion sort does a lot of swapping of elements. However, with a Linked List, the swapping doesn't exist as Linked Lists are stored with relative positioning. So basically, we just have to insert the temp element back into the List at the appropriate index.

When we evaluate the Big-O of Insertion Sort, we get O(n^2). Our outer for loop takes linear time, iterating through n-1 elements. The inner loop also iterates through j elements worst case, which makes it linear n. So n*n --> O(n^2).

Is This A Good Question/Topic? 0
  • +

Replies To: Understanding Insertion Sort

#2 mohaidriss  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 29-September 11

Posted 29 September 2011 - 08:29 AM

Hi,

Your code is accurate, it helped me understand the insertion sort algorithm. However, a small mistake in your code is that the while's condition should be j >= 0 rather than j > 0.

I have manually checked and I detected it.

Thank you,
Mohamed
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1