CS3343/3341 Analysis of Algorithms Spring 2012 |
Recursive
Selection Sort |
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:| Change Findmax below to a Selection Sort Change max to maxInd (or maxind) add exchange and selectionSort (or selectionsort) functions change the class name to SelectionSort (in Java) | |
|---|---|
| Java | C |
public class Findmax {
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("Max element:" + max(A, N));
}
static double max(double[] A, int n) {
double maxel;
if (n == 1) return A[0];
maxel = max(A, n-1);
if (A[n-1] > maxel) return A[n-1];
return maxel;
}
static void init(double[] A, int n) {
for (int i = 0; i < n; i++)
// 0 < A[i] < 1, uniformly distributed
A[i] = Math.random();
}
static void printit(double[] A, int n) {
for (int i = 0; i < n; i++)
System.out.println("A[" + i + "]: " + A[i]);
}
} | #include <stdio.h>
#include <stdlib.h> // for rand()
#define N 15
void init(double [], int);
void printit(double [], int);
double max(double [], int);
void main(void) {
double A[N]; // array of random numbers
srand(27182818); // initialize the RNG
init(A, N); // rand #s for A[0], ..., A[N-1]
printit(A, N); // print them
printf("Max element: %20.16f\n", max(A, N));
}
double max(double A[], int n) {
double maxel;
if (n == 1) return A[0];
maxel = max(A, n-1);
if (A[n-1] > maxel) return A[n-1];
return maxel;
}
void init(double A[], int n) {
int i;
for (i = 0; i < n; i++)
// 0 < A[i] < 1, uniformly distributed
A[i] = (double)rand()/(double)RAND_MAX;
}
void printit(double A[], int n) {
int i;
for (i = 0; i < n; i++)
printf("A[%2i]:%20.16f\n", i, A[i]);
}
|