Questions tagged [quicksort]

The tag has no usage guidance.

106 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
827 views

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'...
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 ...
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 ...
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 ...
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:...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
251 views

Quicksort implementation unclear

This code is taken from wikipedia: ...
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 ...
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 ...
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 ...
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: ...
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 ...