Recent questions tagged sorting / GATE Overflow for GATE CSE

0 votes

1 answer

331

Test by Bikram | Mock GATE | Test 3 | Question: 14
We write a new algorithm by considering the fact that number of comparisons required by Selection Sort can be reduced by considering elements in pairs and finding the minimum and maximum element at the same time. What will be the time complexity of the new algorithm for comparisons of Selection Sort? $O/2$ $O(n)/4$ $O(n)$ $O$(\log n)$

We write a new algorithm by considering the fact that number of comparisons required by Selection Sort can be reduced by considering elements in pairs and finding the min...

Bikram

637 views

Bikram asked Feb 9, 2017

0 votes

1 answer

332

worst case in quck sort
Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of set of 3 elements [First element, middle element, and last element]. What will be worst case time complexity ... (n2) Ο(n logn) Ο(n2 logn) Ο(n log log n) I think it will be B but they have given as A....???

Consider a scenario of modified quick sort, where we have given an input sorted array A[1 . . . n], all elements of array are distinct and n ≥ 3. Pivot is the median of...

iita

1.9k views

iita asked Feb 7, 2017

0 votes

2 answers

333

Programming and ds
Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general? A Heap Sort B Selection Sort C Insertion Sort D Merge Sort the answer turned out to be B but D should the answer because it does not have any swap operatoin.?

Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimize...

deepak_yadav

2.7k views

deepak_yadav asked Feb 6, 2017

0 votes

1 answer

334

Design and Analysis of Algorithm
Q.Suppose our aim is to sort an array in ascending order. Which of the following statements is true? 1.Input in ascending order is worst case for both selection sort and insertion sort. 2. Input in descending order is worst case for both ... sort but not for selection sort. 4.Input in descending order is worst case for selection sort but not for insertion sort.

Q.Suppose our aim is to sort an array in ascending order. Which of the following statements is true? 1.Input in ascending order is worst case for both selection sort and ...

Edwees

4.8k views

Edwees asked Feb 6, 2017

0 votes

1 answer

335

Design and Analysis of Algorithm
We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks in a ... ,60),("Tariq",71),("Shweta",71),("Salma",72),("Sunita",85),("Brinda",85)]

We have a list of pairs [("Tariq",71),("Brinda",85),("Shweta",71),("Sunita",85),("Salma",72),("Uday",60)], where each pair consists of a student's name and his/her marks ...

Edwees

1.9k views

Edwees asked Feb 6, 2017

0 votes

2 answers

336

Design and Analysis of Algorithm
Which of the following statements is not true? 1.For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n2). 2.If we randomly choose a pivot element each time, quicksort will ... would have worst case complexity O(n log n). 4.Quicksort and merge sort are both examples of divide and conquer algorithms.

Which of the following statements is not true? 1.For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n2). 2...

Edwees

6.2k views

Edwees asked Feb 6, 2017

2 votes

1 answer

337

Test series
Minimum time taken to find median of a list of numbers is O(log n) O(n) O(n log n) O (n2)

Minimum time taken to find median of a list of numbers isO(log n)O(n)O(n log n)O (n2)

Sanju Rakonde

397 views

Sanju Rakonde asked Feb 6, 2017

1 votes

1 answer

338

Space complexity
Which of the following algorithm have the smallest memory requirement i.e Low space complexity including data space and run time stack for recursive calls. A)insertion sort B)quick sort C)merge sort D)selection sort

Which of the following algorithm have the smallest memory requirement i.e Low space complexity including data space and run time stack for recursive calls.A)insertion sor...

reena_kandari

1.8k views

reena_kandari asked Feb 5, 2017

0 votes

1 answer

339

Non duplicate element
There is a sorted array which is of very large size. In those elements every element are repeated more than once except one element. How much time it will take to find that element? O(1) O(n) O(nlogn) O(logn) I think its less than O(log n) (divide n conquer) but solution is O(n)

There is a sorted array which is of very large size. In those elements every element are repeated more than once except one element. How much time it will take to find th...

Pankaj Joshi

