Questions tagged [sorting]
For questions about dividing groups of objects based on their properties.
22
questions
0
votes
2
answers
724
views
Linear algebra to find EV of sort algorithm
I am having a hard time figuring out how to use Markov chains to address a sorting method. It is for a PE problem (i.e. problems done for fun), if anyone's curious. I do not want spoilers but just ...
- 857
13
votes
2
answers
3k
views
Median of distinct numbers
What is the least number of comparisons we need to find the median of 6 distinct numbers?
I am able to find the answer to the median of 5 distinct numbers to be 6 comparisons, and it makes sense, ...
- 2,123
11
votes
5
answers
31k
views
Worst case analysis of MAX-HEAPIFY procedure .
From CLRS book for MAX-HEAPIFY procedure :
The children's subtrees each have size at most 2n/3 - the worst case
occurs when the last row of the tree is exactly half full
I fail to see this ...
- 2,349
11
votes
1
answer
4k
views
Why is sorting pancakes NP hard?
An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with ...
- 212
5
votes
5
answers
35k
views
5
votes
3
answers
2k
views
expected number of shuffles to sort the cards
Initially the deck is randomly ordered. The aim is to sort the deck in order. Now in each turn the deck is shuffled randomly. If any of the initial or last cards are in sorted order then they are kept ...
- 561
3
votes
2
answers
3k
views
How many rounds are required in a "Swiss tournament sorting algorithm"?
You're organizing a Swiss-style tournament with N players of a game.
The game is a two-player game, and it results in one winner and one loser. The players are totally ordered by skill, and whenever ...
- 10.7k
3
votes
4
answers
2k
views
Merge sort seems to take the same number of comparisons for best and worst case.
I am trying to clear up my conceptions of merge sort. What I cannot understand how merge sort takes less number of comparisons during best case.
Let me explain, looking at the merge procedure given ...
- 1,025
2
votes
1
answer
1k
views
Sort vectors according to their distance between them
I have a collection of vectors, let`s say $n$ vectors. I am trying to find an easy way to SORT these vectors in that way that after sorting of vectors $(V_1,V_2,...,V_n)$ the first vector $V_1$ and ...
- 35
2
votes
3
answers
321
views
Equation to calculate best liked comments
In my website, users can either "like" or "dislike" a posted comment. I want to put a link to sort comments by liking such that the most liked ones becomes on top.
Of course I cannot just sort by ...
Anas
2
votes
2
answers
3k
views
Probability of a sorted sequence
Now I tried tackling this question from different sizes and perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I ...
- 945
2
votes
1
answer
81
views
How to sort 4 (or more) values with non-piecewise functions?
This question was inspired by this:
Finding a non-piece wise function that gives us the $i$'th largest number.
My question is
how to do this for
four or more values.
In other words,
given 4 ...
- 108k
2
votes
2
answers
250
views
Arranging numbers in an array (Swedish Math Olympiad 1986)
Consider an $m\times n$ array of real numbers. Let $d>0$. Suppose that the difference between the maximum number and the minimum number in each row is at most $d$. We then sort the numbers in ...
- 184
1
vote
1
answer
95
views
Sort rectangles by size, but with a tunable advantage favoring squareness
I want to sort some rectangles from biggest to smallest, but with a tunable advantage favoring squarer rectangles. I'm sure this is super easy but I'm not getting it. I think it's related to topics ...
- 63
1
vote
1
answer
98
views
Can a comparison network obtain all the n! permutations of a vector?
I want to permute a vector using comparison networks. This is the only method I have at my disposal.
My original idea is to use a sorting network like Batcher or Bitonic. Basically I place my vector ...
- 175