0

Here are the algorithms for Insertion Sort. The first one uses shifting mechanism for placing the value in the left sorted part. The second one swaps the consecutive values until the left portion becomes sorted.

  1. By Shifting

    function insertionSort(array A) for i from 1 to length[A]-1 do value := A[i] j := i-1 while j >= 0 and A[j] > value do A[j+1] := A[j] j := j-1 done A[j+1] = value done

  2. By Swapping

    function insertionSort(array A) for (i =0; i<N; i++) for(int j=i; j>0; j--) if(less(A[j], A[j-1])) exch(A, j, j-1) else break; done done

Wikipedia says this about the run time analysis of Insertion Sort:

Worst case performance: O(n^2) comparisons, swaps Best case performance: O(n) comparisons, O(1) swaps Average case performance: O(n^2) comparisons, swaps

which fits with the algorithm 2. But in case of algorithm 1, the analysis becomes:

Worst case performance: O(n^2) comparisons, O(n) swaps Best case performance: O(n) comparisons, O(1) (no) swaps Average case performance: O(n^2) comparisons, O(n) swaps

Please clarify the meaning of shifting and swapping.

Improve this question
7
  • The above two algos are exactly the same, assuming exch(A, j, j-1) exchanges position j and j-1 in the array A Commented Nov 26, 2013 at 18:23
  • further, unless it utilizes a binary-search of the previously sorted segment, it also isn't even a proper insertion sort algorithm. I.e. neither of these are proper insertion sorts. Commented Nov 26, 2013 at 18:25
  • 1
    Hmm? Insertion sort doesn't require a binary search for the insertion location. Indeed, doing that would blow the O(n) best-case performance which is really the only thing insertion sort has going for it. Commented Nov 26, 2013 at 18:26
  • @Sneftel the binary-search of the previously sorted segment is what keeps insertion sort from blowing up into O(N^2) comparisons. We may be talking about different adaptations of the same algorithm, admittedly. Ex. you can implement insertion-sort in literally a two-line for-loop using std::upper_bound and std::rotate using the standard library. Commented Nov 26, 2013 at 18:31
  • Insertion sort of an already sorted list is O(n) because each element is only compared to the one before it. If each element were compared with log k elements to determine the insertion location, the resultant performance would be O(n log n). See Knuth, Vol. 3, p.80. (Normal) insertion sort doesn't have a binary search. Commented Nov 26, 2013 at 18:40

3 Answers 3

Reset to default
3

To answer the general question: shifting is moving all elements by one position. Swapping is exchanging the elements at two distinct indexes.

Consider the following array:

a b c d e f

and suppose we wanted to put element e at the second position.

Shifting With shifting, the array becomes

a e b c d f

(The sequence b c d was shifted one to the right, making room for e to be inserted.)

Swapping With swapping, the array becomes

a e c d b f

(The elements b and e swapped places.)

In the case of the specific algorithms you posted, the first one simply moves elements to the right until it finds the place where the new element goes and then inserts it. The second one puts the element at the end and then repeatedly swaps the new element with the previous element until it is discovered to be in the correct position.

