All Questions
Tagged with sorting computer-science
44
questions
1
vote
0
answers
241
views
How to state a recurrence that expresses the worst case for good pivots?
The Problem
Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and $...
- 1,884
1
vote
1
answer
87
views
Why is Mergesort $O(n)$ rather than $O(n\log{n})$?
Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is
$T(n)=2*T(n/2) +2$, for $n>2$, ...
- 83
1
vote
1
answer
145
views
Sorting algorithms
How could we show that the algorithm of
Mergesort is stable,
Quicksort is not stable but it can be implemented as stable,
Heapsort is not stable.
I have show that the algorithm of Insertion Sort ...
- 14k
1
vote
1
answer
62
views
Is the invariant correct?
I want to show that Insetion Sort is stable... Do I have to do that using an invariant??
Is the invariant the following??
At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b \...
- 14k
0
votes
2
answers
3k
views
Dividing the interval in subintervals of equal length
I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$
dividing the interval $[0, 1)$ ...
- 14k
2
votes
2
answers
11k
views
Can anyone explain the average case in insertion sort?
I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof
Here is an example of insertion sort running a on a set of data
...
- 1,884
1
vote
1
answer
94
views
Is there a typo in this runtime analysis of selection sort?
This is from https://courses.cs.washington.edu/courses/cse373/13wi/lectures/02-25/19-sorting2-select-insert-shell.pdf, slide 6.
The instructor is doing a runtime analysis of selection sort. Here is ...
- 1,884
0
votes
1
answer
79
views
Quicksort-How did we get the relation?
At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence:
We suppose that the partitions are equally likely, so the possibility that the sizes ...
- 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
1
vote
2
answers
95
views
The expected time to sort $n$ elements is bounded below
Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$.
Could you give me some hints how I could do that?
- 14k
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
1
vote
3
answers
2k
views
How many comparisons are required?
Let $S$ be a set of $n$ integers. Assume you can perform only addition of elements of $S$ and comparisons between sums. Under these conditions how many comparisons are required to find the maximum ...
- 14k
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
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
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