0
\$\begingroup\$

Can following code be called insertion sort? I tried implementation according to my underdtanding...

#include<iostream>
void insertionSort(int* array,int length){
       for(int unsortedIndex=1; unsortedIndex<length;unsortedIndex++){
           for(int sortedIndex=0; sortedIndex<unsortedIndex; sortedIndex++){
            if(array[unsortedIndex] < array[sortedIndex]){
                int temp = array[sortedIndex];
                array[sortedIndex] = array[unsortedIndex];
                array[unsortedIndex] = temp;
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ have you actually checked that it sorts with decently large inputs (>10)? \$\endgroup\$ – ratchet freak Jan 16 at 9:27
  • \$\begingroup\$ no but will do now n let you know \$\endgroup\$ – Deepeshkumar Jan 16 at 9:28
  • \$\begingroup\$ yeah it works fine \$\endgroup\$ – Deepeshkumar Jan 16 at 9:30
1
\$\begingroup\$

Yes, it is a variant that does the inner loop from the opposite side than the canonical version.

This has the effect that you do a lot more comparisons than you would otherwise because you cannot early out as soon as you find where the element should be inserted to.

Now for the nitpicks:

There is no need to #include<iostream> for this.

Indentation isn't consistent.

\$\endgroup\$
0
\$\begingroup\$

This is not the standard insertion sort algorithm. Your algorithm has one feature in common with insertion sort, which is that it finds a small element and puts it at the front of the list. However, your algorithm does that by performing one swap, whereas the standard insertion sort does that by shifting all of the larger sorted elements over.

One result of this difference is that your algorithm does not have all of the properties of insertion sort. In particular, your sorting algorithm is not stable. Stability is more of a concern when you are sorting objects rather than primitive ints, but still, this property is significant enough for me to consider your algorithm to fail to qualify as a variant of insertion sort.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.