CS3343/3341
 Analysis of Algorithms 
Spring 2012
  Recursive Selection Sort  
ANSWERS

Question 6 in Recitation 2: Recursive Selection Sort

[Below is are programs answering the questions. The Java program on the left is a direct and straightforward answer. The C program on the right does all the same things, but differs from the requirements in various minor ways. Notice that the program on the right took almost exactly 100 times as long to sort 10 times as many number, just as we would expect from a Θ(n2) algorithm.] The programs below create an array A of 15 random doubles. They use a recursive function max to find the largest element in this array.

For this question, you are asked to write a recursive selection sort function by making additions and changes to either the Java or the C progam below (or both) in the following steps:

  1. Replace the recursive function max with a new recursive function maxInd (in Java, or maxind in C) that will return the integer index of the largest element in the array. (For the new task, we no longer care what the value of the largest element is.)

  2. Test the function maxInd with a separate run.

  3. Add a function selectionSort (in Java, or selectionsort in C) that will sort the array into order. Keep in mind that an array of length 1 is already sorted. (In Java, you may want to rename your class, from Findmax to, say, SelectionSort.)

    1. This function should first find the index of the largest element of A from 0 to n-1, inclusive, (that is, 0 <= i < n).

    2. Exchange the element found in the previous step with the (n-1)st element, using a separate function exchange.

    3. Use the same selection sort function recursively to sort the portion of A from 0 to n-2, inclusive.

    4. Test the final program by sorting an array of 15 random numbers.

    5. Be sure to include the source code and the results of the run above in your submission for Recitation 2.

Recursive Selection Sort
JavaC
public class SelectionSort {
   final static int N = 15;

   public static void main(String[] args) {
      double[] A = new double[N]; // random numbers
      init(A, N); // rand #s for A[0], ..., A[N-1]
      printit(A, N); // print them
      System.out.println("Sorted:");
      selectionSort(A, N);
      printit(A, N); // print them
   }

   static int maxind(double[] A, int n) {
      int maxi;
      if (n == 1) return 0;
      maxi = maxind(A, n-1);
      if (A[n-1] > A[maxi]) return n-1;
      return maxi;
   }

   static void init(double[] A, int n) {
      int i;
      for (i = 0; i < n; i++)
         // 0 < A[i] < 1, uniformly distributed
         A[i] = Math.random();
   }

   static void interchange(double[] A, int i, int j) {
      double temp = A[i];
      A[i] = A[j];
      A[j] = temp;
   }

   static void selectionSort(double[] A, int n) {
      if (n > 1) {
         int maxi = maxind(A, n);
         interchange(A, maxi, n-1);
         selectionSort(A, n-1);
      }
   }
         
   static void printit(double[] A, int n) {
      for (int i = 0; i < n; i++)
         System.out.println("A[" + i + "]: " + A[i]);
   }
}

A[0]: 0.4534815873855662
A[1]: 0.9927727080215302
A[2]: 0.20945017674179256
A[3]: 0.7227261032813783
A[4]: 0.020413768735719873
A[5]: 0.5091398541631915
A[6]: 0.7829523285265241
A[7]: 0.8786898050745833
A[8]: 0.0532760549887723
A[9]: 0.4770259118024267
A[10]: 0.36052267970606433
A[11]: 0.9339965933637324
A[12]: 0.44119689343353763
A[13]: 0.91604465953217
A[14]: 0.3806089534390542
Sorted:
A[0]: 0.020413768735719873
A[1]: 0.0532760549887723
A[2]: 0.20945017674179256
A[3]: 0.36052267970606433
A[4]: 0.3806089534390542
A[5]: 0.44119689343353763
A[6]: 0.4534815873855662
A[7]: 0.4770259118024267
A[8]: 0.5091398541631915
A[9]: 0.7227261032813783
A[10]: 0.7829523285265241
A[11]: 0.8786898050745833
A[12]: 0.91604465953217
A[13]: 0.9339965933637324
A[14]: 0.9927727080215302

#include <stdlib.h>
#include <time.h>
#define M 10000
void inita(void);
void check_sorted(void);
void sort_select(int n);
int maxind(int);
void swap(double *, double *);
double a[M];

void main(void) {
   int starttime, stoptime; /* elapsed time */
   int startclock, stopclock; /* CPU time */
   srand48((long)time(NULL));
   inita();
   starttime = time(NULL); startclock = clock();
   sort_select(M-1);
   stoptime = time(NULL); stopclock = clock();
   printf("Sorting %i numbers\n", M);
   printf("Elapsed time: %ld seconds\n",
       stoptime - starttime);
   printf("CPU time: %.3f seconds\n",
       (double)(stopclock - startclock)/1000000.0);
   check_sorted();
}

void sort_select(int n) {
   int maxi;
   if (n > 0) {
      maxi = maxind(n);
      swap(&a[maxi], &a[n]);
      sort_select(n-1);
   }
}

int maxind(int m) {
   int maxi;
   if (m == 0) return m;
   maxi = maxind(m-1);
   if (a[m] > a[maxi]) return m;
   return maxi;
}

void swap(double *x, double *y) {
   double z = *x;
   *x = *y;
   *y = z;
}

void inita(void) {
   int i;
   for (i = 0; i < M; i++)
      a[i] = drand48();
}

void check_sorted(void) {
   int sorted = 1;
   int i;
   for (i = 0; i < M-1; i++)
      if (a[i] > a[i+1]) sorted = 0;
   if(sorted) printf("Array sorted\n");
   else printf("*** Array NOT sorted\n");
}

Sorting 10000 numbers
Elapsed time: 1 seconds
CPU time: 0.300 seconds
Array sorted

Sorting 100000 numbers
Elapsed time: 32 seconds
CPU time: 31.740 seconds
Array sorted

Revision date: 2011-12-02. (Please use ISO 8601, the International Standard Date and Time Notation.)