Register

GATE CSE 1999 | Question: 1.12

• edited by
9,304 views
26 votes
26 votes

A sorting technique is called stable if

  1. it takes $O (n \log n)$ time

  2. it maintains the relative order of occurrence of non-distinct elements

  3. it uses divide and conquer paradigm

  4. it takes $O(n)$ space

• edited by
User Avatar

2 Answers

Best answer
30 votes
30 votes

Correct Option: B

If it maintains the relative order of occurrence of non-distinct elements.

(from definition of stable sorting)

• edited by
User Avatar
17 votes
17 votes

Answer (B)

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.

Ref: https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

31 votes
31 votes
3 answers
1
Kathleen asked Sep 23, 2014
5,156 views
GATE CSE 1999 | Question: 8
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $3$rd smallest elements in minimum number of comparisons.
Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $...
User Avatar
25 votes
25 votes
1 answer
2
Kathleen asked Sep 23, 2014
4,068 views
GATE CSE 1999 | Question: 1.24
Let $R = (A, B, C, D, E, F)$ be a relation scheme with the following dependencies $C \rightarrow F, E \rightarrow A, EC \rightarrow D, A \rightarrow B $. Which one of the following is a key for $R$? CD EC AE AC
Let $R = (A, B, C, D, E, F)$ be a relation scheme with the following dependencies $C \rightarrow F, E \rightarrow A, EC \rightarrow D, A \rightarrow B $. Which one of the...
User Avatar
38 votes
38 votes
1 answer
3
Kathleen asked Sep 23, 2014
16,909 views
GATE CSE 1999 | Question: 1.18, ISRO2016-53
Consider the join of a relation $R$ with a relation $S$. If $R$ has $m$ tuples and $S$ has $n$ tuples then the maximum and minimum sizes of the join respectively are $m+n$ and $0$ $mn$ and $0$ $m+n$ and $|m-n|$ $mn$ and $m+n$
Consider the join of a relation $R$ with a relation $S$. If $R$ has $m$ tuples and $S$ has $n$ tuples then the maximum and minimum sizes of the join respectively are$m+n$...
User Avatar
21 votes
21 votes
6 answers
4
Kathleen asked Sep 23, 2014
23,207 views
GATE CSE 1999 | Question: 1.17
Which of the following is the most powerful parsing method? LL (1) Canonical LR SLR LALR
Which of the following is the most powerful parsing method?LL (1)Canonical LRSLRLALR
User Avatar
Link Copied!