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
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
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
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,035
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
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
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
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
1
vote
1
answer
400
views
Find 3rd largest number out of 7 under at most 11 comparisons
I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
- 177
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
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
525
views
Distribution probability of elements and pair-wise differences in a sorted list
Suppose a set of $m$ integers from $0$ to $n-1$. The integers are uniformly distributed and unique in the set ($n \gg m$). Then, put all the integers into a list an sort that list:
$$x_0 < x_1 < ...
- 1,307
1
vote
1
answer
2k
views
Insertion Sort Average Case
Although I know "Insertion Sort" has an average time complexity of O(n^2) (although not really familiar with the notation myself, i got that O(f(n)) is basically any constant multiplied to f(n) or ...
- 851
1
vote
1
answer
660
views
Does switching between different $L_p$ norms preserve order?
Suppose you have a list of $n$ dimensional vectors. One can order them by using an $L_p$ norm to do comparisons between vectors. The general questions is, will the order be different depending on the ...
0
votes
1
answer
607
views
Which one gives better constant factors between heap sort and quick sort?
Heap Sort has complexity $\mathcal{O}(n\lg(n))$ and Quick Sort with some tuning (choosing the pivot in a random order) on average also sorts in $\mathcal{O}(n\lg(n))$ and both of these are tight upper ...
- 2,349
0
votes
0
answers
2k
views
Algorithm for Liquid sort puzzle
I recently came across this game and it is really interesting.
https://play.google.com/store/apps/details?id=com.picolaf.liquidsortpuzzle&hl=en_US&gl=US
The goal here is to sort the liquid of ...
-1
votes
2
answers
1k
views
Need help analyzing a merge sort
Im working on trying to understand merge sorts better and had a professor give me this to try to help. It is finals week and I have been trying to walk through this problem but have been having ...
- 9