DEV Community 👩‍💻👨‍💻

Discussion on: Quick sort vs. Insertion sort

Collapse
 
cicirello profile image
Vincent A. Cicirello

Cool visualization. Your insertion sort isn't actually insertion sort though. It looks like a cross between insertion sort and bubble sort. Insertion sort doesn't do swaps. Instead, just before the inner loop it should store the next element to be inserted in a temporary variable. The inner loop should then shift elements until insertion point found. Then just after inner loop but still inside outer loop, the element saved earlier is inserted.

By shifting rather than swapping, insertion sort does roughly a third of the work that your version does, at least in terms of assignments (same number of comparisons). A swap involves 3 assignments, whereas a shift is just 1 assignment.

Collapse
 
abagames profile image
ABA Games Author

As you pointed out, it is not an exact insertion sort. It's a hybrid with bubble sort due to the lack of a 'set' instruction that directly sets the array's value.