# Questions tagged [quicksort]

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

160 questions
Filter by
Sorted by
Tagged with
1 vote
38 views

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
47 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. ...
42 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 ...
57 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 ...
62 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 ...
35 views

### How to analyze quicksort

I am trying to prove that the following statements are true: ...
1 vote
26 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 ...
84 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
143 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 ...
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
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: ...
3k 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: ...
295 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
29 views

1 vote
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 ...
159 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: ...
126 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 ...
1 vote
879 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 ...
1 vote