Hot answers tagged

88

A stable sort is one which preserves the original order of the input set, where the comparison algorithm does not distinguish between two or more items. Consider a sorting algorithm that sorts cards by rank, but not by suit. The stable sort will guarantee that the original order of cards having the same rank is preserved; the unstable sort will not.


53

Are there any practical considerations that I am overlooking which making binary search better than linear search? Yes - you have to do the O(n log n) sorting only once, and then you can do the O(log n) binary search as often as you want, whereas linear search is O(n) every time. Of course, this is only an advantage if you actually do multiple searches on ...


26

Stable algorithms preserve the relative order of elements. So a stable sorting algorithm will retain the relative order of values which compare as equal. Consider a sorting algorithm where we sort a collection of 2d points based on their X dimension. Collection to be sorted: {(6, 3), (5, 5), (6, 1), (1, 3)} Stable Sorted: {(1, 3), (5, 5), (6, 3), (6, 1)} ...


19

First of all, computers come with specialized hardware. Every laptop and desktop computer sold for quite a few years now has a specialized co-processor, a Graphics Processing Unit, that handles visual-processing algorithms, such as video and gaming applications require. Very large computers (e.g., "supercomputers", IBM's System Z family) have a variety of ...


19

I've written a quick and dirty benchmark test for this. It compares 7 different methods, some of which require specific knowledge of the data being split. For basic general purpose splitting, Guava Splitter is 3.5x faster than String#split() and I'd recommend using that. Stringtokenizer is slightly faster than that and splitting yourself with indexOf is ...


17

I would speculate that: Array.sort is implemented as quicksort, because quicksort can sort anything in decent time given a comparator. Sorting a list of 10000 entries is not so common. Accessing a data-structure of 10000 or more elements is rather common. If you need to maintain order, a balanced search tree is often a better way to go than to sort your ...


14

The basic assumption is that you do not make one search. So if you need to search the same data multiple times then you only have to sort once and can profit from binary search. If you a searching often and have changing data it is worth to use a sorted list where new entries are sorted into the list. So basically binary search is better when you search ...


14

IComparable has the restrictions you mentioned, that is correct. It is an interface which was already available in .NET framework 1.0, where those functional alternatives and Linq were not available. So yes, one might see it as an outdated framework element which is mainly kept for backwards compatibility. However, for lots of simple data structures, one ...


13

I've done something like this before using a generator (in C#, an infinite loop that yields each loop iteration). Each iteration looks at its pool of songs (or whatever) and tosses out ones that have been played too recently (or whatever negative criteria). Then you pick one from the filtered list, and update your state. As your state drifts (you play non-...


13

In 1962 research on sorting algorithms wasn't as far advanced as today and the computer scientist Tony Hoare found a new algorithm which was quicker than the other so he published a paper called Quicksort and as the paper was quoted the title stayed. Quoting the abstract: A description is given of a new method of sorting in the random-access store of a ...


13

You overlooked sleep-sort which is task distributed. Here is an implementation for the Bourne shell: input="10 4 5 1" for n in $input; do (sleep $n; echo $n) & done When the program completes, the sorted list of numbers is printed on the standard output. (Note that you could need to add job management to determine when the subprocesses finish.)


13

The algorithms for determining which string comes first when comparing two strings are called collation algorithms and the sort order they produce is called the collation order. Unfortunately, there is no agreed upon global collation order. To make matters worse, the correct sorting order is not only language dependent, but can even differ between different ...


13

Congratulations, you have re-invented counting sort! (I'm not being sarcastic, things independently being re-invented multiple times is a good thing, it shows that it is a natural and good way to solve problems.) The time complexity of counting sort is indeed better than O(n * log n). Note that the usually cited "barrier" of Ω(n * log n) for "sorting" ...


12

1. If you rarely add and remove data What about using the same technique as the one used in RDBMS with indexes? In other words, you'll have the unordered set containing the data, and four ordered sets containing the keys and the pointers to the items in the data set. Of course, this may cause performance issues if you need to frequently add and remove ...


12

You know that every element of your int arr[]; is in [1;1000]. So have an array of counters, int cnt[1001]; in C parlance. Clear it (all zeros). Then, read the arr[] array sequentially. Suppose that you have read the value x at index i (so x==arr[i]). Then increment its counter, so cnt[x]++; When you have reached the end of the input array arr, iterate ...


11

I would say you could use a bit field. That is you use one bit for each number from 0 to 9,999,999. This is 1.25 MByte of RAM. You read the file once and mark the corresponding bit when a number is read. Then in the second pass you walk over the bitfield and print the index to all entries that have the bit set. This works because you know that there are no ...


10

I have think of something, which can reduce your queries. Here in my example, I have added a new column for sorting named pos. So, initially without any dragging your table will be like - Now, Lets consider that you dragged the Item 4 between Item 1 & Item 2. Now, new pos value for Item 4 will be (20 + 10) / 2, which is 15. So, You will only need to ...


10

The main issue is that sorting algorithms (1) need a lot of flexibility, and (2) would be very difficult to accelerate using hardware anyway. One thing is that sorting algorithms are already easily fast enough to outrun the memory bandwidth of the processor - the processor will already spend a large proportion of its time waiting for data to move backwards ...


10

Generally speaking, if the language or standard library provides a function to do what you want done, use it until or unless you have a specific reason you need to use something else. That latter can happen, but it's fairly unusual as a general rule. Of course, in at least some cases it can make sense to consider some middle ground, such as writing a ...


9

If you're using Python 2.x, then that's easily achievable by using cmp, although you have to modify your function to return -1 instead of 0. Something like this: def greater(a, b): if (a % b) % 2 == 0: return 1 return -1 x = [2,7,5,10,30,15] print(sorted(x, cmp=greater)) But if you're using Python 3.x, then it gets a bit more complicated ...


9

Your problem is that your "numbers" don't have decimal places. You have a string which consists of two integers which are separated by .. Parse them as two integers and write a custom comparer. The sorting algorithm can remain the same, you just need to pass in the comparer. In C# such a comparer could look similar to this: void Test() { var data=new ...


9

A topological sort algorithm can sort a collection of data according to some set of rules as you have specified, where not all pairs have a pre-defined ordering. Typically the rules only define a partial ordering, so there are multiple possible orderings and topological sorting chooses an arbitrary one. If there's a contradiction in the rules you have ...


9

The algorithm here is: Take the value in the middle of the array, and move it to the front (by swapping). This value is the pivot. Loop through the rest of the array. Each time you see a value less than the pivot, swap it to closer to the front of the array. Specifically we have an index (named last) that keeps track of where the last lesser value was ...


8

Actually you can use a comparator which has a method compare(a,b) which you can implement. Then you can pass it in for the compare step (this is supported in nearly all standard libraries of most languages). For example in java you can call Collections.sort(fooList, new Comparator<Car>(){ public int compare(Car a,Car b){ return a....


8

Folks obsess about sorting algorthims for the wrong reasons. The value of understanding mergesort or any other sort isn't simply being able to write your own sort function. Rather it's that sorts provide readily understandable examples of entire classes of algorithms. Mergesort and quicksort are both examples of a general approach called 'divide and conquer'....


8

Every sort algorithm has a worst case, and in many cases the worst case is really bad so it is worth testing for it. The problem is, there is no single worst case just because you know the basic algorithm. Common worst cases include: already sorted; sorted in reverse; nearly sorted, one out of order element; all values the same; all the same except first (...


8

That task is simple: Iterate from start and end at the same time, and swap the element if needed. A = index_first B = index_last while A < B while A < B and v[A] < 0 A++ while A < B and not v[B] < 0 B-- if A < B swap(v[A], v[B]) You get N comparisons (once for each element) and at most N/2 swaps (if ...


Only top voted, non community-wiki answers of a minimum length are eligible