14
votes
Accepted
Is the IComparable interface outdated/"harmful"?
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. ...
- 214k
14
votes
Is there a sensible way to sort coordinates?
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 ...
- 51.4k
13
votes
Is this a sorting algorithm faster than O(n*log(n))
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 ...
- 104k
12
votes
Binary search is not fast
Your actual binary search implementation includes a test isSorted() which scans through the whole list and is therefore slower than the linear search. Re-test without this and you will see different ...
12
votes
Why are sort() and reverse() JavaScript methods in-place?
Because we can. Because it’s actually cheaper. A method that returns a different array either elements sorted or reversed takes twice as much memory.
Filtering cannot return the same array because the ...
- 47.5k
11
votes
Accepted
Algorithm to sort ten million 7-digit integers in ascending order with just 1.5Mb RAM?
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 ...
- 315
9
votes
Accepted
Fastest algorithm of dividing array into positive and negative numbers
That task is simple:
Iterate from start and end at the same time, and swap the element if needed.
L = index_first
R = index_last
while L < R
while L < R and v[L] < 0
L++
while ...
- 9,131
9
votes
Accepted
Why is the optimal choice for a pivot in quicksort algorithm the median element?
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 ...
- 76.7k
8
votes
Accepted
Why is stability considered a desirable trait of a sorting algorithm?
The common argument for stability in a sorting algorithm typically involves an example where a list is sorted by two criteria. For example:
1,4,5,7,2,6,8,9,15,65,24,27
sort by evenness/oddness and ...
- 76.7k
7
votes
How to make ability to order records in DB?
Four options for you. I like option 4 but the first one is easiest.
Option 1. Just start one higher
The values in the Order column don't matter, just their relative values. Whether you number ten ...
- 26.9k
7
votes
Accepted
In merge sort, why not just split to individual items immediately rather than recursively splitting in half?
Any recursive function can be converted into an iterative one. Normally, however, you would just use recursion for a Merge Sort, because splitting in half over and over again lends itself naturally to ...
- 200k
7
votes
Accepted
Best algorithm to sort tasks by priorities by a human
Bucket Sort
But I'm getting ahead of myself.
Consider the use cases of listing and sorting tasks like this.
A dev completed a task and needs to know what to work on next
A Project Manager needs to ...
- 1,073
7
votes
Accepted
During a peer evaluation of code, is it constructive to suggest changes for the sake of making the code look "pretty"?
Changes that suggest "making code look nice" are mainly a matter of taste (as opposed to "making it look less ugly", but see below). Such issues have a high potential of making ...
- 901
6
votes
sorting using a custom definition of ">" and "< " in python
Programmer named 'System Down' has correctly described the situation, it's just that for Python 3, we can also use following code.
For Python 3:
import functools
def greater(a, b):
if (a % b) % 2 ==...
- 161
6
votes
Accepted
Grouping objects according to a set of fields
This problem is known, AFAIK, as "partitioning a set into equivalence classes", but I could not find ad hoc a good web resource for it, so I try give a general outline of an efficient algorithm:
The ...
- 214k
5
votes
Accepted
Dual pivot quicksort in face of expensive swaps
Has anyone tested dual pivot quicksort performance with expensive-to-swap elements? It seems that in this case, it should massively underperform compared to standard quicksort.
...
During some ...
- 66
5
votes
A concise way of permanently sorting a bullet list on a wiki
The thing to take advantage of here is that one write is read many times. Sort on the write, not on the read.
Up to you if you want to do that client or server side. But if letting clients sort on ...
- 115k
5
votes
Accepted
How to make ability to order records in DB?
There are multiple approaches that you can use:
The easiest one is to forgo the UNIQUE constraint on the column that specifies the ordering (either as linked list or as sequence number). It is then ...
- 76.7k
5
votes
Simple algorithm for computing an orderable value from a string
It's a bad approach because it doesn't work. This is basically a question of domain sizes.
Even with only 36 possible characters, there are vastly more possible strings than probably fit into the ...
- 110k
5
votes
Parallel sorting algorithm that compares all elements
If the comparison metric is a boolean (as indicated in the comments), then there are two possibilities.
The metric is transitive (if comp(A, B) yields true and comp(B, C) yields true, then comp(A, C) ...
- 76.7k
5
votes
What means "breaking ties" in context of sorting
In the context of sorting, tie breaking is about ensuring a total order.
Take a look at the example data:
"id": "14" //made up data
"name": "John" //real data
"birth_date": "1990-12-20T11:50:...
- 16.3k
5
votes
Accepted
Why are sort() and reverse() JavaScript methods in-place?
Arrays were originally implemented as hash tables. Keys (buckets) were converted to strings and hashed. v8 still implements it as a hash table, but also supports a fixed array (ref).
The language ...
- 214
5
votes
During a peer evaluation of code, is it constructive to suggest changes for the sake of making the code look "pretty"?
If you're spending time in your code review process arguing about the order of things in dictionaries, you are doing it wrong.
Create a standard, stick to it, enforce it in your tooling and spend your ...
- 25.6k
4
votes
Accepted
Sorting by setting a sequence property instead of rearranging the position in the list
These days, most of the time you're sorting records of any kind, you're really only sorting pointers to them, while the records stay where they are in memory. That means that performing a sort and ...
- 110k
4
votes
Accepted
Mostly sorted arrays: Insertion sort vs insert at sorted position
When inserting an item in the middle of the sorted array, you first need to find the correct location (e.g. via binary search), and you need to shift all the elements on the right of the insertion ...
- 135k
4
votes
Accepted
Resolving foreign keys: breaking cycles to enable a topological sort
What you are asking for is essentially the the so-called Feedback arc set problem, so finding the minimum necessary edges to be removed from the graph induced by the FK constraints is NP hard. There ...
- 214k
4
votes
Accepted
When to use Quicksort instead of MergeSort?
Likely there isn't necessarily a single correct answer, but your professor wants to see how well you know the properties of both algorithms and whether you can justify a set of constraints / goals in ...
- 743
4
votes
Accepted
Iterative Sorts vs. Recursive Sorts
What you asked is:
"How can Quicksort and Merge Sort be more efficient in terms of memory usage than the naive sorts?"
And the answer is: they aren't.
Complex sort algorithms like Quicksort and ...
- 214k
Only top scored, non community-wiki answers of a minimum length are eligible