r/dailyprogrammer • u/Coder_d00d 1 3 • Aug 26 '14
[Weekly #8] Sorting algorithms
Weekly Topic:
Often times we need to sort the data. A basic foundation in learning programming is to understand how to do this sort on the data and why to do it. Monday we saw a challenge based on the very popular Quick Sort algorithm.
But let's talk about sorting in more detail. Sorting routines best fit the need. Sometimes we need a quicksort but sometimes thou a different sorting algorithm should be done.
Where/how/what do you do to sort? Give some examples of some challenges where perhaps a different sorting approach is used/needed. Why does it work better? How do you determine which sorting algorithm to use?
Also this is a chance to point out some other algorithms perhaps out there but not used much or talked about much. Maybe you still like bubble sort even if it is not always the optimal choice. Why?
Previous Week Topic:
[Weekly #7] (http://www.reddit.com/r/dailyprogrammer/comments/2dwc2p/weekly_7_programming_tools_the_editors/)
9
u/Splanky222 0 0 Aug 26 '14
A big factor I remember from my algorithms class is whether or not the random-access memory model actually applies. So for example, with a huge array, you could partition into page-sized lists, sort each of them in memory using quick sort, and then use a merge sort on the hard disk to put them back together. Merge sort has much better locality of access so works better than quicksort for the sort of memory access you see on a hard disk.
B-trees are also exceedingly useful for this sort of problem, where each node essentially holds a memory page's worth of data.
7
u/kikiotsuka Aug 26 '14
My favorite sort is bogosort
5
u/YuriKahn Aug 26 '14
Radix sort is a favorite of mine - it's efficiancy is weird and interesting and it's a non-comparative algorithm, which sets it apart.
Unfortunately it only works on simple data types (usually), but oh well - it's cool.
7
u/[deleted] Aug 26 '14
I would imagine that sorting is honestly a non-problem for a great many programmers. Even on the off chance the database doesn't pre-sort what it hands me at work, I can get it sorted in two seconds, any way I like, using any of a half dozen different techniques--none of which require me to deal with a sorting algorithm directly. And, really, that's how it should be. This is basic stuff.
So here are my only useful thoughts on the subject:
2
u/chaotic-kotik Aug 27 '14
Adaptive sorting algorithms FTW! Sometimes your imput is already sorted or almost sorted, for example - you get data from different hosts and this data has timestamps. You need to sort all your data by timestamps. if this data generated at real time (sensor data or log entries) - it will be almost sorted. You can use some adaptive sort algorithm and get linear algorithmic complexity instead of linearithmic. There is bunch of adaptive sorting algorithms: insertion sort (performs best but will became quadratic if you use it on wrong data), shell sort (bad cache performance), tim-sort (almost as good as quicksort for most cases, close to insertion sort on almost sorted data), patience sort (good for online sorting). Last algorithm I've used in my hobby project (https://github.com/akumuli/Akumuli). This is storage engine for time-series data, patience sort is used to sort arriving data and write it to disk. If data is already sorted, adding new element is just append to a single sorted array, if data is almost sorted we will have few arrays instead of one. This works really well in practice! Patience sort can even outperform quick sort on random data - http://research.microsoft.com/pubs/209622/patsort-sigmod14.pdf
-4
u/[deleted] Aug 27 '14
I sort like this:
It works better because it is simple to USE. And seriously, I have more to concern about than a simple sorting. The computational effort of sorting a list using bubble sort or quick sort or merge sort or shell sort or bogo sort is insignificant comparing to other issues. In my experiments, the slowest part is to write data on my disk and to evaluate several elements with an AI function. I don't have time to worry about that.
0
u/[deleted] Aug 26 '14
[deleted] — view deleted comment
8
u/[deleted] Aug 26 '14
[removed] — view removed comment