Questions tagged [quicksort]

Sorting algorithm based on recursive partitioning devised by Hoare (ACM Algorithm 63) with fast average case running time.

Filter by
Sorted by
Tagged with
2
votes
1answer
30 views

Hoare partition scheme may cause infinite recursion

Wiki states: "...partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion." What prevents Hoare ...
0
votes
3answers
82 views

Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
2
votes
1answer
40 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
1
vote
1answer
19 views

Is there a way to find the correct element in the array for the given index x?

In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element). Is there any algorithm to find correct element for a given index ? Here, correct index of an ...
0
votes
1answer
27 views

How to arrange a sub-array for Quick sorting algorithm?

Alghorithm : Quick sort . idea : devide and conqure . steps : 1- find the pivot point from array like first element . 2- partiotioning the array so that elements are smaller than pivot point are in ...
-1
votes
1answer
34 views

Number of comparisons in Quicksort

So would it be correct to say that the number of comparisons from level 1 to level 2 would be $2(n/2-1)$? Or would it be more correct to say that the number of comparisons is $2^i(n/2^i-1)$?
2
votes
2answers
36 views

Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements. Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$. Furthermore, ...
0
votes
1answer
51 views

Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?

The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS. Problem 7-1.b Hoare's partition algorithm from the book. Part b: Assuming the subarray $A[p,...
2
votes
1answer
40 views

Proving Quicksort is $O(n^2)$

So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$. I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following ...
0
votes
2answers
42 views

no of times partion is called in quick sort, assuming array is always halved

In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1. The recurrence for the running ...
-4
votes
1answer
24 views

Run time for first and last index as a pivot in Quicksort?

What is the running time of quicksort if we always use the first index as the pivot? What if we always use the last index as the pivot? Is the running time $O(n)$?
1
vote
2answers
158 views

What is the space complexity of quicksort?

What is the space complexity of quicksort? I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\...
1
vote
2answers
160 views

How does size of list in merge-sort, quick-sort, insertion-sort, matter?

We have been taught that: Insertion-sort will best work if we have a small list. Quick-sort will best work if we have a long list. Merge-sort will best work if we have a huge list. It is not ...
0
votes
0answers
18 views

TAoCP on quicksort: What are the differences between printings/editions?

In a footnote to the preface of "The Art of Computer Programming - Sorting and Searching", D. E. Knuth writes in a copy copyrighted 1973: In this second printing […] The section on ...
1
vote
1answer
42 views

Quickly determine if insertion sort or quick sort is better

I'm in a scenario where ~30% of the time, my array is almost completely sorted, and the other 70% of the time, it is basically completely random. I want to quickly determine if my list is almost ...
0
votes
0answers
27 views

How to known which algorithm is the best for what situation, when sorting numbers?

Is there some kind of "universal list" of performance of different algorithms in different situations? I have different databases that save user input (numbers). However some of these sets ...
0
votes
2answers
107 views

Average case running time of quick sort

How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ? Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
1
vote
0answers
41 views

QuickSort when the range of data is known

In QuickSort Algorithm, the pivot is chosen as the first element or a randomised element. However, if the range of data to be sorted is known, For example, from 1 to 100, and they are mostly equally ...
8
votes
2answers
1k views

Isn't linear time O(n)?

In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22 Partition needs really linear time, not just $O(n)$ time....
0
votes
1answer
136 views

Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

The question is clear in the title. I am trying to solve this recursion as a part of showing that the worst case of quicksort algorithm occurs when $k=0$, but can't do it. I could do the following ...
1
vote
0answers
28 views

Running time of random pivot quicksort on random and sorted arrays

I don't understand why I am getting the following execution times for the quicksort with a random pivot. Times are in microseconds they are the average of five executions. Random array: ...
-1
votes
1answer
118 views

Time complexity of a machine which combines Insertion Sort and Quicksort

Given a machine that sorts an array of length $n$ with the following algorithm: Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort) Select the median of the whole ...
0
votes
0answers
27 views

How does quicksort handle case when we choose the first number as pivot and all the remaining elements after the pivot is greater

For example, we have an array [4,7,6,13] and I choose the first item 4 as the pivot. Now I have a pointer i that goes through the array from index 1 to index 3; and I have another pointer j that ...
0
votes
0answers
67 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 ...
1
vote
0answers
75 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 ...
2
votes
1answer
268 views

Average number of exchanges during first partition stage in Quicksort

I am trying to understand average no of exchanges in Quicksort. Here is the code to partition the array - ...
1
vote
1answer
52 views

Quicksort Time Complexity

I am learning the Quicksort algorithm and I am struggling with understanding the time complexity. Here is the JavaScript ES6 code for the partition function that is used in the algorithm: ...
1
vote
2answers
236 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
111 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
56 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
81 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
200 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
1k 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 ...
1
vote
2answers
1k 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
70 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
35 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
250 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
383 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 ...
0
votes
1answer
239 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
82 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: ...
2
votes
1answer
226 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
580 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
841 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
146 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
314 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
517 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
71 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
1k 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
96 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 ...
5
votes
1answer
122 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 ...