23 Comments

  1. In loop 1 why do you just leave the one hanging?

    In loop 2 why does the 10 and the 1 connect??? Thats a gap of 1 not a gap of 2.
    Also why do you just leave 9 alone?

    This is important info that you just kinda skipped…

    Reply
  2. Your explanation helped me understand the selection sort very well but I believe you might have made a mistake on your first round when gap = 4. When gap = 4 it should have compared 7 and the 1. After comparison the 7 would then be inserted to where the one is and the loop should run one more time after that comparing the 3 and the one. Effectively putting the 3 where the seven originally was at the start and replacing the 3 at the start of the array with a 1. I may be wrong but after tracing the algorithm that is the answer I got and the shell sort worked.

    Reply
  3. Simply, by looking at at, I can say shell sort is least efficient compared to other methods. I have find the exact reason.
    I think binary tree is efficient in sorting. I don't have to do so many comparisons and swaps. I am looking for multithreaded binary tree sorting in java / javascript

    Reply
  4. This video doesn't actually explain the algorithm correctly. Shell sort doesn't take 2 elements at a time like this. It simply takes all elements that are a certein gap size appart, and then performs an insertion sort on these. Thus, the final insertion sort only ever has to move elements that are very close together. How close depends on the previous gap size.
    Also, the time complexity of shell sort is a bit harder to describe, as it depends on the gap sizes used. Halfing the gap size each time will indeed result in the worst case being O(N²). However, many different gap sizes have been tested in the past. Some have a worst case of O(N^3/2), others O(N^4/3). Some number sequences for gap sizes have an unknown time complexity, but tests show that they are even better than that!

    Reply
  5. Why does this decrease the time complexity? How many ops do you have to spend swapping? Which gap size should you use? Why is the complexity what it is? Great intro to the algorithm and thank you for creating the content… would love to see more detail.

    Reply

Post Comment