Recent questions tagged quick-sort / GATE Overflow for GATE CSE

0 votes

3 answers

1

GATE DS&AI 2024 | Question: 20
Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that uses the last element as the pivot. \begin{array}{|l|l|l|l|l|} \hline 60 & 70 & 80 & 90 & 100 \\ \hline \end{array} The minimum number of swaps performed during this Quicksort is $\_\_\_\_\_\_\_\_$.

Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that uses the last element as the pivot.\begin{array}{|l|l|l|l|l|...

Arjun

1.2k views

Arjun asked Feb 16

1 votes

1 answer

2

Memory Based GATE DA 2024 | Question: 25
Consider the QuickSort algorithm with the last element chosen as the pivot. If the goal is to sort the given array $a = [30, 40, 50, 60, 70, 80]$ in ascending order, how many swaps will occur during the execution of the algorithm?

Consider the QuickSort algorithm with the last element chosen as the pivot. If the goal is to sort the given array $a = [30, 40, 50, 60, 70, 80]$ in ascending order, ho...

GO Classes

275 views

GO Classes asked Feb 4

5 votes

2 answers

3

GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 29
Consider an array that has $10$ distinct elements. Suppose we use randomized quicksort (with the pivot chosen uniformly at random). What is the probability that the partition method will result in an array such that the size of the ... the left and one on the right of the chosen pivot. The pivot itself is not part of any subarray.

Consider an array that has $10$ distinct elements. Suppose we use randomized quicksort (with the pivot chosen uniformly at random). What is the probability that the parti...

GO Classes

656 views

GO Classes asked Jan 21

0 votes

1 answer

4

Quick sort
13, 60,19,52,45,27,41,30,34,32.. Is this sequence in an array a worst case for Quicksort if first element is choosen as pivot always? I have tried to run algorithm of Quicksort on this sequence but not getting it.. Can anyone please explain this? My ... hence for whole array it would not be a worst of if sorting using Quicksort.. Can someone please tell me where I am thinking wrong??

13, 60,19,52,45,27,41,30,34,32.. Is this sequence in an array a worst case for Quicksort if first element is choosen as pivot always?I have tried to run algorithm of Quic...

Kanha3112

399 views

Kanha3112 asked Sep 12, 2023

1 votes

1 answer

5

Made Easy Test Series 2024
Which of the following statement(s) is/are true? (a) Quicksort and merge sort are both examples of divide and conquer algorithms. (b) If we randomly choose a pivot element each time, quicksort will always terminate in time $O(n log n).$ (c) For every fixed ... in time $O(1)$, quicksort would have worst case complexity $O(n log n)$. plese give answer and explain it why ?

Which of the following statement(s) is/are true?(a) Quicksort and merge sort are both examples of divide and conquer algorithms.(b) If we randomly choose a pivot element ...

Ray Tomlinson

860 views

Ray Tomlinson asked Aug 9, 2023

3 votes

2 answers

6

In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?

In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?a) Partition always divides the array into two non-empty subsets.b) ...

dhruba

1.0k views

dhruba asked Jun 5, 2023

0 votes

1 answer

7

Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?

Consider performing QuickSort on an array of n distinct elements. What is the probability that no comparisons will be made between the smallest and largest element?a. 1/n...

dhruba

444 views

dhruba asked Jun 5, 2023

0 votes

2 answers

8

Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]
Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]

Sort the following array using quicksort algorithm. [40,11,4,72,17,2,49]

Ajink123

555 views

Ajink123 asked May 10, 2023

1 votes

1 answer

9

GO Classes 2023 | IIITH Mock Test 1 | Question: 43
Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$ Which of these element(s) could have been the pivot element? $4$ $5$ $2$ $9$

Recall the Partition subroutine that we used in QuickSort. Suppose that the following array has just been partitioned around some pivot element $: 3,1,2,4,5,8,7,6,9.$Whic...

GO Classes

878 views

GO Classes asked Mar 26, 2023

0 votes

1 answer

10

Quicksort
In Quick sort of the following numbers, if the pivot is chosen as the first element, what will be the order of the numbers after the use of partition function ? Assume we are sorting in increasing order. 11, 15, 9, 13, 17, 7, 5, 12, 6, 18

In Quick sort of the following numbers, if the pivot is chosen as the first element, what will be the order of the numbers after the use of partition function ? Assume we...

someshawasthi

597 views

someshawasthi asked Nov 25, 2022

0 votes

2 answers

11

UGC NET CSE | October 2022 | Part 1 | Question: 74
Which of the following algorithm design approach is used in Quick sort algorithm? Dynamic programming Back Tracking Divide and conquer Greedy approach

Which of the following algorithm design approach is used in Quick sort algorithm?Dynamic programmingBack TrackingDivide and conquerGreedy approach

admin

342 views

admin asked Oct 23, 2022

1 votes

2 answers

12

