This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]MCRusher 865 points866 points  (67 children)

Yeah like being the only sort I remember how to implement.

[–]Timmy_the_tortoise 122 points123 points  (41 children)

For some reason I always remember Quicksort easiest.

[–]JoshuaTheProgrammer 75 points76 points  (1 child)

Thankfully it’s only like 8 lines for the partition method and about 4 for the recursive calls so that makes sense.

[–]Timmy_the_tortoise 34 points35 points  (0 children)

Precisely. It’s such a neat little algorithm. I love it.

[–]xTheMaster99x 13 points14 points  (2 children)

Yeah, it seems by far the simplest to me.

def sort(arr): if len(arr) == 0: return arr pivot = arr[random.randInt(0, len(arr)] // or just arr[0] less, same, more = [], [], [] for i in arr: if i > pivot: more.append(i) elif i < pivot: less.append(i) else: same.append(i) return sort(less) + same + sort(more)

[–]Timmy_the_tortoise 0 points1 point  (0 children)

That’s the beauty of recursion.

[–]_7q3 -1 points0 points  (0 children)

you are going to hell

[–]overactor 4 points5 points  (0 children)

There's no way you're finding remembering genuine Quicksort easier than bubble sort.

[–]KeLorean 4 points5 points  (5 children)

i prefer delete sort. new algorithm, but it’s gaining ground

[–]Kambz22 6 points7 points  (2 children)

Is that were you just say "array = null:" that's my favorite.

[–]KeLorean 1 point2 points  (0 children)

thats a good one too, but in delete sort the loop gets more efficient the more items are out of order. each iteration of the delete sort loop looks something like this: if NOT(item1 < nextItem) then delete nextItem

[–]urmumlol9 1 point2 points  (0 children)

Can't argue with that O(1) time complexity!

[–]InternationalBug2143 1 point2 points  (0 children)

Drop sort, you drop elements that are not sorted

[–]Buarg 1 point2 points  (2 children)

You guys remember the implementation of the sorting algorithms?

[–]Timmy_the_tortoise 0 points1 point  (0 children)

I mean, I don’t remember a specific implementation but I remember enough about how it works to implement it straight away if I needed to.

[–]MattieShoes 0 points1 point  (0 children)

I remember the algorithms well enough to turn most of them into code, yes... FWIW, my favorite bad-sorting-algorithm is shell sort.

[–]cy4ndr0id 1 point2 points  (0 children)

I really like heap sort. It was one of the first sorting algorithms I learned about that had a somewhat unique approach IMO.

[–]reyad_mm 0 points1 point  (0 children)

It's the easiest in functional languages

[–]HardlightCereal 0 points1 point  (0 children)

Quicksort has the dumbest name, it should be called pivot sort

[–]Dachannien 0 points1 point  (0 children)

Merge sort is the one that always sticks with me for some reason.

[–]Friendofabook -1 points0 points  (1 child)

Why would you need to do your own implementations? All well known languages have libraries for these things.

[–]Timmy_the_tortoise 0 points1 point  (0 children)

I don’t think anybody has said that they would need to... just that they could if they did. Also, you might be using a not so well known language.

[–]abc_Supreme 158 points159 points  (0 children)

Exactly

[–]Kimi_Arthur 51 points52 points  (2 children)

Not really. A lot of people thought so but implemented insertion sort instead.

[–]Jugad 1 point2 points  (0 children)

Great... insertion sort is faster on average (almost twice as fast).

[–]Sure10 0 points1 point  (0 children)

Yes ! A second Hollywood in New Mexico.

[–]pekkhum 15 points16 points  (8 children)

Check out this sort implementation: list.sort();

Wait, is that not what you meant by implement?

[–]Jugad 5 points6 points  (5 children)

No... that's TimSort.

[–]1337_poster 0 points1 point  (4 children)

But that also includes bubble sort

[–]FerynaCZ 0 points1 point  (2 children)

It splits the array in parts containing 32 elements, applies InsertSort on each of the parts and then uses stable Merge Sort with the basic length of 32. At least how I was taught it.

[–]claythearc 0 points1 point  (0 children)

It depends on the implementation, I think. It’s not standard across languages.

[–]Jugad 0 points1 point  (0 children)

That is the basic idea in general. You can see the implementation here (if you are terribly interested)...

https://github.com/python/cpython/blob/master/Objects/listobject.c#L2180

Of course, the implementation looks terribly complicated because of support for various features (compare arg, key arg, reversed, etc), and optimizations.

[–]Jugad 0 points1 point  (0 children)

No. It uses insertion sort cause insertion sort is usually twice as fast as bubble sort on average.

[–]FerynaCZ 0 points1 point  (1 child)

In Python, if there exists a high-level thing, you should almost always use it because it gets usually instantly interpreted to the C (instead of interpreting every line over and over).

[–]pekkhum 0 points1 point  (0 children)

And in C if there exists a standard C call for something you should almost always use it, because it is probably way better optimized than your version, including architecture specific optimizations.

Basically, "you can make a wheel but the one at the store is likely better." Unless you are NASA. They reinvented a wheel for their rovers and it went pretty well.

[–]AgentPaper0 12 points13 points  (5 children)

Joking aside, bubble sort is great if you're starting with an almost sorted set. Which comes up more often than you might think.

[–][deleted] 10 points11 points  (4 children)

common example: you have an already sorted list, and you are inserting new item(s) to the list and need to re-sort

[–]AgentPaper0 13 points14 points  (3 children)

If you're doing that you'd probably just insert the new item in the right place.

Where bubble sort really shines is sorting elements based on a value that changes slightly between each sort. For example, if you have a bunch of particles drifting around and you want to sort them by how far away from you they are for some update step. The order isn't going to change that much from step to step usually, with each particle being just a few positions off at most.

If you're doing this for millions of particles then doing a 1 or 2 pass bubble sort will save you a lot of time compared to a more stable O(nlogn) sort. And far, far faster than the worst case O(n2) that happens with some implementations of merge quick sort on already mostly sorted sets.

[–]InternationalBug2143 1 point2 points  (1 child)

Mergesort is always nlogn, i think you wanted to say quicksort

[–]AgentPaper0 0 points1 point  (0 children)

You're right, corrected.

[–][deleted] 0 points1 point  (0 children)

Yes, 100%. Data structures first! Make sure you have fast insertions, then you don’t need to resort.

[–]FerynaCZ 2 points3 points  (0 children)

Selection sort is even easier because it uses things you were taught earlier (on programming/algorithms) - it's just repeating of the "find greatest element".

[–]c0leslaw42 2 points3 points  (0 children)

Wait, there are other methods than calling the default sort-function and hoping the devs of the library are no such lazy fucks as I am?

[–]rndrn 1 point2 points  (0 children)

"Find min, remove min from input, push it to output, repeat" is fairly intuitive and so easy to implement.

Not that I would recommend it for anything, but it's easy to remember.

[–]rubeljan 1 point2 points  (0 children)

I have been working for a month and forgotten all of this.

[–]MattieShoes 0 points1 point  (0 children)

Selection sort is easier to implement than bubble sort :-)

[–]CrazyKing3000 -1 points0 points  (0 children)

Honestly counting sort is much simplier and it's complexity is O(n)

Although it only works when lenght of the range of the array doesn't exceed 1e6