EDIT: Regarding the differences in performance analysis of the two algorithms: I think the analysis of the shift-based algorithm is flawed because it does not count the work of shifting O(n) elements (worst- and average-case performance) during each iteration of the outer loop. Granted that shifting is neither comparison nor swapping, it nevertheless represents work (about a third as much as swapping, but constant multipliers don't matter in big-O calculations.)

If one (incorrectly) ignores the cost of shifting, the differences are easily explained. In the case of shifting, each iteration of the outer loop requires O(n) iterations of the inner loop, but only a single swap (once the insertion location has been found). The swap-based algorithm, on the other hand, does a swap for all but the last comparison performed each iteration of the outer loop.

P.S. I don't see two separate performance analyses in the Wikipedia page on insertion sort, nor do I see the swap-based implementation.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Ted Hopp, I know that. What I'm not getting is the two different analysis for same Insertion sort.
@Atinesh - In most languages, creating space to temporarily store a variable is simply using another position on the stack and is essentially free. If your array elements are complex structures and you're unfortunate enough to be using a language where assignment involves copying the entire structure in memory, then shifting will be cheaper than swapping. But in either case, the big-O analysis will be the same; the overhead shows up as coefficients, not as increased asymptotic complexity.
I think 'swaps' will be ambiguous term here in this reference. Writes will be more accurate. Please see my ques below and tell me what do u think about the answer.
1

Swapping means to exchange the places . Example : 1 2 3 4 5 swap 2nd loc and 5 loc will give output : 1 5 3 4 2.

Shifting means simply shift from the current location. Example : 1 2 3 4 5 Shift by two places in left : 3 4 5 empty empty.

Insertion sort uses shifting. It stores the element to be inserted in some variable, finds the correct position of the variable and shifts by one place to the right. In your case you are shifting by swapping adjacent elements which is not necessary.It is an overhead.

Improve this answer

1 Comment

Both ways are correct. I am trying to say that during insertion sort you should use shifting method instead of swapping method. Because during swapping an extra temporary variable is created and destroyed during every swap. It takes extra time.
0

What I'm saying is Analysis that wikipedia gave i.e.

Worst case performance: O(n^2) comparisons, swaps Best case performance: O(n) comparisons, O(1) swaps Average case performance: O(n^2) comparisons, swaps

is correct, According Algo 2. But in major text I found Algo 1 for Insertion sort. But in this case analysis will become.

Worst case performance: O(n^2) comparisons, O(n) swaps Best case performance: O(n) comparisons, O(1) (no) swaps Average case performance: O(n^2) comparisons, O(n) swaps

What to consider in general case. Shifting based algo or totally swapping based algo. What I've seen in books(CLRS) and my teacher also told me shifting based Insertion sort Algo. But in this case total no. of swaps will become O(n). I read somewhere that we prefer Selection sort over Inseertion sort when we are concerned with no. of writes. Selection sort requires O(n) writes and Insertion sort requires O(n^2) writes [Swap].

Now consider this ques, this will clear my doubt

Q. As against to the conventional Insertion sort algorithm. If we use Binary Search to find the position of new element, the time complexity of this versin will be

Part I a)Will remain O(n^2) in worst case. b)Will become O(n logn) in worst case.

Part II a)Total no. of writes will remain O(n^2) b)Total no. of writes will become less as comapred to O(n^2)

Improve this answer

8 Comments

Whether you are concerned with number of writes or number of swaps, the big-O analysis will be the same; doubling (or tripling) the number of writes in the swap version has no effect on the asymptotic complexity. As to the new question you've posted regarding binary search, see the discussion under "Variants" in the Wikipedia article "Insertion sort".
@TedHopp, But why. asymptotic analysis is concerned with total no. of comparison. It doesn't have any relation with writes.
The number of writes is 1 for each element shift and 3 for each exchange. Since coefficients do not affect big-O asymptotics (O(3n) == O(n)), the complexity analysis is unaffected. (This is not to suggest that coefficients are irrelevant to performance; they most definitely are important in practice.) If you want to affect the asymptotic complexity, consider using a skip list instead of an array or one of the other variants described in the Wikipedia article.
"asymptotic analysis is concerned with total no. of comparison. It doesn't have any relation with writes" - The last sentence is wrong. There is a very strong relationship between the number of comparisons and the number of exchanges and/or shifts, as described in my answer. And there's a very strong relationship between these and the number of writes, as described in my previous comment.
Wiki says "Binary insertion sort employs a binary search to determine the correct location to insert new elements, and therefore performs ⌈log2(n)⌉ comparisons in the worst case, which is O(n log n). The algorithm as a whole still has a running time of O(n^2) on average because of the series of swaps required for each insertion". Now they are considering swapping based algo.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.