Recent questions tagged sorting - GATE CSE Doubts

0 votes

1 answer

Selection sort
Can anybody explain me why the number of swaps in selection sort algorithm is (n-1) in worst case ? Let's say the array is {6,5,4,3,2,1} then the number of swaps should be 5. But I think the no of swaps should be 3. Please explain.

asked Feb 7 in Algorithms by Akshay0798 (7 points) | 35 views

0 votes

0 answers

Previous Year GATE
The number of elements that can be sorted in Θ(log n) time using heap sort is ___________ .

asked Jan 17 in Algorithms by Rishav Chetan (9 points) | 17 views

+1 vote

1 answer

NIELIT NIC STA 2020 set-C ques 80
Given array is {1,2,4,3}. Bubble sort is used to sort it. How many passes will be done to sort the array? 4 2 1 3 Answer given is 3 but I am getting 2. Need to confirm before challenging the key :)

asked Nov 26, 2020 in Programming by ayush.5 (99 points) | 38 views

+1 vote

1 answer

NIELIT STA 2018
Given an random unsorted array ‘A’ in which every element is at most ‘d’ distance from is position in sorted array where d<Size(A). If we applied the insertion sort over this array, then the time complexity of algorithm is: O($n\log d$) O($n^2\log d$) O($nd$) O($n^2d$)

asked Nov 18, 2020 in Algorithms by Sudarshan Bandyopadh (11 points) | 41 views

0 votes

1 answer

Deletion in heap
How to delete the last node in a max-heap or min-heap? Do we delete it directly or like in normal case- replace it with itself then call max heapify on it and then finally decrease heap size?

asked Oct 11, 2020 in Algorithms by RasMalai (27 points) | 40 views

0 votes

0 answers

Question on heap from MIT quiz
Link: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/exams/quiz1.pdf

asked Oct 10, 2020 in Algorithms by RasMalai (27 points) | 18 views

0 votes

1 answer

UGC NET CS 2015 Jun - II
Which of the following algorithms sort n integers, having the range 0 to (n2 - 1), in ascending order in O(n) time ? A Selection sort B Bubble sort C Radix sort D Insertion sort

asked Sep 24, 2020 in Algorithms by Musa (5 points) | 19 views

0 votes

0 answers

#made-easy-test-series
Assume each item is a 8 digit octal number and the maximum number of comparisons needed to sort 10 items using radix sort is________? according to me answer should be zero bcz radix sort is non comparision base algorithm but they give this explanation The max. no ... number having→ 8 digits The octal number system base value is → 8 So, items*digits*base=10*8*8=640 answer=640

asked Aug 28, 2020 in Algorithms by 404 found (37 points) | 35 views

0 votes

0 answers

Algorithms Concept doubt
Can some one give examples of External Sorting Algorithms ?

asked Aug 17, 2020 in Algorithms by Shivateja MST (45 points) | 40 views

0 votes

2 answers

Geeks for Geeks Topic Test
Which of the following is not true about comparison-based sorting algorithms. The minimum possible time complexity of a comparison-based sorting algorithm is O(N log N) for a random input array. Any comparison-based sorting algorithm can be made stable by using ... . Heap Sort is not a comparison-based sorting algorithm. Choose the correct option. 1,2. 2,4. 4. 2.

asked May 16, 2020 in Algorithms by ramcharantej_24 (13 points) | 148 views

0 votes

0 answers

GATE2014-3-14 Video Solution
You have an array of $n$ elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is $O(n^2)$ $O(n \log n)$ $\Theta(n\log n)$ $O(n^3)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 13 views

0 votes

0 answers

