# Questions tagged [quicksort]

Sorting algorithm based on recursive partitioning devised by Hoare (ACM Algorithm 63) with fast average case running time.

154 questions
Filter by
Sorted by
Tagged with
20 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 ...
14 views

### change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
38 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: ...
473 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: ...
97 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 ...
18 views

207 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 ...
68 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: ...
96 views

### Improving QuickSort Algorithm with pivot as first element

I was trying to improve the algorithm since its the most effective and known algorithm among many others, I came across " Quicksort algorithm with an early exit for sorted subfiles 1987 by University ...
265 views

### Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
2k views

### Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
1k views

### Analysing worst-case time complexity of quick-sort in different cases

I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across: When array is already sorted in either ascending order or descending order and we ...
75 views

### Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning

In the book Introduction to Algorithms (3th edition) chapter 7 the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$ as the worst-case happens ...
48 views

### How to predict the number of comparisons done by QuickSort if you know the percentage to which the array is pre-sorted?

I've noticed that correlating the number of comparisons done by a naive implementation of QuickSort with the percentage of elements that were already sorted gives you a curly-brace-shaped-curve if you ...
346 views

### Quick Sort Equal to or Less Than

For my course I have to memorise a number of algorithms and to know how to perform them by hand. The steps of the quick sort are given as the following in the text book I am using: Choose the item at ...
449 views

### What is the worst case for C++ "sort" function?

So, what is the worst case for C++ "sort" function, when does it go to O(n^2) time? I know it's QuickSort, therefore, it's very fast in most cases, but it gets to O(n^2) in special cases. I've tried ...