The tag has no wiki summary.

learn more… | top users | synonyms

32
votes
6answers
2k 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 ...
15
votes
3answers
5k 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.
15
votes
3answers
1k 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 ...
13
votes
2answers
468 views

Trying to understand the 2N lnN compares for quicksort

I was going through the analysis of quicksort in Sedgewick's Algorithms book. He creates the following recurrence relation for number of compares in quicksort while sorting an array of N distinct ...
10
votes
2answers
838 views

What does it mean for a sorting algorithm to be “stable”?

In reading about various sorting algorithms I've seen it mentioned that some are "stable" and some are not. What does that mean, and what tradeoffs are involved on that basis when selecting an ...
10
votes
8answers
11k 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 ...
9
votes
5answers
930 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 ...
8
votes
6answers
484 views

Quicksort and don't bother?

Especially when writing 'standard' (non-HPC) applications, do you consider what sorting algorithm to pick, or just settle with quicksort (which is what most libraries just call sort)? To some extent ...
8
votes
2answers
717 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 ...
8
votes
3answers
204 views

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

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 ...
8
votes
3answers
314 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 ...
7
votes
5answers
3k 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 ...
6
votes
6answers
3k views

Why is binary search,which needs sorted data, considered better than linear search?

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
6
votes
3answers
810 views

Why is Quicksort called “Quicksort”?

The point of this question is not to debate the merits of this over any other sorting algorithm - certainly there are many other questions that do this. This question is about the name. Why is ...
6
votes
5answers
398 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 ...
5
votes
3answers
628 views

Why don't computers come with specialized hardware such as sorting networks?

Instead of programming the way we do, why don't we make specifications of common tasks such as "sorting", and then let the environment compile it to make best use of it's hardware? This way, we could ...
5
votes
2answers
2k 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 ...
5
votes
3answers
1k 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 ...
5
votes
1answer
367 views

Sorting versus hashing

My problem is as follows. I have an array of n strings with m < n of them distinct. I want to create a one-to-one function which assigns each of the m distinct strings to the numbers 0 ... m-1. ...
4
votes
3answers
2k views

Quickest way to split a delimited String in Java

I am building a Comparator that provides multi-column sort capability on a delimited String. I am currently using the split method from String class as my preferred choice for splitting the raw String ...
4
votes
6answers
5k 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 | | | > > ...
4
votes
2answers
2k 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 ...
4
votes
2answers
2k 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 ...
4
votes
2answers
498 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 ...
4
votes
3answers
1k 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 ...
3
votes
3answers
436 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 ...
3
votes
1answer
82 views

Algorithm that determines relevant attributes in ordered list

Suppose I have a list of objects sorted by a person based on that person's subjective taste. Let's assume that this person is being somewhat consistent in their sorting and that there are quantifiable ...
3
votes
1answer
281 views

which sorting algorithms is using OrderBy

I am litle curious about what sorting algorithm is using OrderBy (linq to objects). quicksort? heapsort? introspective sort ? As i see in MSDN documentation List.Sort is using introspective sort: ...
2
votes
4answers
322 views

Is there any sorting algorithm which is not inherently sequential and is task distributable?

After googling for a couple hours, I came to a conclusion that all sorting algorithms are inherently sequential which can be data distributed but not task distributable. Is there any algorithm which ...
2
votes
3answers
724 views

Sorting an array of numbers with decimal places

Suppose I have an array of float values in the following format: { 1.34, 1.15, 1.1, 1.2, 1.26, 1.10, 1.20, 1.17 } Suppose they have been provided by user input (or some other mechanism), where the ...
2
votes
4answers
3k 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 ...
2
votes
4answers
278 views

Looking for monotonically increasing (integer) hash function

I'm looking for a HashFunction(X,Y: Integer): Integer that is monotonically increasing on X, then Y. So: HashFunction(x1,y1) > HashFunction(x2,y2) if x1>x2 HashFunction(x,y1) > HashFunction(x,y2) if ...
2
votes
4answers
773 views

Applications of heapsort

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 ...
2
votes
1answer
95 views

Sorting with continous input

I'm designing (not writing, yet) a task scheduler system for a complex video game. The rest of the program passes it objects containing a function and some metadata including an estimation of how much ...
2
votes
4answers
2k views

Which sorting algorithms have a different worst case complexity than their average case?

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 ...
2
votes
1answer
442 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 ...
2
votes
1answer
939 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 ...
2
votes
1answer
147 views

Fully Stable, In-Place Unique Algorithm in O(n)

Is there an algorithm that, given a sorted array, swaps all the first unique elements to the beginning of the array and the duplicates to the end, while remaining stable for both the unique subarray ...
2
votes
3answers
140 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 ...
2
votes
2answers
504 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 ...
2
votes
1answer
83 views

Why is time complexity of k-way merge sort O(nk^2)?

I'm comparatively new to algorithm analysis and am taking a related course on coursera where I came accross k way merge sort. The time complexity of 2 way merge sort is n log2 n, of 3 way merge sort ...
2
votes
2answers
91 views

Set distances algorithm question

I have multiple sets containing integers. An integer maybe present in one set or multiple sets. I would like to find/match the sets with the most common integers. Example s1 {1, 2, 3, 4} s2 {1, 3, 4, ...
1
vote
5answers
4k views

Is Bubble Sort the slowest sorting algorithm? [closed]

Is Bubble Sort the slowest sorting algorithm? If the answer is no, then what is the slowest one?
1
vote
4answers
253 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 ...
1
vote
3answers
486 views

Sort an array in a specific order - not ascending/descending

I'm working on an algorithm that works best if the inputs are passed to it in a particular order, so I want to sort them that way. The difference is drastic enough for me to consider re-sorting the ...
1
vote
6answers
7k 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 ...
1
vote
1answer
118 views

Heuristic for consistiently ordering points in a a plane

I have rectangular regions in a plane. I want to consistently order them in a human-friendly way that a typical y-x sort won't work for. Basically I want (0,0), (1,0), and (0,1) to sort the same as ...
1
vote
3answers
418 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) ...
1
vote
2answers
186 views

Python sorted iterable set, modifiable during iteration

I am looking for a datastructure to handle cycling through a large number of ordered subroutines, some of which are active, most of which are not. I am thinking I need an implementation of a python ...
1
vote
1answer
233 views

Advantage of 2-way merge sort against n-way

It's known 2-way Merge sort takes N*logN time. I wonder, what would be the running time if we split an array of the size N into N subarrays and then do the same thing as we would do for 2-way Merge? ...