Sorting Algorithms.

Discussion in 'Software & ROM Hacks' started by laingsoft, May 22, 2015.

  1. laingsoft

    laingsoft Formerly SteamDNT

  2. ttsgeb

    ttsgeb Breaker of Everything Staff Member

    My God, sleepsort is beautiful. I just... It's so perfect.
     
  3. grossaffe

    grossaffe President Groosevelt Staff Member

    sleepsort makes me want to cry.

    I'm a fan of heapsort for being simple, very fast, and low memory requirement. Mergesort is great for also being very fast and can be made parallel for a speed boost in multi-core systems.
     
  4. laingsoft

    laingsoft Formerly SteamDNT

    Heapsort is really a beautiful algo. When I first wrote my heap implementation for a data structures class, our prof didn't mention it until well after we had finished. At that point she was like "So, now if you dump everything out of your heap, do you notice anything about the data?" I do love it.

    Mergesort always irked me for some reason. Maybe it's the recursion. I just always leaned more towards quicksort. Usually when I have to sort something I end up using quicksort rather than mergesort if the language doesn't have a built in sort function.
     
  5. grossaffe

    grossaffe President Groosevelt Staff Member

    quicksort has the issue of being an O(N^2) function, however I have made use of it in my laziness since it's built into C's stdlib.
     
  6. laingsoft

    laingsoft Formerly SteamDNT

    It's only ever O(n^2) if the list is already sorted and you don't choose the pivot properly. But yeah I guess.

    We are pretty spoiled with libraries :confused:
     
  7. grossaffe

    grossaffe President Groosevelt Staff Member

    It's always O(N^2) because "Big O" notation specifies worst-case scenario. The average case is nlog(n) like the other sorting algorithms, though. Kinda like heap insertion is O(nlog(n)) but its average case is actually a constant (at least I think it was the insertion that was a constant at about 2 percolations no matter the size of the heap).
     
  8. laingsoft

    laingsoft Formerly SteamDNT

    Ah, Well it was a long time since I did my algorithms course, you are right.

    And I believe heap insertion worst case is O(logN) not O(N logN), and deletions are also O(LogN)
     
  9. grossaffe

    grossaffe President Groosevelt Staff Member

    I do believe you are correct. I think I had nlog(n) in my head from the sorting.
     
  10. grossaffe

    grossaffe President Groosevelt Staff Member

    My brother is a fan of the slow sort.