The Sorter

[LookiLukas]

.. but for me it´s n*log(n) !

[wfhbright]

This song became the anthem of our CS department lol

[opliik]

You forgot about mergesort?

[twistor96]

I loved it!

[MrDoctorTomas]

I am just putting it on my ipod, can I?

[lximilo]

Im so using this for teaching the new students next semester ^^

[mlittman]

great! let me know how it works out. (if you practice, you can even sort cards that way.)

[JimbitoCono]

@mlittman

Actually , our assistant professor showed us this video :D

And it worked out fine , for me!

[d2513850]

I like this song!

[gamernabil]

this is an intersting way 2 explain

[mlittman]

thanks! (who was the prof? UIUC is a great school!)

[giorgos11235]

awesome

[fotis156]

this is awesome!!

[barrikid]

Awesome Video!

[Faceless989]

epic!

[AtomicNerd001]

and i thought i was a nerd 0.o

[ray0kun]

Don't worry, you are.

[AtomicNerd001]

wow -_-

smart guy 'eh?

[nukz0r]

cringe

[Da1nOnlyBKB]

O_o

[szeb06]

wow! i loved that music... awesome!

[benutzer2]

That's pretty awesome, gg vid lol.

[lolbensuckslol]

yyuyu

[MonoCabron123]

xDDDDDDDDD thanks a lot xD

[jazter1]

Es como el plaza sesamo de la progrmacion

[mlittman]

Gracias!

[gusgle]

GENIAL!!!

[HackPirate]

oui :) je suis d'accord

[sg100000000]

Isn't n times through a list linear rather than quadratic?

[mlittman]

searching through a list of length n is linear (n). Repeating that operations n times is quadratic (n times n = n squared).

[ambir]

SOLID! I WANT MORE!

[shoaibi]

great!!!! just great! wish if they could teach us like that at college

[bashir444]

a dell made in texas lol i love it. learning this night before midterm. way better than reading books

[JohnsJava]

god thats cheesy, informative, but cheesy...

[shizzle5150]

this is awesome! I like the original version but this is ace.

[aphididae]

thats hilarious

[80amnesia]

man that was funny :)

[andrewsmithty]

dude... that was fun ... :)

but yeah i'd rather use heapsort... which i can count on... no worst case scenario...!

[newcoleco]

well, with the heap sort, if your list is already sorted, the algorithm do not detect it and mix up the list to build the heap. In my opinion, it's very bad.

We can improve quicksort speed by using the insertion sort algorithm to sort less than 7 items, rather than continuing by choosing a pivot and etc.

[arcfenix]

Awesome ! :P i learnt quick sort instantly lolz

[CheeZe477]

So awesome.

[Lem0nAndLime]

Firstly,excellent fun breakdown of the 2 sorts.

[Lem0nAndLime]

Secondly, in ur QuickSort, choosing a good middle value pivot by random to reduce the number of swaps&compares has some luckyness to it.Recursively do the following.

[Lem0nAndLime]

There's a technique called median of 3 that's sorts asc/dsc the middle,start and end index values to obtain a better middle value

[mlittman]

L&L: Thanks for the informative comments. Yes, I realize there is more to sorting than I covered in that song! In my class, I do touch on some of the other sorts, although I don't go into depth about effective ways to choose pivots (it's not that kind of class). As for shell sort, I always thought it was n x sqrt(n), but wikipedia says it can be made n log^2 n. I don't know how that analysis goes, though.

[Lem0nAndLime]

When you program the QuickSort a common method is simple choose the right most index as the pivot. However, if the set is in ascending or decending order and the sort does the vice sort of this, then this can degrade the QuickSort to O(N^2). Precautions such as knowing the set will be random or using the median of 3 will prevent this.

[Lem0nAndLime]

If one suggestedto writing/using a random generator to choose each pivot,this would certainly slow the Quicksort, due to all the computation overheads in this.

(As a wild say, use slow sorts( O(N)^2 )ones on fewer than 1000 items, Advanced Sorts on anything greater.) Though Moores Law and computation speed is everly increasing and slow sorts are getting seemingly less slow.

[Lem0nAndLime]

If the data isn't random, such as Quicksort Ascending a roughly Decending Set, then a HeapSort is better, or Radix, or MergeSort could possible but the 2 later use more memory also all can be conceptually harder to understand but each are O(N*logN), but these sorts O(N*logN) are minutly slower, then an a QuickSort at (N*logN) best.

[Lem0nAndLime]

Minute diffrence meaning more comparisons, also, if MergeSort is implemented using Recursion also create minor speed diffrences. But as I said better than QuickSort during its Worst Case Scenario.

[Lem0nAndLime]

mlittman for introclasses it will be good to teach basic sorts such as, bubble sort, selection sort then insertion sort. If you fancy squeezing an advance sort, try the Shell sort, as its an clever expansion of Insertion Sort with nice visualisation of its working. Also, its Order(n*logn)^2 slower than QSort.

[x0utsideofthis]

OmfG THys Is SO0O0OOOoO gHEY.

[lua121]

ehauheiheauhaea, =), very good...

[KlokJammer]

No, quicksort is bad! Its worst case is quadratic O(n²). Introsort and Mergesort are better than both. All my professors discourage quicksort greatly.

[mlittman]

I hadn't heard of introsort, but the wikipedia entry seems misleading. Quicksort with a random pivot is expected n log n and the chance of being Omega(n^2) is exponentially small (facts not even mentioned on the page). Quicksort is fast and lightweight and an astonishing improvement over selection sort. One can engineer it to squeeze as much performance out of it as possible, but that's not really a topic for an intro class.

[galanodell88]

indeed it is lol. poor selection

[MeRc3n4rY]

holy mother of jesus, thats hilarious!