Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [quicksort]

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

162 questions
Filter by
Sorted by
Tagged with
1 vote
97 views

### Quick sort with $K-1$ pivots

I was thinking about quicksort with multiple pivots and I came across this question. How can we efficiently implement a version of Quicksort where we choose $k−1$ pivots to partition an array of ...
190 views

### Analysis of QuickSort Expected Time Complexity: Without Counting the Number of Comparisons

While reading CLRS (4th ed.) regarding the analysis of the expected time for QuickSort, I encountered an alternative approach. The analysis involves the following steps: Given an array of size $n$, ...
1 vote
64 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 ...
• 30.4k
1 vote
67 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. ...
69 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 ...
86 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 ...
37 views

### How to analyze quicksort

I am trying to prove that the following statements are true: ...
• 105
1 vote
27 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 ...
85 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 ...
• 257
1 vote
418 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: ...
• 505
4k 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: ...
• 505
440 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 ...
• 505
1 vote
31 views

• 9,561
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 ...
182 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: ...
• 245