All Questions
Tagged with sorting computer-science
6
questions with no upvoted or accepted answers
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
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
0
answers
303
views
Prove that MergeSort is stable for any input size n ∈ N using induction on n.
In terms of a list of objects with two separate fields, suppose a stable sort would order the list in increasing order. However, if two elements have the same number, then they'll appear in the same ...
0
votes
0
answers
67
views
How to prove if a list is sorted if any two consecutive elements are sorted?
To check if a list is sorted, a typical approach is to check every element and its next element, and see if they are sorted. Intuitively, I understand it is correct. But is there a more mathematical ...
- 101
0
votes
0
answers
36
views
How to get increasing int number based on two values
I did ask this question on SO but it seems this will find more appropriate audience here.
I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
- 101