All Questions
Tagged with sorting computer-science
44
questions
23
votes
2
answers
11k
views
What is meaning of strict weak ordering in layman's term?
I gone through many pages using Google, but not understand exact meaning of Strict-weak Ordering term.
I have this requirement while sorting strings.
- 474
7
votes
2
answers
243
views
Quicksort with Trivalued Logic
Does anyone know a way to do a quick sort with trivalued logic?
The problem I’m trying to solve is this: I’m trying to display a view of a complex 3d object from a given viewing angle. I’ve broken the ...
6
votes
1
answer
355
views
Reference Request on Order Theory topics
I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
- 917
5
votes
5
answers
35k
views
4
votes
1
answer
218
views
probability of number of comparisons of randomized quicksort
Let's assume we have an array of length $5$ which contains pairwise different integers. The subcript denotes the order of the respective integer, so $i_1<i_2<i_3<i_4<i_5$.
We apply the ...
- 4,564
4
votes
1
answer
3k
views
SQRTSORT from Vazirani's book on algorithms
I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
- 44
3
votes
2
answers
554
views
Application of Mergesort
We have $8$ players and we want to sort them in $24$ hours.
There is one stadium. Each game lasts one hour.
In how many hours can we sort them??
I thought that we could it as followed:
$$\boxed{...
- 14k
3
votes
1
answer
856
views
Expected time of Quicksort
I am reading the proof of the theorem:
The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time.
The proof is this:
For simplicity in the timing analysis assume ...
user175343
3
votes
2
answers
1k
views
Find both the largest and second largest elements from a set
Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons.
Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient.
...
- 14k
3
votes
2
answers
992
views
Time complexity of sorting a partially sorted list
Assume a sorted list of $n$ elements followed by $f(n)$ elements in random order.
How would you sort the whole list given the following:
a) $f(n)=O(1)$
b) $f(n)=O(\log n)$
c) $f(n)=O(n^{1/2})$
d) ...
- 31
3
votes
1
answer
1k
views
Sort an array given the number of inversions
Given an array $A$ with $n$ integers in it, one way of measuring the distance of the array from a sorted array is by counting inversions. A pair of indices $i,j ∈ {0,...,n−1}$ is called an inversion ...
- 31
3
votes
1
answer
184
views
Generate a new total ordered set from an existing ordered set and a partial ordering
I have a totally ordered set S and I'd like to re-order it based on a partial ordering P.
If set S looks like [A, B, C, D, E] where A < B, B < C, and so on. And set P looks like [A, E, B]. Then ...
- 135
2
votes
2
answers
8k
views
The decision tree has height at least $\log n!$
The proof of the theorem
Any decision tree that sorts $n$ distinct elements has height at least $\log n!$
is the following:
Since the result of sorting $n$ elements can be any one of the $n!$ ...
- 14k
2
votes
2
answers
202
views
Could graph theory aid in the understanding of comparison sorting algorithms?
I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article.
Up to $n=15$, we know how many comparisons between elements one must make to ...
- 7,148
2
votes
1
answer
1k
views
A decision tree has an expected depth of at least $\log n!$
I am looking at the proof of the following theorem and I have some questions.
The theorem is the following:
On the assumption that all permutations of a sequence of $n$ elements are equally ...
- 14k