Question

You want to implement Radix Sort to sort a large set of random numbers using an auxiliary sorting algorithm for the digits and you want your algorithm to be fast. Which auxiliary sorting algorithms would you use?

1. Heap Sort

2. Merge Sort

3. Insertion Sort

4. Selection Sort

5. Basic Quick Sort

Answer 1

1) ::-- Heap sort :--

MAX‐HEAPIFY(A, i)
1. l ← LEFT(i)
2. r ← RIGHT(i)
3. if l ≤ heap‐size[A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ heap‐size[A] and a[r] > A[largest]
7. then largest ← r
8. if largest ≠ i
9. then exchange A[i] A[largest]
10. MAX‐HEAPIFY (A, largest)

2)) :::-- Merge sort :--

procedure mergesort( var a as array )
if ( n == 1 ) return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]
l1 = mergesort( l1 )
l2 = mergesort( l2 )
return merge( l1, l2 )
end procedure
procedure merge( var a as array, var b as array )
var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while
return c
end procedure

3)) ::-- Insertion sort:--

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
        
   for i = 1 to length(A) inclusive do:
        
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      
      /*locate hole position for the element to be inserted */
                
      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
                
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
      
   end for
        
end procedure

4) :--- Selection sort:---

procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if

end for
/* swap the minimum element with the current element*/
if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure

5)) ::-- Quick sort :--

Algorithm I:
int partition(int A[ ], int left, int right);
// sort A[left..right]
void quicksort(intA[ ], int left, int right
)
int q
;
if (right > left )
{
q = partition(A, left, right);
// after ‘partition’
//
Æ A[left..q-1] ≤ A[q] ≤ A[q+1..right]
quicksort(A, left, q-1);
quicksort(A, q+1, right);
}
}

// select A[left] be the pivot element)
int partition(int A[], int left, int right);
{ P = A[left]
;
i = left;
j = right + 1;
for(;;) //infinite for-loop, break to exit
{ while
(
A[++i] < P) if (i >= right) break;
// Now, A[i] ≥P
while
(
A[--j] > P) if (j <= left) break
;
// Now, A[j] ≤P
if (i >= j ) break; // break the for-loop
else swap
(
A[i],
A[j]);
}
if (j == left) return j
;
swap
(
A[left],
A[j]);
return
j;
}