TANCET 2011 SORTING

Question

An array has 5 elements. Calculate the following:

SL. NO:	NAME	ARRAY IS ALREADY SORTED		ARRAY IS REVERSE SORTED
		ELEMENT COMPARSIONS	ELEMENT EXCHANGES	ELEMENT COMPARISONS	ELEMENT EXCHANGES
1	BUBBLE SORT	?	?	?	?
2	SELECTION SORT	?	?	?	?
3	INSERTION SORT	?	?	?	?
4	QUICK SORT	?	?	?	?
5	MERGE SORT	?	?	?	?
6	RADIX SORT	?	?	?	?
7	HEAP SORT	?	?	?	?
8	TREE SORT	?	?	?	?
9	COUNTING SORT	?	?	?	?

 

Comments

Number of Comparisons and Number of Exchanges

---

upto where you solved?

---

Assuming this is the code for selection sort:

for(i=0;i<n-1;i++){
    smallest=a[i];
    for(j=i+1;j<n;j++){
        if(smallest>a[j])
            smallest=a[j];
    }
    if(smallest!=a[i])
        a[i]=smallest;
}

SL. NO:	NAME	ARRAY IS ALREADY SORTED		ARRAY IS REVERSE SORTED
		ELEMENT COMPARSIONS	ELEMENT EXCHANGES	ELEMENT COMPARISONS	ELEMENT EXCHANGES
1	BUBBLE SORT	4	0	4+3+2+1 = 10	4+3+2+1 = 10
2	SELECTION SORT	(4+1) + (3+1) + (2+1) = 12	0	(4+1) + (3+1) + (2+1) = 12	4
3	INSERTION SORT	4	0	?	?
4	QUICK SORT	?	?	?	?
5	MERGE SORT	6	0	6	0
6	RADIX SORT (assuming all elements are consecutive)	0	0	0	0
7	HEAP SORT	?	?	?	?
8	TREE SORT	?	?	?	?
9	COUNTING SORT	0	0	0	0