The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [quicksort]

The tag has no usage guidance.

106 questions
Filter by
Sorted by
Tagged with
59k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: ...
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 ...
6k views

Why don't we use quick sort on a linked list?

Quick sort algorithm can be divided into following steps Identify pivot. Partition the linked list based on pivot. Divide the linked list recursively into 2 parts. Now, if I always choose last ...
4k views

Is transitivity required for a sorting algorithm

Is it possible to use a sorting algorithm with a non-transitive comparison, and if yes, why is transitivity listed as a requirement for sorting comparators? Background: A sorting algorithm generally ...
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 ...
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 ...
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: ...
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 ...
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: ...
335 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 ...
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 ...
1k views

709 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 ...
100 views

Quick groupby - is this a well known algorithm?

I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted. E.g. if input is ...
882 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 ...
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 ...
120 views

424 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 ...