Tag Info

New answers tagged

0

Note that the pseudo-code in wiki is not practical. It is written to undestand. If an array is [0,0,0,1] pivot is 1 and other elements are less than the pivot, then swapping(t <-- a, a <-- b, b <--t) works as t <-- a, a <-- a, a <-- t. In this case swapping works nothing. If an array is [4,2,1,3] then [4,2,1,3] --> [2,4,1,3] --> [2,1,4,3] ...


0

An algorithm escapes from most bad cases using a randomized pivot, excluding continuous elements equals to a pivot from partitioning, and asymmetric search. It searches forward an element greater or equals to a pivot, and searches backward an element less than a pivot. I thank MichaelT, Asymmetric search is devised to resolve [2,1,2,1,2,1,2,1]. The ...


5

Take a look at this neat implementation of sorting six integers. According to sorting networks, 16 comparisons are required to sort 7 integers. Here is the code for seven integers: static int sort7(int *d){ #define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; } SWAP(1, 2); SWAP(3, 4); SWAP(5, 6); SWAP(0, 2); ...


1

The problem doesn't require an exact solution. And opinions are not an exact mesure anyway. You could simply count +1 every time a song is preferred and -1 every time it is not preferred. A B C A >= B : 2 +2 -2 A <= B : 0 0 0 A >= C : 1 +1 -1 A <= C : 4 -4 +4 ---------- -1 -2 ...


1

One possible formalization is as a longest path problem. Construct a directed graph in which nodes are labeled with songs, and for each ordered pair of songs (A, B) there is a weighted edge A -> B with weight equal to the number of votes for A < B. Then the longest simple path is a total order that agrees with the maximum number of votes. If the longest ...



Top 50 recent answers are included