GATE2013-30 Video Solution
The number of elements that can be sorted in $\Theta(\log n)$ time using heap sort is $\Theta(1)$ $\Theta(\sqrt{\log} n)$ $\Theta(\frac{\log n}{\log \log n})$ $\Theta(\log n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 10 views

0 votes

0 answers

GATE2004-29 Video Solution
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of $n$ $n^2$ $n \log n$ $n \log^2n$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 9 views

0 votes

0 answers

GATE2012-39 Video Solution
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $

asked Apr 18, 2020 in Algorithms by admin (573 points) | 12 views

0 votes

0 answers

GATE2005-39 Video Solution
Suppose there are $\lceil \log n \rceil$ sorted lists of $\lfloor n /\log n \rfloor$ elements each. The time complexity of producing a sorted list of all these elements is: (Hint:Use a heap data structure) $O(n \log \log n)$ $\Theta(n \log n)$ $\Omega(n \log n)$ $\Omega\left(n^{3/2}\right)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE1999-1.14, ISRO2015-42 Video Solution
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order: $20, \ 47, \ 15, \ 8, \ 9, \ 4, \ 40, \ 30, \ 12, \ 17$ ... $4, \ 8, \ 9, \ 15, \ 20, \ 47, \ 12, \ 17, \ 30, \ 40$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2014-2-38 Video Solution
Suppose $P, Q, R, S, T$ are sorted sequences having lengths $20, 24, 30, 35, 50$ respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2006-52 Video Solution
The median of $n$ elements can be found in $O(n)$ time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot? $\Theta (n)$ $\Theta (n \log n)$ $\Theta (n^{2})$ $\Theta (n^{3})$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2006-14, ISRO2011-14 Video Solution
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2014-1-14 Video Solution
Let $P$ be quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ be the number of comparisons made by P for the inputs $[1 \ 2 \ 3 \ 4 \ 5]$ and $[4 \ 1 \ 5 \ 3 \ 2]$ respectively. Which one of the following holds? $t_1 = 5$ $t_1 < t_2$ $t_1>t_2$ $t_1 = t_2$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2003-62 Video Solution
In a permutation \(a_1 ... a_n\), of $n$ distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of \(1. ... at most $n$ inversions? \(\Theta(n^2)\) \(\Theta(n\log n)\) \(\Theta(n^{1.5})\) \(\Theta(n)\)

asked Apr 18, 2020 in Algorithms by admin (573 points) | 9 views

0 votes

0 answers

GATE2003-61 Video Solution
In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)? \(\frac{n(n-1)}{2}\) \(\frac{n(n-1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE1995-1.16 Video Solution
For merging two sorted lists of sizes $m$ and $n$ into a sorted list of size $m+n$, we require comparisons of $O(m)$ $O(n)$ $O(m+n)$ $O(\log m + \log n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2009-39 Video Solution
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)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 6 views

0 votes

0 answers

GATE2015-3-27 Video Solution
Assume that a mergesort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size of a problem that can be solved in $6$ minutes? $256$ $512$ $1024$ $2018$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2003-22 Video Solution
The unusual $\Theta(n^2)$ implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running ... $\Theta(n^2)$ become $\Theta(n (\log n)^2)$ become $\Theta(n \log n)$ become $\Theta(n)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 9 views

0 votes

0 answers

GATE2015-2-45 Video Solution
Suppose you are provided with the following function declaration in the C programming language. int partition(int a[], int n); The function treats the first element of $a[\:]$ as a pivot and rearranges the array so that all elements less than or equal to the pivot is in the left ... and $(a, $ left_end$, k)$ $(a, n-$left_end$-1, k-$left_end$-1)$ and $(a, $left_end$, k)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE1994-1.19, ISRO2016-31 Video Solution
Algorithm design technique used in quicksort algorithm is? Dynamic programming Backtracking Divide and conquer Greedy method

asked Apr 18, 2020 in Algorithms by admin (573 points) | 6 views

0 votes

0 answers

GATE2001-1.14 Video Solution
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using Randomized quicksort? $O(n)$ $O(n \log n)$ $O(n^2)$ $O(n!)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2008-IT-43 Video Solution
If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be? $\Theta(n)$ $\Theta(kn)$ $\Theta(n \log n)$ $\Theta(n^2)$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 12 views

0 votes

0 answers

GATE2016-2-13 Video Solution
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 in ... time Insertion sort runs in $\Theta (n)$ time I and II only I and III only II and IV only I and IV only

asked Apr 18, 2020 in Algorithms by admin (573 points) | 8 views

0 votes

0 answers

GATE2008-43 Video Solution
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then $T(n) \leq 2T(n/5) + n$ $T(n) \leq T(n/5) + T(4n/5) + n$ $T(n) \leq 2T(4n/5) + n$ $T(n) \leq 2T(n/2) + n$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE1987-1-xviii Video Solution
Let $P$ be a quicksort program to sort numbers in ascending order. Let $t_{1}$ and $t_{2}$ be the time taken by the program for the inputs $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$, respectively. Which of the following holds? $t_{1} = t_{2}$ $t_{1} > t_{2}$ $t_{1} < t_{2}$ $t_{1}=t_{2}+5 \log 5$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 11 views

0 votes

0 answers

GATE1999-1.12 Video Solution
A sorting technique is called stable if it takes $O (n \log n)$ time it maintains the relative order of occurrence of non-distinct elements it uses divide and conquer paradigm it takes $O(n)$ space

asked Apr 18, 2020 in Algorithms by admin (573 points) | 10 views

0 votes

0 answers

GATE1991-01,vii Video Solution
The minimum number of comparisons required to sort $5$ elements is ____

asked Apr 18, 2020 in Algorithms by admin (573 points) | 5 views

0 votes

0 answers

GATE1996-2.15 Video Solution
Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot $1, 2, 3, \dots n$ $n, n-1, n-2, \dots, 2, 1$ Let $C_1$ and $C_2$ be the number of comparisons made for the inputs (i) and (ii) respectively. Then, $C_1 < C_2$ $C_1 > C_2$ $C_1 = C_2$ we cannot say anything for arbitrary $n$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2005-IT-59 Video Solution
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 ... Which of the following is TRUE? only I and II only I and IV only II and III only III and IV

asked Apr 18, 2020 in Algorithms by admin (573 points) | 54 views

0 votes

0 answers

GATE1992-02,ix Video Solution
Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Following algorithm(s) can be used to sort $n$ in the range $[1\ldots n^3]$ in $O(n)$ time Heap sort Quick sort Merge sort Radix sort

asked Apr 18, 2020 in Algorithms by admin (573 points) | 7 views

0 votes

0 answers

GATE2000-17 Video Solution
An array contains four occurrences of $0$, five occurrences of $1$, and three occurrences of $2$ in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent). What is the minimum number of swaps ... case? Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

asked Apr 18, 2020 in Algorithms by admin (573 points) | 32 views

0 votes

0 answers

GATE2015-1-2 Video Solution
Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n$ ( $\geq $ 2) numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n - 1) + T(1) + cn$ $T(n) = 2T ( n - 1) + cn$ $T(n) = T (n/2) + cn$

asked Apr 18, 2020 in Algorithms by admin (573 points) | 5 views

Page:

9,095 questions

3,154 answers

14,583 comments

95,939 users