314 views

Pankaj Joshi asked Feb 4, 2017

0 votes

1 answer

340

#algorithms #best #algo
Best algorithm for this set: 1.Independently sorting each of 1,000,000 arrays, each with 5 elements. 2.Sorting a set of 4,000,000 numbers in worst case O(n lg n) time.

Best algorithm for this set:1.Independently sorting each of 1,000,000 arrays, each with 5 elements.2.Sorting a set of 4,000,000 numbers in worst case O(n lg n) time.

Smriti012

701 views

Smriti012 asked Feb 3, 2017

0 votes

2 answers

341

MadeEasy Subject Test: Algorithms - Sorting
a. i>0,K>0, a[K]> a[max] b. i>0,K<0, a[K]< a[max] c. i<0,K>0, a[K]> a[max] d. i>0,K>0, a[K]< a[max]

a. i>0,K>0, a[K] a[max]b. i>0,K<0, a[K]< a[max]c. i<0,K>0, a[K] a[max]d. i>0,K>0, a[K]< a[max]

naveen81

729 views

naveen81 asked Jan 30, 2017

0 votes

1 answer

342

Ace Test Series: Algorithms - Sorting

Sonali Rangwani

727 views

Sonali Rangwani asked Jan 30, 2017

0 votes

1 answer

343

ace mock 6
which of the following methods will be the best if number of swappings done, is the only measure of efficiency? A) Bubble sort B) Selection sort C) Insertion sort D) Quick sort

which of the following methods will be the best if number of swappings done, is the only measure of efficiency?A) Bubble sort B) Selection sortC) Insertion so...

iita

693 views

iita asked Jan 30, 2017

6 votes

1 answer

344

Sorting Techniques
What is the best sorting algorithm to use for the elements in array are more than 1 million in general? A Merge sort. B Bubble sort. C Quick sort. D Insertion sort. Ans:C Source: http://quiz.geeksforgeeks.org/algorithms-insertionsort-question ... B Source: http://quiz.geeksforgeeks.org/algorithms-searching-and-sorting-question-16/ Kindly explain on why the answers are different?

What is the best sorting algorithm to use for the elements in array are more than 1 million in general?AMerge sort.BBubble sort.CQuick sort.DInsertion sort. Ans:CSource: ...

Orochimaru

7.9k views

Orochimaru asked Jan 27, 2017

2 votes

3 answers

345

Insertion sort
Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the insertion sort when element 1 reaches the first position of the array ? (A) 50 (B) 25 (C) 75 (D) 100 Source: http://quiz.geeksforgeeks.org/algorithms-insertionsort-question-4/

Consider the array A[]= {6,4,8,1,3} apply the insertion sort to sort the array . Consider the cost associated with each sort is 25 rupees , what is the total cost of the ...

Orochimaru

10.9k views

Orochimaru asked Jan 27, 2017

1 votes

1 answer

346

Test by Bikram | Mock GATE | Test 2 | Question: 25
Which of the following sorting algorithms has the lowest best-case asymptotic algorithmic complexity? Selection sort Merge sort Insertion sort Heap sort

Which of the following sorting algorithms has the lowest best-case asymptotic algorithmic complexity?Selection sortMerge sortInsertion sortHeap sort

Bikram

273 views

Bikram asked Jan 24, 2017

6 votes

2 answers

347

Test by Bikram | Mock GATE | Test 2 | Question: 17
A Multinational software vendor needs to choose two sorting algorithm implementations $S1$ and $S2$ to built a software for it's offshore clients. $S1$ will be used in situations where item exchanges cost nothing but item comparisons remain ... for $S1$ and insertion sort for $S2$. Insertion sort for $S1$ and selection sort for $S2$.

A Multinational software vendor needs to choose two sorting algorithm implementations $S1$ and $S2$ to built a software for it's offshore clients.$S1$ will be used in sit...

Bikram

806 views

Bikram asked Jan 24, 2017

1 votes

2 answers

348

