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.

22 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
82 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 ...
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 ...
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 ...
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 ...
2
votes
0answers
538 views

Quick Select explanation

I have been looking for a quick and easy explanation on Quick Select and stumbled upon this. It's quick and easy to follow, but there's a part which I am not following quite well: The uploader is ...
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 $...
1
vote
0answers
205 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
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: ...
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?
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
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 ...
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 ...
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 ...
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 ...
0
votes
0answers
268 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 ...
0
votes
0answers
120 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)?
0
votes
0answers
292 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 ...
0
votes
0answers
296 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
0
votes
0answers
247 views

Dijkstra's Quicksort Algorithm

How does Dijkstra's Quicksort Algorithm perform better than the original Quicksort Algorithm in terms of memory usage,number of exchanges made and time taken? original quicksort refers to Tony Hoare'...
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 ...
-1
votes
1answer
185 views

Quick Sort Algorithm When Partition is Constant Time

I ran into a question about Quick Sort Algorithm. Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
-2
votes
1answer
251 views

Quicksort implementation unclear

This code is taken from wikipedia: ...