#Quicksort
In Quicksort of the following numbers, if the pivot is chosen as the first element, what will be the order of the numbers after the use of partition function? Assume we are sorting in increasing order. 11, 15, 9, 13, 17, 7, 5, 12, 6, 18

In Quicksort of the following numbers, if the pivot is chosen as the first element, what will be the order of the numbers after the use of partition function? Assume we a...

Nitesh_Yadav

466 views

Nitesh_Yadav asked Apr 8, 2022

3 votes

2 answers

13

GATE Overflow Test Series | Mock GATE | Test 5 | Question: 43
Suppose we are given an algorithm $'X'$ that find the median in time $\Theta(n^2)$, where $n$ is the number of inputs. Now consider a QuickSort implementation where we first find median using the above algorithm $'X'$, then use this median as pivot. What ... QuickSort? $\Theta(n^2)$ $\Theta(n \log n)$ $O(n \log n)$ $\Theta(n^2 \log n)$

Suppose we are given an algorithm $’X’$ that find the median in time $\Theta(n^2)$, where $n$ is the number of inputs. Now consider a QuickSort implementation where w...

gatecse

383 views

gatecse asked Feb 8, 2021

1 votes

2 answers

14

NIELIT Scientific Assistant A 2020 November: 83
Which of the following is correct recurrence for worst case of QuickSort? $T(n)=T(n-4)+T(n-2)+O(1)$ $T(n)=T(n-1)+T(0)+O(n)$ $T(n)=2T(n/2)+O(n)$ $T(n)=4T(n/2)+O(n)$

Which of the following is correct recurrence for worst case of QuickSort?$T(n)=T(n-4)+T(n-2)+O(1)$$T(n)=T(n-1)+T(0)+O(n)$$T(n)=2T(n/2)+O(n)$$T(n)=4T(n/2)+O(n)$

gatecse

524 views

gatecse asked Dec 9, 2020

7 votes

2 answers

15

GATE Overflow Test Series | Algorithms | Test 1 | Question: 10
Which of the following is/are the possible array contents after second pass of Quick Sort for the following initial ordering assuming first element is taken as pivot?$34, 8, 64, 51, 32, 21$ $8, 21, 32, 34, 51, 64$ $8, 32, 34, 51, 64, 21$ $8, 34, 51, 64, 32, 21$ $8, 34, 64, 51, 32, 21$

Which of the following is/are the possible array contents after second pass of Quick Sort for the following initial ordering assuming first element is taken as pivot?$$34...

gatecse

324 views

gatecse asked Aug 18, 2020

7 votes

1 answer

16

GATE Overflow Test Series | Algorithms | Test 1 | Question: 17
For quick sort pivot selection you are provided with an buggy implementation of Median select, which can return any element between $(n/3)^{rd}$ smallest and $(2n/3)^{rd}$ smallest in $O(n)$ time. With this function to choose the pivot, which ... it will take $\Theta(n \log n)$ time In best case, it will run in $\Omega(n \log n)$ time

For quick sort pivot selection you are provided with an buggy implementation of Median select, which can return any element between $(n/3)^{rd}$ smallest and $(2n/3)^{rd}...

gatecse

436 views

gatecse asked Aug 18, 2020

2 votes

4 answers

17

NIELIT 2016 DEC Scientist B (CS) - Section B: 12
The running time of Quick sort algorithm depends heavily on the selection of: No. of inputs Arrangement of elements in an array Size of elements Pivot Element

The running time of Quick sort algorithm depends heavily on the selection of:No. of inputsArrangement of elements in an arraySize of elementsPivot Element

admin

15.3k views

admin asked Mar 31, 2020

0 votes

3 answers

18

QUICK SORT- SELF DOUBT
In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n)

In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexit...

ajaysoni1924

3.5k views

ajaysoni1924 asked Sep 2, 2019

1 votes

1 answer

19

Cormen Edition 3 Exercise 7.4 Question 6 (Page No. 185)
Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.

Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elemen...

akash.dinkar12

1.2k views

akash.dinkar12 asked Jun 28, 2019

0 votes

1 answer

20

Cormen Edition 3 Exercise 7.4 Question 5 (Page No. 185)
We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is nearly sorted. Upon calling quicksort on a subarray with fewer than $k$ elements, let it simply return without ... $k$, both in theory and in practice?

We can improve the running time of quicksort in practice by taking advantage of the fast running time of insertion sort when its input is “nearly” sorted. Upon callin...

akash.dinkar12

542 views

akash.dinkar12 asked Jun 28, 2019

0 votes

1 answer

21

Cormen Edition 3 Exercise 7.4 Question 4 (Page No. 184)
Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.

Show that RANDOMIZED-QUICKSORT’s expected running time is $\Omega(n\ lg\ n)$.

akash.dinkar12

521 views

akash.dinkar12 asked Jun 28, 2019

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true