Search results for sorting / GATE Overflow for GATE CSE

48 votes

5 answers

21

GATE CSE 2009 | Question: 39
In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort? $\Theta(n)$ $\Theta(n \log n)$ $\Theta(n^2)$ $\Theta(n^2 \log n)$

In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time com...

Kathleen

21.3k views

Kathleen asked Sep 22, 2014

8 votes

1 answer

22

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 49
An inversion in an array $a$ is a pair of array indices $(i, j)$ such that $i<j$ but $a[i]>a[j]$. What is the maximum number of inversions that can be eliminated by the following program fragment? tmp = a[5] ; a[5] = a[10] ; a[10]= tmp ; $5$ $6$ $9$ $20$

An inversion in an array $a$ is a pair of array indices $(i, j)$ such that $i<j$ but $a[i]>a[j]$.What is the maximum number of inversions that can be eliminated by the fo...

GO Classes

582 views

GO Classes asked Jan 13

0 votes

1 answer

23

Sorting Algorithm
For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends in Best case = O(n). Why isn't the same concept applicable to selection sort? Why it never comes down from O(n$^2$)?

For flag based approach in Bubble sort we can check first by a flag if the list is sorted or not in O(n), and if it is sorted, then no need to sort and the operation ends...

Mrityudoot

192 views

Mrityudoot asked Mar 7

2 votes

2 answers

24

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 20
Consider the following array$: [32, 33, 5, 2, 14, -4, 22, 39, 34, -9].$ ... sorting algorithms could we possibly have applied? Merge sort (top-down approach) Bubble sort Quicksort (Using First element as pivot) Insertion sort

Consider the following array$: [32, 33, 5, 2, 14, -4, 22, 39, 34, -9].$ We apply a certain sorting algorithm and observe that the array has been modified to $[2, 5, 14, 3...

GO Classes

576 views

GO Classes asked Feb 5

5 votes

2 answers

25

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

657 views

GO Classes asked Jan 21

1 votes

2 answers

26

GATE CSE 2024 | Set 2 | Question: 25
Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2,5,3,1,4,2,6]$ is ___________.

Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{A}$ that must be replaced with ano...

Arjun

2.3k views

Arjun asked Feb 16

3 votes

0 answers

27

GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 47
A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points $[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].$ We sort these in ascending order by the ... $[(9, 0, 9),(6, 1, 4),(7, 1, 8),(0, 2, 5),(3, 5, 7),(6, 5, 9)]$

