Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [quicksort]

The tag has no usage guidance.

0
votes
1answer
35 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 (...
1
vote
1answer
42 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 ...
0
votes
0answers
23 views

between hoare and lomunto quicksort which give better cache performance? [duplicate]

between hoare and lomunto quicksort which give better cache performance ? we know that in hoare quicksort we move the pointer i,j in different direction but in lomunto quicksort we move i,j in same ...
1
vote
1answer
46 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
183 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
47 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
54 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
66 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
81 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
0
votes
2answers
54 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
42 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
139 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
87 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
204 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
2answers
110 views

Which algorithm is used by STL sort? [closed]

I implemented my own shellsort, shown in plot below are the timings for it. 0 means std::sort, used for comparision 1 means single thread 2 to 12 means multi-thread (pthreads) Which algorithm is ...
1
vote
0answers
25 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
176 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
29 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
35 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) = \...
3
votes
1answer
46 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
257 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 ...
3
votes
1answer
117 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
276 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
72 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
140 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?
13
votes
4answers
4k 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
136 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
323 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
227 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
87 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 ...
0
votes
2answers
52 views

Quick sort analysis confusion

Is randomized quick sort runtime is independent of the sequence of input? but depends on the numbers in the input? Let say A1 = [1,2,3,4,5] , A2 = [5,2,3,4,1] A3 = [5,4,3,2,1] , Will the randomized ...
3
votes
1answer
622 views

How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?

All variable names are from Quicksort's wikipedia page's Lomuto's and Hoare's quick sorts pseudocode. If p is what is returned by the ...
1
vote
2answers
74 views

quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$? [closed]

Below is an excerpt from Khan Academy's Quick Sort Analysis page. In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each ...
2
votes
1answer
383 views

How to understand the analysis of expected running time of randomized quick-sort in this paper?

I'm learning the book named Data Structures & Algorithms in Python. On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me ...
0
votes
0answers
180 views

How to calculate the depth of the call stack for the average case of quicksort

In the best case of quicksort the depth of the call stack is measured by $\lceil\log_2 n\rceil$ if I am not wrong. What would be the formula for calculating the depth of the call stack in case of an ...
3
votes
2answers
588 views

Why are unbalanced partitions worse than balanced partitions in Quicksort?

I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions. After reading this document it shows that worse case partitions are of the type $(0,(n-1)),...
0
votes
0answers
71 views

Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
1
vote
2answers
407 views

Quicksort dual pivot or single

I've seen to explanations for the quick sort algorithm. One in which a pivot is chosen, and put into place, before both sides of the pivot are recursively pivot-sorted. Another involved a more ...
1
vote
1answer
416 views

Proof that quicksort's running time is ∼1.39 n log n

In the fourth edition of Sedgewick's Algorithms, it's claimed that the running time of QuickSort is $\sim 1.39n\log_2 n$. I'm trying to find a "simple" proof and explanation of this. All I know is ...
1
vote
1answer
281 views

Selection of pivot in quicksort partitioning of Hoare and Lomuto

There are two commonly mentioned partition methods: ...
2
votes
3answers
140 views

Confusion about the definition of the average-case running time of algorithms

In this lecture note, The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T_{\text{average-case}}(n) ...
0
votes
0answers
240 views

Modification of Lomuto's Quicksort algorithm to reduce swaps

Its well known that Lomuto's partitioning algorithm results in too many unnecessary swaps. Can we modify the algorithm in this way: Initialize a pointer a that points to the first position in the ...
5
votes
0answers
80 views

What are applications to sort plain integer arrays?

A lot of research and engineering effort is put into finding fast methods to sort an array of integers; e.g., Java's runtime library has highly-tuned methods to sort arrays of each primitive type (see ...
11
votes
2answers
1k views

Finding k'th smallest element from a given sequence only with O(k) memory O(n) time

Suppose that we read a sequence of $n$ numbers, one by one. How to find $k$'th smallest element just with using $O(k)$ cell memory and in linear time ($O(n)$). I think we should save first $k$ terms ...
0
votes
0answers
236 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
1
vote
2answers
421 views

Does quicksort for increasing order work faster if the input set is more decreasing sorted?

In CLRS's Introduction to Algorithms, The following procedure implements quicksort: ...
9
votes
3answers
5k views

Trying to understand this Quicksort Correctness proof

This proof is a proof by induction, and goes as follows: P(n) is the assertion that "Quicksort correctly sorts every input array of length n." Base case: every input array of length 1 is already ...
5
votes
1answer
7k views

Solving Recurrence Relation (quicksort )

I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$ However trying to solve for it I get something different and I am not sure why that is. Ok, so solving recurrence relations can be ...
-1
votes
1answer
2k views

Stack depth for QuickSort

CLRS Problem : 7.4 How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ? Original quicksort Tail recursive quicksort Question ...
2
votes
1answer
52 views

Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

I am experimenting with the sorting of arrays and their execution times. While using bubblesort, insertsort and ...