Questions tagged [quicksort]
Sorting algorithm based on recursive partitioning devised by Hoare (ACM Algorithm 63) with fast average case running time.
164 questions
1
vote
1
answer
106
views
Quicksort 3-way paritition vs 2-way partition
I know 3-way partition variation of quicksort is best choice for arrays with large numbers of duplicate, but I don't clearly figure out that is 3-way as good as 2-way when there is no duplicate key?
0
votes
3
answers
2k
views
O(nloglogn) Sorting Algorithm?
I have come up with an sorting algorithm that looks like $O(n \log \log n)$. Could anyone help to find if it is already commonly known or worth anything?
The time complexity seems to be: $T(n) = \...
1
vote
1
answer
165
views
Quick sort with $K-1$ pivots
I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
2
votes
2
answers
253
views
Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons
While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps:
Given an array of size $n$, ...
1
vote
1
answer
145
views
Multithreaded quicksort
The runtime of Quicksort can be significantly reduced if multiple threads running on multiple cores can be used. With just two cores, just partition an array into two halves and let another thread ...
1
vote
2
answers
96
views
Worst Case Scenario Quick Sort
I'm aware that the worst case scenario recurrence relation corresponding equation is:
$$
T(n) = T(n-1) + T(0) + \Theta(n)
$$
However, I really don't get how the last term $ \Theta(n)$ was determined.
...
0
votes
0
answers
105
views
Hoare's partition original method
So I was reading the Hoare's partition part of the Quicksort wiki and it says:
"With respect to this original description, implementations often make minor but important variations. Notably, the ...
-4
votes
2
answers
96
views
Design and analyze an efficient algorithm that, given n distinct integers, returns an element which is neither the smallest nor the largest
I'm trying to prepare for mock exam, could you please help me with possible solutions?
Design and analyze an efficient algorithm that, given n distinct integers, returns
an element which is neither ...
0
votes
2
answers
68
views
Modified Quicksort*
given array of size n, and a function called FindPivot which returns the median with a time complexity of O(n^(1.1)).
what is the worst case time complexity of quicksort using the given func to find ...
-1
votes
1
answer
40
views
How to analyze quicksort
I am trying to prove that the following statements are true:
...
1
vote
0
answers
29
views
Quicksort sampling
This question is in the context of quicksort. Consider that a subarray of distinct elements of size $k$ is sampled from the input array of size $n$, and then we choose a pivot from the sampled ...
0
votes
0
answers
85
views
Analysis of randomized algorithms
The expected running time, $T(n)$, of quicksort when the pivot is chosen uniformly at random satisfies $$ T(n) \leq \mathcal O(n) +\frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n - i)),$$
which leads to the ...
1
vote
1
answer
699
views
Quicksort for Strings
I am currently trying to study the Quicksort algorithm. I understand how it works for integers but can anyone explain how does Quicksort algorithm work with strings?
The reason for my confusion is ...
0
votes
2
answers
29
views
Searching for sorting algorithm taking into account all possible solution of similar numbers
I need a reference for sorting algorithm where all possible orders are considered.
example:
if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
1
vote
0
answers
45
views
Median as pivot selection halves array into one third and two thirds
Selecting the median as an approach for pivot selection halves the array into $T(\frac n3)$ and $T(\frac{2n}{3})$, so our $T(n)$ becomes:
$$T(n) = T(\frac{2n}{3})+ T(\frac n3)$$
Solution:
Approach 1: ...
4
votes
2
answers
4k
views
Stability of QuickSort Algorithm
Def: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows:
So for this QuickSort algorithm:
...
0
votes
2
answers
501
views
Complexity of sorting $k$-sorted array using QuickSort and HeapSort
Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is ...
1
vote
1
answer
33
views
For QuickFind, which sub problem we should consider
Question: Suppose we have the following array where we want to find the smallest $i$th smallest element in the array using QuickFind algorithm (similar to QuickSort):
$$
QuickFind\left( A,n,i \right) ...
1
vote
1
answer
62
views
In a sorted subarray $Z_{ij}$ elements $i$ and $j$ get compared when either $i$ or $j$ is pivot
This is related to the discussion of average case of quick sort.
Given that we have a sorted sub-array $Z_{ij} = i, i+1, \dots, j$ where $i < j$.
Claim: $i$ and $j$ are compared if and only if, ...
1
vote
1
answer
218
views
Pivot algorithm in median of medians
The pseudocode for the pivot function for the Median of Medians algorithm is given in https://en.wikipedia.org/wiki/Median_of_medians.
On the last line, there is a ...
2
votes
3
answers
10k
views
Time Complexity of Quicksort when using Median Pivot in sorted array
I am looking for any literature or reference for the worst case complexity of using quicksort on a sorted array with median as pivot. Different internet sources give conflicting answers and often skip ...
3
votes
1
answer
270
views
Hoare partition scheme may cause infinite recursion
Wiki states: "...partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion."
What prevents Hoare ...
0
votes
3
answers
236
views
Runtime of sorting algorithms given a particular input
say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
2
votes
1
answer
662
views
Understanding the upper bound proof for quick sort
I'm trying to understand the average run time of quicksort which is $O(n \log n)$.
I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
1
vote
1
answer
64
views
Is there a way to find the correct element in the array for the given index x?
In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element).
Is there any algorithm to find correct element for a given index ?
Here, correct index of an ...
0
votes
1
answer
203
views
How to arrange a sub-array for Quick sorting algorithm?
Alghorithm : Quick sort .
idea : devide and conqure .
steps :
1- find the pivot point from array like first element .
2- partiotioning the array so that elements are smaller than pivot point are in ...
-1
votes
1
answer
445
views
Number of comparisons in Quicksort
So would it be correct to say that the number of comparisons from level 1 to level 2 would be $2(n/2-1)$?
Or would it be more correct to say that the number of comparisons is $2^i(n/2^i-1)$?
2
votes
2
answers
273
views
Quicksort: Probability of an element being compared to fewer than $k$ pivot elements
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements.
Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$.
Furthermore, ...
0
votes
1
answer
604
views
Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?
The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.
Problem 7-1.b
Hoare's partition algorithm from the book.
Part b: Assuming the subarray $A[p,...
2
votes
1
answer
826
views
Proving Quicksort is $O(n^2)$
So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.
I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
0
votes
2
answers
1k
views
no of times partion is called in quick sort, assuming array is always halved
In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running ...
-4
votes
1
answer
77
views
Run time for first and last index as a pivot in Quicksort?
What is the running time of quicksort if we always use the first index as the pivot? What if we always use the last index as the pivot? Is the running time $O(n)$?
3
votes
2
answers
10k
views
What is the space complexity of quicksort?
What is the space complexity of quicksort?
I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\...
1
vote
2
answers
1k
views
How does size of list in merge-sort, quick-sort, insertion-sort, matter?
We have been taught that:
Insertion-sort will best work if we have a small list.
Quick-sort will best work if we have a long list.
Merge-sort will best work if we have a huge list.
It is not ...
1
vote
1
answer
153
views
Quickly determine if insertion sort or quick sort is better
I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost ...
0
votes
2
answers
223
views
How to known which algorithm is the best for what situation, when sorting numbers?
Is there some kind of "universal list" of performance of different algorithms in different situations?
I have different databases that save user input (numbers). However some of these sets ...
0
votes
2
answers
282
views
Average case running time of quick sort
How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
1
vote
0
answers
129
views
QuickSort when the range of data is known
In QuickSort Algorithm, the pivot is chosen as the first element or a randomised element. However, if the range of data to be sorted is known, For example, from 1 to 100, and they are mostly equally ...
8
votes
2
answers
2k
views
Isn't linear time O(n)?
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22
Partition needs really linear time, not just $O(n)$ time....
0
votes
1
answer
2k
views
Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$
The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
1
vote
0
answers
82
views
Running time of random pivot quicksort on random and sorted arrays
I don't understand why I am getting the following execution times for the quicksort with a random pivot.
Times are in microseconds they are the average of five executions.
Random array: ...
-1
votes
1
answer
450
views
Time complexity of a machine which combines Insertion Sort and Quicksort
Given a machine that sorts an array of length $n$ with the following algorithm:
Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort)
Select the median of the whole ...
0
votes
0
answers
35
views
How does quicksort handle case when we choose the first number as pivot and all the remaining elements after the pivot is greater
For example, we have an array [4,7,6,13] and I choose the first item 4 as the pivot. Now I have a pointer i that goes through the array from index 1 to index 3; and I have another pointer j that ...
0
votes
0
answers
379
views
Calculating the running time of Quicksort's PARTITION procedure
I am confused about calculating the PARTITION procedure's running time.
PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$
I analyzed the PARTITION procedure ...
1
vote
0
answers
289
views
Clarification of the analysis of the worst case situation of quicksort as dealt with in CLRS
I was going through the text Introduction to Algorithms by Cormen et. al. and I came across their analysis of the worst case of the quicksort algorithm. I could not quite understand a few specific ...
2
votes
1
answer
784
views
Average number of exchanges during first partition stage in Quicksort
I am trying to understand average no of exchanges in Quicksort.
Here is the code to partition the array -
...
1
vote
1
answer
110
views
Quicksort Time Complexity
I am learning the Quicksort algorithm and I am struggling with understanding the time complexity.
Here is the JavaScript ES6 code for the partition function that is used in the algorithm:
...
1
vote
2
answers
2k
views
Show that the best case time complexity of Quicksort is $\Omega(n \log n)$
I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$.
The following recurrence describes the best-case time complexity of Quicksort:
$$T(n) = \min_{0 \le q \le n-...
2
votes
2
answers
1k
views
quicksort invariant 3 conditions with loop invariant
in studying Quicksort using the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the ...
0
votes
1
answer
202
views
Radix sort slower than Quick sort?
I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below:
...