Question

Imagine that you have been assigned to implement a sorting program. The goal is to make this program general purpose, in that you don't want to define in advance what record or key types are used. Describe ways to generalize a simple sorting algorithm (such as insertion sort, or any other sort you are familiar with) to support this generalization.

Data Structures and Algorithm Analysis in C++ by Clifford Shaffer

Answer 1

Sorting would help to reorder the list of objects. There are different types of sortings listed ;Bubble sorting, Inserting sorting, and selection sorting methods..there are different types of sorting..internal sorting as well as external sorting.

For example we can take insertion sorting as a method, we can select the objects which are not into order and make them in order. When we sort the most difficult method is to compare the two elements the dominant factor in the run time of the application.

Like we can take 0 camparisions to insert the first element;

1 comparision to insert the second element

2 comparions to insert the third element

To sort unordered list of elements, we remove its entries one at a time and then insert them into sorted part

void insertionSort(int[] ar)

{
   for (int a=1; a ‹ ar.length; i++)
   {
      int index = ar[a]; int j = i;
      while (j > 0 && ar[j-1] > index)
      {
           ar[j] = ar[j-1];
           j--;
      }
      ar[j] = index;
} }

for the above mentioned we take into consideration the unordered list of numbers and list them in order.