Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [quicksort]

The tag has no usage guidance.

106 questions
Filter by
Sorted by
Tagged with
30 views

What is the probability of comparision between smallest and greatest element in array when quick sort randomly choose the pivot element?

Consider the recursive quick sort with random pivoting i.e. each time a random pivot element is chosen uniformly. When this ...
35 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
36 views

Average Case Running Time of Quicksort Algorithm

From this website, it states that the average case of Quicksort algorithm is T(n) = T(n/9) + T(9n/10) + θ(n) Im a bit confused. Is it supposed to be ? ...
111 views

Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

Wikipedia here https://en.m.wikipedia.org/wiki/Selection_algorithm shows an algorithm using sort of quicksort.. in order to find Kth largest or smallest element taking O(n) time only on average. The ...
34 views

Quicksort Algorithm with Pivot element as Median

I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are ...
52 views

Quicksort where element comparison outcome is random. Probability of element being in a certain position

So we have this block of pseudocode: Monsters = [M1,M2,M3,M4,M5,M6,M7,M8]; qsort(Monsters,rand_compare); qsort() sorts the ...
49 views

Quick sort worst case complexity improvement [closed]

Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?
78 views

Worst Case Scenario for Quicksort algorithm with pivot element n/2

What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element? I know that if I choose the left or rightmost element as pivot ,the ...
56 views

Big O: Analyzing the time complexity of an $O(n \log n)$-algorithm

For homework, the task is to verify the time complexity of quicksort. User Nick suggested on quora that one could check the number of comparisons made when doubling the input size. If the comparisons ...
222 views

Is there a sorting algorithm of order $n + k \log{k}$?

I'm given an integer vector which is said to contain many duplicate values (total of k distinct integers), for example ...
62 views

Proof for Unusual QuickSort Partition Scheme

TL:DR I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort? The following is code I wrote for a middle pivot ...
102 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
46 views

Quicksort with Hoare's Partition Algorithm

I've came across Hoare's partition algorithm in Cormen. After analysis I think that the algorithm isn't working as I expected. Let's suppose that we've array [4,3,2,1], then in my opinion partition ...
62 views

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 ...
166 views

Hoare's Partition Scheme Stuck

I'm tracing through a quick sort algorithm on paper, but I keep getting stuck on the partitioning using Hoare's partitioning. The array is {3,1,4,1,5,9,2,6,5,3,5}. ...
389 views

How to get the optimized quicksort algorithm's time complexity

I learned in my data structures class that QuickSort can be optimized by calling the InsertionSort method when the length of the subarray is less than a certain threshold. However, when it comes to ...