# Questions tagged [quicksort]

The tag has no usage guidance.

124 questions
Filter by
Sorted by
Tagged with
28 views

### Time complexity of a machine which combines Insertion Sort and Quicksort

Given a machine that sorts an array of length $n$ with the following algorithm: Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort) Select the median of the whole ...
25 views

### How does quicksort handle case when we choose the first number as pivot and all the remaining elements after the pivot is greater

For example, we have an array [4,7,6,13] and I choose the first item 4 as the pivot. Now I have a pointer i that goes through the array from index 1 to index 3; and I have another pointer j that ...
34 views

### Calculating the running time of Quicksort's PARTITION procedure

I am confused about calculating the PARTITION procedure's running time. PARTITION procedure is used in the Quicksort Algorithm to partition the array $A[p...r]$ I analyzed the PARTITION procedure ...
42 views

### Clarification of the analysis of the worst case situation of quicksort as dealt with in CLRS

I was going through the text Introduction to Algorithms by Cormen et. al. and I came across their analysis of the worst case of the quicksort algorithm. I could not quite understand a few specific ...
160 views

### Average number of exchanges during first partition stage in Quicksort

I am trying to understand average no of exchanges in Quicksort. Here is the code to partition the array - ...
28 views

### Quicksort Time Complexity

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity. Here is the JavaScript ES6 code for the partition function that is used in the algorithm: ...
36 views

29 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 ...
123 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 ...
172 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 ...
103 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 ...
61 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: ...
117 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 ? ...
399 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 ...
177 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 ...
102 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 ...
233 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?
353 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 ...
68 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 ...
822 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 ...
87 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 ...
119 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 ...
72 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 ...
71 views

2k views

### Running time of median of 3 partioning

I am hoping someone can break something down for me in a way I can digest. I am trying to understand the running time for the median of three partitioning. What is the goal of median of three ...
354 views

### What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...