A $\text{stable sort}$ preserves the order of values that are equal with respect to the comparison function. We have a list of three-dimensional points$[(7, 1, 8),(3, 5, ...

GO Classes

214 views

GO Classes asked Feb 5

3 votes

1 answer

28

GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 24
Here is an array of ten integers$: 5389170264$ Suppose we run MergeSort on this array. What is the number in the $7$th position of the partially sorted array after the outermost two recursive calls have completed (i.e., just before the very last Merge ... for example, the input array has a $0$ in its $7$th position.) $3$ $1$ $2$ $4$

Here is an array of ten integers$: 5389170264$Suppose we run MergeSort on this array. What is the number in the $7$th position of the partially sorted array after the out...

GO Classes

371 views

GO Classes asked Jan 13

0 votes

1 answer

29

GATE DS&AI 2024 | Question: 35
Consider the following sorting algorithms: Bubble sort Insertion sort Selection sort Which ONE among the following choices of sorting algorithms sorts the numbers in the array $[4,3,2,1,5]$ in increasing order after exactly two passes over the array? $\text{(i)}$ only $\text{(iii)}$ only $\text{(i)}$ and $\text{(iii)}$ only $\text{(ii)}$ and $\text{(iii)}$ only

Consider the following sorting algorithms:Bubble sortInsertion sortSelection sortWhich ONE among the following choices of sorting algorithms sorts the numbers in the arra...

Arjun

862 views

Arjun asked Feb 16

0 votes

0 answers

30

GATE 2024
Consider an n element array which is to be sorted either in ascending or descending order. The given restriction is only one pass will be used for completely sorting the array and an element can compare with only it's adjacent pair. What will be the worst time complexity? Is this related to bubble sort algorithm or not?

Consider an n element array which is to be sorted either in ascending or descending order. The given restriction is only one pass will be used for completely sorting the ...

TusharRana

390 views

TusharRana asked Feb 11

0 votes

0 answers

31

Memory Based GATE DA 2024 | Question: 22
Given the array $ [4, 3, 2, 1, 5] $, which of the following sorting algorithms can successfully sort the array in exactly two passes? Bubble Sort Insertion Sort Selection Sort Merge Sort

Given the array $ [4, 3, 2, 1, 5] $, which of the following sorting algorithms can successfully sort the array in exactly two passes?Bubble SortInsertion Sort Selectio...

GO Classes

159 views

GO Classes asked Feb 4

0 votes

1 answer

32

ISRO 2024
Worst case time complexity of heap sort for n elements O(nlogn) O(logn) O^2 O(n)

Worst case time complexity of heap sort for n elementsO(nlogn)O(logn)O^2O(n)

Ramayya

192 views

Ramayya asked Jan 7

1 votes

1 answer

33

UGC NET CSE | June 2008 | Part 2 | Question: 23
Which of the following is true for a sorted list with ' $n$ ... $\mathrm{O}(\log n)$ time.

Which of the following is true for a sorted list with ' $n$ ' elements?Insertion in a sorted array takes constant time.Insertion in a sorted linear linked list takes cons...

admin

142 views

admin asked Jan 6

56 votes

5 answers

34

GATE IT 2005 | Question: 59
Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in non-decreasing order. Let $c$ be a sorted array containing $2n$ integers obtained by merging the two arrays $a$ and $b$. Assuming the arrays are indexed starting from $0$, consider the following ... Which of the following is TRUE? only I and II only I and IV only II and III only III and IV

Let $a$ and $b$ be two sorted arrays containing $n$ integers each, in non-decreasing order. Let $c$ be a sorted array containing $2n$ integers obtained by merging the two...

Ishrat Jahan

11.8k views

Ishrat Jahan asked Nov 3, 2014

0 votes

2 answers

35

Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?

Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...

dhruba

1.2k views

dhruba asked Jun 5, 2023

1 votes

2 answers

36

geeksforgeeks
In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort? A N(logN base 3) B N(logN base 2/3) C N(logN base 1/3) D N(logN base 3/2)

In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?AN(...

Bhavana Giri 10

7.0k views

Bhavana Giri 10 asked Jun 14, 2017

1 votes

1 answer

37

Self doubt
#include <stdio.h> void SSort(int [], int); void swap(int *,int*); int main() { int arr[] = {5,4,3,2,1,0}; int n = sizeof(arr)/sizeof(arr[0]); SSort(arr,n); for(int i = 0; i < n; i++) { printf("%d\t", arr[i]); } return 0; } void SSort( ... = *x; *x = *y; *y = tmp; } This is a selection sort algorithm. But the output of the algo is: 0 0 0 0 0 0. Where is the problem ?

#include <stdio.h>void SSort(int [], int);void swap(int *,int*);int main() { int arr[] = {5,4,3,2,1,0}; int n = sizeof(arr)/sizeof(arr[0]); SSort(arr,n); for(...

Gopal6854

336 views

Gopal6854 asked Sep 13, 2023

0 votes

1 answer

38

Combinatorics, Discrete Maths (self doubts)
Consider the set of 4 -digit positive integers. How many of them have their digits in :- a) strictly decreasing order ? b) non decreasing order ? c) non increasing order ?

Consider the set of 4 -digit positive integers. How many of them have their digits in :-a) strictly decreasing order ?b) non decreasing order ?c) non increasing order ?...

Swarnava Bose

401 views

Swarnava Bose asked Jun 3, 2023

5 votes

5 answers

39

ISRO2020-33
If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort? $67,12,10,5,4,7,23$ $4,7,10,23,67,12,5$ $4,5,7,67,10,12,23$ $10,7,4,67,23,12,5$

If an array $A$ contains the items $10,4,7,23,67,12$ and $5$ in that order, what will be the resultant array $A$ after third pass of insertion sort?$67,12,10,5,4,7,23$$4,...

Satbir

7.8k views

Satbir asked Jan 13, 2020

43 votes

4 answers

40

GATE CSE 2016 Set 2 | Question: 13
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE? Quicksort runs in $\Theta (n^2)$ time Bubblesort runs in $\Theta (n^2)$ time Mergesort runs ... Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in the ascending order, which of the following are TRUE?Qu...

Akash Kanase

14.4k views

Akash Kanase asked Feb 12, 2016

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