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.

Filter by
Sorted by
Tagged with
0
votes
1answer
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 ...
1
vote
2answers
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: ...
1
vote
1answer
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 ? ...
3
votes
2answers
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 ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
4
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
62 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
0
votes
2answers
61 views

Is it possible to make partition of Quicksort run in O(lg n)?

I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.
0
votes
1answer
70 views

QuickSort of linked lists optimised for duplicates

This is an past year question for a school exam that I do not suggested solutions for. Problem Description Quick Sort is not stable because of need to swap values in array when partition is done. If ...
1
vote
1answer
2k views

Implementation of QuickSort to handle duplicates

I have this past year question based on the following scenario: When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
0
votes
2answers
86 views

Time complexity of quicksort for arrays in increasing or descreasing order

Two $n$-size arays are given: $n_1$ is in decreasing order and $n_2$ is in increasing order. Let $c_1$ be the time complexity for $n_1$ using quicksort, and $c_2$ the time complexity for $n_2$ using ...
2
votes
2answers
391 views

Recurrence relation of quicksort depending on its pivot

I understand how the recurrence relation of quicksort is $T(n) = 2T(n/2)+\mathcal{O}(n)$, but if we are guaranteed a certain pivot, for example $n/4$th smallest element to be the pivot every time, ...
0
votes
1answer
181 views

Merge sort and quicksort recursion tree depth

1) I need to determine recursion tree depth for strings composed of 10, 100 and 1000 elements when using merge sort. For the 10 elements one/I can do it on a paper, just drawing tree, but what about ...
1
vote
2answers
284 views

Proof of QuickSort algorithm correctness

Recently I’ve studied QuickSort and understood its general idea. Basically, we do the following: Pick an element from the array (no matter which one and how in this context) Rearrange elements in ...
2
votes
3answers
1k views

When average , worst and best case time complexity happens in quick sort?

I know recurrence relation corresponding to quick sort worst case is $T(n)=T(n-1)+T(0)+\Theta(n)$ and time complexity is $O(n^2)$. This happens when we select pivot which is either largest element ...
1
vote
1answer
490 views

Quick Sort - First Element As Pivot

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point. I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot (...
2
votes
2answers
224 views

algorithm to find all values that occur more than n/10 times

I took an algorhytm course on coursera and there some optional questions for student enrichment. I can't solve the following task: Decimal dominants. Given an array with n keys, design an algorithm ...
1
vote
1answer
199 views

In this implementation of Hoare-partitioning Quicksort, why are additional checks for $i \leq j$ needed?

I am looking at the following implementation of Quicksort that uses Hoare partition scheme (two approaching indices $i$ and $j$ starting from either end of the array). I am having trouble seeing why ...
0
votes
2answers
5k views

Quick Sort with first element as pivot

I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point. I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot S[...
1
vote
1answer
248 views

Finding the Kth largest element can be optimized to O(n) only if k is a constant?

There's a famous question posted on this site which asks about finding the $k$th largest element. Many answers are written there which optimized it and found algorithms with expectation of $O(n)$. ...
2
votes
0answers
62 views

Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
0
votes
2answers
871 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 ...
1
vote
0answers
205 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
0
votes
2answers
59 views

Understanding how quicksort operates

I am having a hard time understanding the quick sort partition operation. I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand ...
-3
votes
1answer
44 views

Please help, I have been attempting to understand Quicksort for 9 hours now with little luck!

I have done absolutely everything that i could to try to understand this algorithm. I did NOT want to go on without understanding it completely even though I know it might only be a single problem in ...
4
votes
1answer
824 views

Hoare partitioning scheme in Quicksort

I'm reading about Quicksort algorithm, specifically using the Hoare partitioning scheme. Wikipedia page says, that when choosing a pivot element one can use both ...
1
vote
1answer
237 views

quicksort recurrence relation

In Concrete Mathematics Textbook by Donald Knuth and Oren Patashnik , ch.2 Sum ,sec2.2 He wrote: The average number of comparison steps made by quicksort when it's applied to $n$ items in random ...
5
votes
1answer
653 views

Randomized quicksort expected running time analysis

I am following the quicksort analysis in CLRS (pp. 181-184, 3rd edition). Let me summarize the setting of the analysis. Setting in CLRS First let $Z = \{z_1, ..., z_n\}$ be the set of elements of ...
1
vote
0answers
43 views

Tiny question about Coding conventions for Lomuto partition code

Just out of curiousity: Both Introduction to Algorithms (Cormen et al), Wikipedia, and prior cs.stackexchange questions all present the Lomuto partition as: ...
0
votes
2answers
344 views

Question regarding Hoare's partitioning scheme and a slight modification to it

This is the pseudocode on wikipedia for Hoare's partitioning scheme: ...
0
votes
0answers
185 views

Sorting an array of length n with k distinct elements in O(kn) [duplicate]

I have an array of the size N with K distinct elements.We don't know what the K is. I would like to sort this array in O(kn). I have found this answer and I would like to understand what does exactly @...
1
vote
1answer
82 views

Number of calls with length 2 array in quick-sort

I need to find average number of recursive calls in quick-sort with array of length 2. I established and solved the following recursion: $$T_N = \frac{1}{N}\sum_{k=1}^N\left(T_{k-1}+N_{N-k}\right) = \...
2
votes
1answer
83 views

An algorithm for k-way array partitioning

I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s_1, s_2, \cdots, s_{n-1}$ into $n$ subsequences, where subsequence $i$ all ...
0
votes
2answers
428 views

What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?

If I were to sort the list of numbers 1,7,5,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at ...
2
votes
1answer
206 views

Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs?

I know that the time complexity of quick sort in the worst case is $\Theta(n^2)$ and in the average case is $\Theta(n \log n)$. Can it be $\Theta(n\sqrt n)$ for certain inputs?
3
votes
2answers
507 views

how to bound the probability that quicksort takes greater than n lg n time?

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed) Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
0
votes
2answers
102 views

Good reference for average-case runtime analysis of QuickSort

I'm a beginner in programming with little knowledge about the technicalities. I'm assigned to do a "reading project" on the average case analysis of quicksort. I mean I have to present it in class. ...
1
vote
0answers
190 views

Scenarios where merge sort is preferred over quick sort

As merge sort and quicksort both have the same average time complexity of $O(n \log(n))$. In which scenarios would merge sort be preferred over quicksort when sorting data?
16
votes
4answers
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 ...
1
vote
0answers
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}. ...
0
votes
1answer
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 ...
0
votes
0answers
549 views

Expectation for the number of comparisons in a randomized Quicksort

I found this link: http://theory.stanford.edu/~tim/w11/l/qsort.pdf and it kind of theoretically describes how to approach finding expectation for the number of comparisons in a Quicksort. Using ...
2
votes
1answer
100 views

Quick groupby - is this a well known algorithm?

I am interested in an algorithm that accepts an array that places identical elements contiguously but the array doesn't necessarily have to be sorted. E.g. if input is ...