Questions tagged [sorting]
For questions about dividing groups of objects based on their properties.
22
questions
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 ...
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?
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
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 ...
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 ...