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.6k
0
votes
0
answers
302
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
178
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
132
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,...
- 868
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
67
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
276
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 ...
