1

Which sorting method will be the fastest when the list is already sorted? All of the sorting algorythms like: [1] bubble sort, [2] modified bubble sort and [3] insertion sort in best case scenario will perform at O(n). So they supposed to be all equally fast. When I try to solve example sorting problem I see that really all of them perform at O(n). Then I saw a graph that insertion sort will be faster than two others (it's here: https://www.toptal.com/developers/sorting-algorithms/nearly-sorted-initial-order). I'm wondering if it's true for already sorted data like for example list = 1, 2, 3, 4? I think they're equally fast - am I right?

Thanks for help!

BloodyMary
  • 173
  • 13

1 Answers1

0

If it's already sorted, then probably just something that goes through every element of the list to check that it's in proper order. So O(n) yeah.

If you want proof, you could write out bubblesort/modified bubblesort/ insertion sort then see what happens in the case that nothing needs to be sorted.

EDIT:

Also, like you said, it's probably modified bubblesort. (Most similar to a basic sorted? check)

Which sort algorithm works best on mostly sorted data?.

Similar question here.

TedTran2019
  • 887
  • 5
  • 15
  • The previous topic was closed and it was generally about "most sorted data", and not totally sorted data (even if that's similar case). I checked it in Python and I've got 0.000000873 s for insertion, 0.000002025 s for bubble sort and 0.000000854 s for modified bubble sort. Here modified bubble sort wins, but in the topic above most people are convinced that insertion sort will be faster (and the link that I provided also supports this). So I'm still confused which one is really faster. – BloodyMary Oct 19 '19 at 23:10
  • I guess whatever is most similar to a sorted check and has the least frills attached is going to be the fastest. Ie. whatever just goes from start to end of array, checking if they're in sorted order. Now that you mention it, I think that's actually modified bubblesort. Because all it does is check the all adjacent elements if they need to be swapped, and if not, moved on. And if there zero swaps, just break. My bad, I kind of brushed over because I googled it first and saw that there was an extremely similar question. – TedTran2019 Oct 19 '19 at 23:25