All Questions
Tagged with sorting computer-science
44
questions
1
vote
1
answer
78
views
Is there an intuitive reason natural logarithms arise in the analysis of randomized quicksort?
The randomized quicksort algorithm works as follows:
If the list to sort is empty or has length one, it’s sorted.
Otherwise, pick a uniformly random element of the list called the pivot element. ...
- 10.5k
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 ...
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
2
votes
1
answer
182
views
Sit N people around a table so as to minimize the maximum difference in height between any two adjacent people
(This is actually a coding challenge for an interview. Unfortunately, only 2 test cases are coded, so even if my solution passes them both, that doesn't tell me I've found the correct solution. Also, ...
- 315
1
vote
1
answer
601
views
How do I prove by using induction on k, that MergeSort uses $n(\log_2(n)+1)=2^k(k+1)$ comparisons?
I have been asked this question in an assignment for my exam.
The assignment question is: "Assume that Merge uses (exactly) $a+b-1$ comparisons to combine two lists with a and b elements. ...
- 13
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
1
answer
133
views
Minimize the absolute difference of the sum of two dijoint sets in which terms are in the powers of $p$.
Given $n(n>=1)$ integers $k_1,k_2 \cdots k_n(k_i>=0)$, and an integer
$p>=1$, Johny picks $p^{k_i}$ from $i-th$ category for each category , and he wants to
divide them into two disjoint sets,...
- 888
1
vote
2
answers
7k
views
How many comparisons does the insertion sort use to sort the lists in question
I have two lists to sort using insertion sort:
How many comparisons does the insertion sort use to sort the list
$n, n − 1, . . . , 2, 1$?
How many comparisons does the insertion sort use to sort ...
- 1,189
0
votes
1
answer
68
views
Why is the probability of two elements being compared equal to 2/(𝑗−𝑖+1) in random quicksort?
After reading Why is the probability of two elements $y_i$, $y_j$ being compared equal to $2/(j - i + 1)$ in random quicksort?
I am confused as to what $j-i+1$ means in the denominator.
Is it the ...
- 927
1
vote
2
answers
776
views
Minimum Comparisons needed for worst case sorting of array consisting of only 1,-1,0
Let $A$ be an array of $n$ elements consisting of only $-1,1,0$. What is the least number of comparisons that must be made in worst case to sort the array?
At first I was thinking of the answer is 0 ...
- 889
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
1
vote
1
answer
121
views
Run Time Analysis of the Merging Part in Mergesort
I want to show that if I apply the Mergesort on a set $M$ with $n$ elements and divide $M$ in $2<b\le n$ parts instead of just $2$, that the I need $O(nlog_2 (b))$ time for the merging part.
So ...
- 297
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
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
1
vote
1
answer
278
views
Randomized Quick Sort and Partition Probability?
We know about Quick Sort and Randomized Version and Partition. I ran into a Fact when I read my notes.
Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized ...
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