# Tagged Questions

For questions about sorting algorithms and their speed and complexity.

10k views

### Quicksort and middle pivot

I am having a head ache understanding quicksort with middle pivot. I found lot of explanations about using left most or right most, but not many about a middle one. Can I safely assume these?: If ...
188 views

### What kind of algorithm could be used to produce an ordering which maximizes # of satisfied 'less than' constraints?

Let's say I have a set of items {e1, e2, ..., en}, and I also have a set of constraints {c1, c2, ..., cm}, with ci := ej appears before ek, for some j and k. I want to produce an ordering of my items ...
3k views

### I'd like to write an “ultimate shuffle” algorithm to sort my mp3 collection

I'm looking for pseudocode suggestions for sorting my mp3 files in a way that avoids title and artist repetition. I listen to crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. singing old ...
4k views

### Applications of heapsort [closed]

Heapsort is a sorting algorithm that has a time complexity of O(nlogn), and performs sorting using O(1) space complexity. However, I know that because it's unstable, it doesn't find many applications (...
613 views

### Does this version of insertion sort have O(n) complexity for best case?

for ( i = 1 ; i <= N ; i++ ) { for ( j = 0 ; j < i ; j++ ) { if ( arr[j] > arr[i] ) { temp = arr[j] ; arr[j] = arr[i] ; for ( k = i ; k > j ; k-- ) ...
5k views

### What are the most popular sorting algorithms in practice? [closed]

Although I suspect the answer to this question may be something along the lines of "popularity is irrelevant; each algorithm has its trade-offs", I'm interested in a list of popular sorting algorithms ...
376 views

### How important is understanding the coding behind sorts?

First off, if this is in the wrong place I apologise. I wasn't too sure on which of the Stack Exchange sites to ask it. I am studying Software Development at university, on a one year conversion ...
874 views

### Should I calculate hotness of a post on request or pre-calculate it?

Here is the Reddit's hot algorithm: cpdef double _hot(long ups, long downs, double date): """The hot formula. Should match the equivalent function in postgres.""" s = score(ups, downs) ...
7k views

### Help understanding MapReduce Sort example

From Section 5.3 of Google's paper describing MapReduce. "A Map function extracts a 10-byte sorting key from a text line and emits the key and the original text line as the intermediate key/...
3k views

### Fastest Haskell library sort implementation

I am implementing an application in Haskell and, for sorting, I use the library function Data.List.sort. However, I was wondering whether this is the fastest sort implementation in the Haskell ...
6k views

### How to handle sorting of complex objects?

How would one sort a list of objects that have more than one sortable element? Suppose you have a simple object Car and car is a defined as such: class Car { public String make; public ...
962 views

### About insertion sort and especially why it's said that copy is much faster than swap?

From Lafore's "Data Structures and Algorithms in Java": (about insertion sort (which uses copy + shift instead of swap (used in bubble and selection sort))) However, a copy isn’t as time-consuming ...
883 views

### Efficient way to sort large set of numbers

I have to sort a set of 100000 integers as a part of a programming Q. The time limit is pretty restrictive, so I have to use the most time-efficient approach possible. My current code - #include<...
516 views

### Type of AI to tackle this problem?

I posted this on stackoverflow but want to get your recommendations as well as a user on overflow recommended I post it here. I'm going to say from the beginning that I am not a programmer, I have a ...
838 views

### Data structure: sort and search effectively

I need to have a data structure with say 4 keys . I can sort on any of these keys. What data structure can I opt for? Sorting time should be very little. I thought of a tree, but it will be only help ...
568 views

### Comparison of my own Insertion Sort versus the standard algorithm

I come from a background of making MVC websites and HTML5 applications, and have recently decided to dive into the sort of stuff i wasn't taught at university, namely the things most people would ...
186 views

### Sorting months with pre-defined order?

I want to sort the months of the year starting at any month, but January needs to show up after December if January isn't the starting point. Can I do that in an array or do I need a special data ...
2k views

### What's the best way to manage list item sort order with Drag & Drop UI?

I have a list of Students that I should display to user on a web page in tabular format. The items are stored in DB along with SortOrder information. On the web page, user can rearrange the list ...
4k views

### sorting using a custom definition of “>” and “< ” in python

suppose I have a custom function such as def greater(a, b): if (a % b) % 2 == 0: return 1 return 0 It defines how to compare two numbers and determine which is greater. In this ...
6k views

### What sorting algorithm does STL use?

I recently started using <vector.h> library and I was wondering, since all the operations are already implemented, IF the method of the sorting algorithm is the most efficient one. Everything ...
936 views

### How can this deterministic linear time selection algorithm be linear?

I'm trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as ...
13k views

### Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
386 views

### Algorithm for determining grid based on variably sized “blocks”?

I'm trying to convert a set of "blocks" in to a grid-like layout. The blocks have a width of either 25%, 33%, 50%, 66%, or 75% of their container and each row of the grid should try to fit as many ...
1k views

### Why doesn't java use a radix sort on primitives?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) is implemented as a 'tuned quicksort' rather than a radix sort. I did a speed comparison a while ago, and with something like n>...
422 views

### Need help with algorithm for sorting list

The answer is probably obvious but not to me at this moment, so I was wondering if somebody who is better with sorting algorithms can help lead me in the right direction. This is not homework, I am ...
25k views

### Sort algorithms that work on large amount of data

I am looking for sorting algorithms that can work on a large amount of data, i.e. that can work even when the whole data set cannot be held in main memory at once. The only candidate that I have ...
15k views

### Why do some sorting methods sort by 1, 10, 2, 3…?

I've noticed than many numerical sorting methods seem to sort by 1, 10, 2, 3... rather than the expected 1, 2, 3, 10... I'm having trouble coming up with a scenario where I would need the first method ...
2k views

### Basic premise on counting sort. How is k related to to Big Oh?

I am reading (Cormen) on counting sort. I understand the structure of the algorithm but the statement: In practice, we usually use counting sort when we have k = O(n), in which case the ...
2k views

### Algorithm refresher. Why is heapsort an insort algorithm?

I can not see why the heapsort is considered an inplace sorting algorithm. I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the ...
2k views

### Java and .NET: Why different sorting algorithms are used by default?

Just wondering why Java and .NET Framework uses different sorting algorithm by default. In Java Array.Sort() uses Merge Sort algorithm by default and as Wikipedia.com says: In Java, the Arrays....
2k views

### does quicksort provide less swapping step?

So far, most of the fastest and common sorting method is quicksort. Although it has its pro and cons. However, i'm thinking that although this sorting method is fast but does it provide shortest ...
373 views

### Data “unsort” / homogeneity algorithm

In an attempt to not reinvent a wheel, I'm asking if anyone has ideas on a data homogeneity algorithm. A brief example: My data has several elements maybe like Number Color Fruit Letter There ...
80 views

### Keep permuting a vector until it is ordered

I have this problem: Imagine you have a vector V, integers from 0 to 70000 -- sorted in ascending order Now you have a permutation P of that vector. Then you do V[P] "shuffling" the vector. If you ...
5k views

### Fast algorithm for finding common elements of two sorted lists

Suppose I have two lists of N 3 by 3 vectors of integers. I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st ...
7k views

### Is Bubble Sort the slowest sorting algorithm? [closed]

Is bubble sort the least Big-O efficient? If the answer is no, then what is the least efficient sorting algorithm?
3k views

### Which sorting algorithms have a different worst case complexity than their average case? [closed]

I'v been working on sorting for a while now but I can't figure these two questions apart, I'm kind of getting mixed up somewhere ... Somebody help a) Which sorting algorithms have a different worst ...
12k views

### Why isn't Radix Sort used more often?

It's stable and has a time complexity of O(n). It should be faster than algorithms like Quicksort and Mergesort, yet I hardly ever see it used.
13k views

### How do I figure out the minimum number of swaps to sort a list in-place?

In-place sorting is essentially swapping elements without using extra storage, correct? How can I find the minimum number of swaps required for a list? A C D Q R Z E // input | | | > > >...
217 views

### Where can I obtain a first-generation copy of the classic “Sorting out Sorting”? [closed]

I cannot even figure out who made it - even the IMDB page is mostly blank, and Wikipedia does not seem to have any information about it. For such a useful film in CompSci, it strikes me as odd that ...