Hot answers tagged

92

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.


55

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)} ...


21

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 ...


20

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 ...


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 ...


14

the smaller the difference between the indices of any two elements, the smaller the difference between the values of the elements. When working with lists of coordinates or similar values with more than one dimension, is there an arrangement of the list that has similar properties to those of a sort in one dimension? What you want is called Distanceā€...


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

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

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

Just sort the players by team and number them starting from 0, so e.g. 0(000) T1a (team 1 player a) 1(001) T1b 2(010) T1c 3(011) T2a 4(100) T2b 5(101) T3a 6(110) T3b 7(111) T3c Then reverse the bits in each number to fill out your bracket sheet 0(000) T1a\______ 1(001) T2b/ \_______ 2(010) T1c\______/ \ 3(011) T3b/ \...


9

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 (...


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 ...


9

You seem to be confusing the median value and the middle element. The middle element of the unsorted array could indeed turn out to be close to the lowest or highest value. The median value on the other hand is the value that has half the values compare as smaller and half the values compare as bigger. The advantage of using the median value as a pivot in ...


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

The problem with Data.List.sort is that it uses merge sort, which creates new lists during each pass. So a lot of time is spent on allocating and freeing memory. Surprisingly, AFAIK there isn't a sorting library for mutable arrays, which are likely to be faster. So I tried to make one and put it on github: marray-sort. It needs rigorous testing, polishing ...


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