Test by Bikram | Mock GATE | Test 2 | Question: 12
Why might quick sort be preferred over insertion sort and merge sort? The worst-case asymptotic algorithmic complexity of quick sort is superior to that of insertion sort and merge sort. In situations where little temporary space is available, ... on a long tape, the average run time of quick sort is superior to that of insertion and merge sort.

Why might quick sort be preferred over insertion sort and merge sort?The worst-case asymptotic algorithmic complexity of quick sort is superior to that of insertion sort ...

Bikram

603 views

Bikram asked Jan 24, 2017

2 votes

2 answers

349

time required to fins the unknowm integer
as we already know the range,so can we use counting sort??and complexity of counting sort is O(n+k) what other method is there to know the missing number??

as we already know the range,so can we use counting sort??and complexity of counting sort is O(n+k)what other method is there to know the missing number??

Akriti sood

929 views

Akriti sood asked Jan 22, 2017

0 votes

2 answers

350

Complexity
Consider X[1, ..., n] and Y[1, ..., n] be two arrays each containing n-numbers both of which are already sorted. What is the time complexity to find median by combining the two arrays? O(log n) O(n) O(n log n) O(log log n)

Consider X[1, ..., n] and Y[1, ..., n] be two arrays each containing n-numbers both of which are already sorted. What is the time complexity to find median by combining t...

kamboj

1.7k views

kamboj asked Jan 22, 2017

2 votes

1 answer

351

quick sort
If we use quicksort algorithm to sort the elements: $16, 13, 14, 12, 21, 16, 23$ and $15$ in ascending order, what is the output after the first pass of quicksort? (Assume pivot element is beginning of an array)

If we use quicksort algorithm to sort the elements: $16, 13, 14, 12, 21, 16, 23$ and $15$ in ascending order, what is the output after the first pass of quicksort? (Assum...

dd

2.2k views

dd asked Jan 20, 2017

2 votes

1 answer

352

WHICH SORTING TO SELECT?
As part of maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be— (a) Bubble sort (b) Insertion sort (c) Selection sort (d) Heap sort

As part of maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be...

deepak mahapatra

16.9k views

deepak mahapatra asked Jan 19, 2017

0 votes

1 answer

353

efficient algo for nearly sorted array

Sanjay Sharma

777 views

Sanjay Sharma asked Jan 19, 2017

2 votes

1 answer

354

Test by Bikram | Mock GATE | Test 1 | Question: 38
A radix sort is to be used to sort the file of non-negative integers shown below into ascending order. What would the order of the numbers be after one pass of the algorithm? $12$ $37$ $42$ $9$ $5$ $7$ $50$ $40$ $45$ $92$ $12$ $37$ $42$ $40$ $45$ $5$ $50$ $7$ ... $12$ $42$ $92$ $5$ $45$ $37$ $7$ $9$ $40$ $50$ $12$ $42$ $92$ $5$ $45$ $7$ $37$ $9$

A radix sort is to be used to sort the file of non-negative integers shown below into ascending order. What would the order of the numbers be after one pass of the algori...

Bikram

522 views

Bikram asked Jan 16, 2017

0 votes

4 answers

355

merge sort

harshit agarwal

1.2k views

harshit agarwal asked Jan 15, 2017

2 votes

1 answer

356

Can anyone make the table of Complexities, No. of swaps required for N elements for all type of sorts?

If possible,. all 3 cases (best,average, worst)

smartmeet

563 views

smartmeet asked Jan 13, 2017

0 votes

1 answer

357

General doubt on calculating the Time complexity for the given Insertion Sort Algorithm in the worst and average case

INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...

LavTheRawkstar

835 views

LavTheRawkstar asked Jan 12, 2017

0 votes

2 answers

358

Sorting

reena_kandari

541 views

reena_kandari asked Jan 10, 2017

0 votes

1 answer

359

Recursive call count for merge sort

Anirban Biswas

1.5k views

Anirban Biswas asked Jan 10, 2017

0 votes

1 answer

360

Algo doubt

Arnabi

360 views

Arnabi asked Jan 7, 2017

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