Questions tagged [quicksort]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
20 views

Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$. The following recurrence describes the best-case time complexity of Quicksort: $$T(n) = \min_{0 \le q \le n-...
1
vote
2answers
296 views

What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
1
vote
2answers
29 views

quicksort invariant 3 conditions with loop invariant

in studying Quicksort using the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein, they describe in order to show correctness, an invariant must hold for the 3 stages of the ...
0
votes
1answer
26 views

Radix sort slower than Quick sort?

I would like to demonstrate that sometime radix-sort is better than quick-sort. In this example I am using the program below: ...
0
votes
0answers
12 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 ...
1
vote
2answers
75 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 ...
0
votes
0answers
30 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 ...
1
vote
1answer
52 views

Quick Sort vs Radix Sort

In an coding exam, I was once asked this question: Assuming that you are only sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you ...
1
vote
2answers
170 views

Probability that two elements are compared in randomized quicksort

I am having an issue in a specific part of the randomized quick-sort analysis. As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
0
votes
1answer
113 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
2answers
448 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 ...
89
votes
2answers
64k views

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: (the argument A is the array, and [p, r] is the range, inclusive,...
2
votes
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 ...
0
votes
1answer
345 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 ...
2
votes
2answers
101 views

Can a relatively small subset of random numbers be permuted and reused and still guarantee good expected running time for an algorithm like quicksort?

So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring ...
1
vote
2answers
434 views

Analysing worst-case time complexity of quick-sort in different cases

I am trying to understand worst case time complexity of quick-sort for various pivots. Here is what I came across: When array is already sorted in either ascending order or descending order and we ...
0
votes
2answers
61 views

Why guess $\Theta(n^2)$ for the substitution method of worst-case partitioning

In the book Introduction to Algorithms (3th edition) chapter 7 the recurrence of the running time of quicksorts partitioning is given by $$T(n) = T(n-1) + \Theta(n)$$ as the worst-case happens ...
2
votes
0answers
28 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 ...
1
vote
2answers
74 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 ...
0
votes
1answer
127 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 ...
18
votes
4answers
53k views

Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Randomized Quick Sort is an extension of Quick Sort in which the pivot element is chosen randomly. What can be the worst case time complexity of this algorithm. According to me, it should be $O(n^2)$, ...
0
votes
1answer
52 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
55 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: ...
4
votes
1answer
115 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
2answers
536 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
60 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
338 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
74 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
82 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
162 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?
1
vote
1answer
663 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 (...
0
votes
1answer
228 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 ...
2
votes
1answer
493 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
67 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
583 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
81 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 ...
0
votes
0answers
67 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
65 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.
1
vote
1answer
5k 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 ...
1
vote
2answers
468 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
2answers
758 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, ...
16
votes
4answers
8k 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
1answer
314 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
9k 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
290 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
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 ...
-3
votes
1answer
45 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
1k 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 ...