Questions tagged [quicksort]

The tag has no usage guidance.

27 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
83 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
116 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
0answers
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 ...
2
votes
0answers
64 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
556 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
37 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 ...
1
vote
0answers
66 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
3answers
2k 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
2answers
310 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
1
vote
0answers
50 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
202 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
198 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
25 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 ...
0
votes
0answers
20 views

Quicksort with lomuto partition - how many repeating elements are too many?

I know that quicksort with Lomuto's partition method faces worst case run-time $\Theta(n^2)$ when there are many repeating elements in the array. However, I'm trying to figure out - how many ...
0
votes
0answers
42 views

Improving QuickSort Algorithm with pivot as first element

I was trying to improve the algorithm since its the most effective and known algorithm among many others, I came across " Quicksort algorithm with an early exit for sorted subfiles 1987 by University ...
0
votes
0answers
70 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
135 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
517 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 ...
0
votes
1answer
369 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
713 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
349 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
144 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
318 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
327 views

Partition algorithm average-case complexity analysis

I was given the following algorithm: ...
0
votes
0answers
274 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'...
-1
votes
1answer
201 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: ...