Questions tagged [quicksort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
2answers
62 views

Quick sort analysis confusion

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input? Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized ...
3
votes
1answer
845 views

How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?

All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode. If p is what is returned by the ...
1
vote
2answers
84 views

quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$? [closed]

Below is an excerpt from Khan Academy's Quick Sort Analysis page. In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each ...
2
votes
1answer
867 views

How to understand the analysis of expected running time of randomized quick-sort in this paper?

I'm learning the book named Data Structures & Algorithms in Python. On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me ...
0
votes
0answers
267 views

How to calculate the depth of the call stack for the average case of quicksort

In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...
2
votes
2answers
827 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
0
votes
0answers
119 views

Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
1
vote
2answers
632 views

Quicksort dual pivot or single

I've seen to explanations for the quick sort algorithm. One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted. Another involved a more ...
1
vote
1answer
575 views

Proof that quicksort's running time is ∼1.39 n log n

In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this. All I know is ...
1
vote
1answer
378 views

Selection of pivot in quicksort partitioning of Hoare and Lomuto

There are two commonly mentioned partition methods: ...
2
votes
3answers
167 views

Confusion about the definition of the average-case running time of algorithms

In this lecture note, The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T_{\text{average-case}}(n) ...
0
votes
0answers
290 views

Modification of Lomuto's Quicksort algorithm to reduce swaps

Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way: Initialize a pointer a that points to the first position in the ...
5
votes
0answers
82 views

What are applications to sort plain integer arrays?

A lot of research and engineering effort is put into finding fast methods to sort an array of integers; e.g., Java's runtime library has highly-tuned methods to sort arrays of each primitive type (see ...
11
votes
2answers
2k views

Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms ...
0
votes
0answers
292 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
1
vote
2answers
624 views

Does quicksort for increasing order work faster if the input set is more decreasing sorted?

In CLRS's Introduction to Algorithms, The following procedure implements quicksort: ...
10
votes
3answers
7k views

Trying to understand this Quicksort Correctness proof

This proof is a proof by induction, and goes as follows: P(n) is the assertion that "Quicksort correctly sorts every input array of length n." Base case: every input array of length 1 is already ...
5
votes
1answer
11k views

Solving Recurrence Relation (quicksort )

I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$ However trying to solve for it I get something different and I am not sure why that is. Ok, so solving recurrence relations can be ...
-1
votes
1answer
2k views

Stack depth for QuickSort

CLRS Problem : 7.4 How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ? Original quicksort Tail recursive quicksort Question ...
2
votes
1answer
54 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...
2
votes
1answer
3k views

Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also ...
5
votes
2answers
968 views

Why does the recurrence equation for QuickSort consider all the elements in the array?

I have been taught that QuickSort has the following recurrence equation in the best case: $T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \...
2
votes
1answer
126 views

Quicksort $T(n)_{best}=\Omega(n\log n) $ proof

About the proof that quicksort has $T(n)_{best}=\Omega(n\log n)$. I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't ...
2
votes
1answer
120 views

Probability bounds on size of smaller partition in randomized quicksort

Let $0 < a < 0.5$ be some constant. We have an $n$-element array as input. Randomized quicksort chooses one element from array uniformly at random as a pivot and partitions. With probability $1-...
4
votes
2answers
2k views

Optimal pivot selection for quick-sort

The actual runtime of applying quick-sort to an integer array heavily relies on the choice of pivots. It is well known that picking a random pivot does not work as good as taking the median of three, ...
2
votes
1answer
967 views

How to understand the storing mechanism used in external merge sort

I was reading about external merge sort from the wikipedia article link, according to it: External sorting is required when the data being sorted do not fit ...
4
votes
1answer
72 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + (...
2
votes
0answers
423 views

How to understand the formal analysis of quickselect? [closed]

According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof ...
0
votes
1answer
221 views

Quicksort bounds

I found an implementation of Quicksort here, and now I cannot understand why it works with those left and right bounds. Right now the link above is unavailable due to some problems with their hosting ...
0
votes
1answer
64 views

Which element is at its final position after the partitioning step in Quicksort?

In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position. The entry a[j] is in its final place in the array, for some j. No entry in a[lo] ...
2
votes
1answer
84 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
2
votes
1answer
486 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 $...
0
votes
0answers
247 views

Dijkstra's Quicksort Algorithm

How does Dijkstra's Quicksort Algorithm perform better than the original Quicksort Algorithm in terms of memory usage,number of exchanges made and time taken? original quicksort refers to Tony Hoare'...
4
votes
2answers
766 views

Why does quicksort work well with virtual memory?

Introduction to Algorithms said that quicksort "works well even in virtual-memory environments," but didn't explain why. I've tried looking an Wikipedia and Stack Exchange, but found no reason why. Is ...
5
votes
5answers
5k views

Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?

I fail to understand why cut off value would be system dependent, and not a constant. From Princeton University website Cutoff to insertion sort. As with mergesort, it pays to switch to ...
17
votes
4answers
46k views

Why does randomized Quicksort have O(n log n) worst-case runtime cost?

Randomized Quick Sort is an extension of Quick Sort in which pivot element is chosen randomly. What can be the worst case time complexity of this algo. According to me it should be $O(n^2)$. Worst ...
2
votes
3answers
3k views

What happened if we implement quicksort without tail recursion?

On Wikipedia, it said that The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:...
1
vote
1answer
179 views

Asymptotic analysis for quicksort on special case

I have the following problem for homework: Given an array of the form $[m+1, m+2,..., n, 1, 2,..., m]$ as an input, analyze quicksort's run time complexity. TIP: check for $m > \frac{n}{2}$ and ...
7
votes
1answer
2k views

Would using the mean as pivot speed up quicksort?

Somehow I thought about quicksort last night and was reading about it on Wikipedia. The interesting part for me was: 'If we could consistently choose a pivot from the middle 50 percent, we would only ...
6
votes
2answers
332 views

Which measure of sortedness explains the phase transition in Quicksort's runtime?

I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is ...
-2
votes
2answers
2k views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
-1
votes
1answer
185 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
3
votes
1answer
2k views

Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

For Hoare's partitioning algorithm quicksort is implemented as such ...
-2
votes
1answer
251 views

Quicksort implementation unclear

This code is taken from wikipedia: ...
2
votes
1answer
705 views

Cost of partitioning in quicksort

I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple. When talking about ...
1
vote
2answers
4k views

Dual-pivot Quicksort reference implementation?

Has some sort of canonical - or reference - implementation of Dual-pivot Quicksort been posted anywhere? I would like to include that algorithm in a comparison among sorting algorithms for a ...
4
votes
2answers
364 views

Performance impact due to time required for shuffling in Quicksort

As a programmer with non CS background, I am learning algorithms. When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the ...
7
votes
2answers
9k views

Why is Quicksort described as “in-place” if the sublists take up quite a bit of memory? Surely only something like bubble sort is in-place?

Quicksort is described as "in-place" but using an implementation such as: ...
6
votes
4answers
9k views

QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens: ...
0
votes
2answers
178 views

Quicksort's asymptotic performance for array of [50,…,50,100,…100]

Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort. I think it it should be $O(n^2)$ as for array of ...