Answer to Question #265543 in C++ for Usama

Question

Write a program that creates three identical arrays, list1, list2, and list3 of 5000 elements. The program then sorts list1 using bubble sort, list2 using selection sort, and list3 using insertion sort and outputs the number of comparisons and item assignments made by each sorting algorithm.

Answer 1

void selectionSort(int *list1, int size) {
   int i, j, mn;
   for(i = 0; i<size-1; i++) {
      mn = i;   
      for(j = i+1; j<size; j++)
         if(list1[j] < list1[mn])
            mn = j;
         swap(list1[i], list1[mn]);
   }
}


void insertionSort(int *list2, int size) {
   int foo, j;
   for(int i = 1; i<size; i++) {
      foo = list2[i];
      j = i;
      while(j > 0 && list2[j-1]>foo) {
         list2[j] = list2[j-1];
         j--;
      }
      list2[j] = foo;   
   }
}


void bubbleSort(int *list3, int size) {
   for(int i = 0; i<size; i++) {
      int swaps = 0;
      for(int j = 0; j<size-i-1; j++) {
         if(list3[j] > list3[j+1]) {       
            swap(list3[j], list3[j+1]);
            swaps = 1;
         }
      }
      if(!swaps)
         break;   
   }
}