A test harness program for testing sorting methods is provided with the rest of

Question

A test harness program for testing sorting methods is provided with the rest of the textbook program files. It is the file Sorts.java in the ch11 package. The program includes a swap method that is used by all the sorting methods to swap array elements.

Describe an approach to modifying the program so that after calling a sorting method the program prints out the number of swaps needed by the sorting method.

Implement your approach.

Test your new program by running the selectionSort method. Your program should report 49 swaps.

Explanation / Answer

// Sorts.java
import java.util.*;
import java.text.DecimalFormat;

public class Sorts
{
static final int TOTAL = 50;
static int[] elements = new int[TOTAL];
static int totalSwaps = 0;

static void initelements()
{
Random rand = new Random();
for (int i = 0; i < TOTAL; i++)
elements[i] = Math.abs(rand.nextInt()) % 100;
}

static public boolean isSorted()
{
boolean s = true;
for (int i = 0; i < (TOTAL - 1); i++)
if (elements[i] > elements[i + 1])
s = false;
return s;
}

static public void swap(int i1, int i2)
{
totalSwaps++;
int temp = elements[i1];
elements[i1] = elements[i2];
elements[i2] = temp;
}

static public void display()
{
int v;
DecimalFormat format = new DecimalFormat("00");
System.out.println("The elements array is:");
for (int i = 0; i < TOTAL; i++) {
v = elements[i];
if (((i + 1) % 10) == 0)
System.out.println(format.format(v));
else
System.out.print(format.format(v) + " ");
}
System.out.println();
}

static int getMinimum(int start, int end)
{
int iOfMin = start;
for (int i = start + 1; i <= end; i++)
if (elements[i] < elements[iOfMin])
iOfMin = i;
return iOfMin;
}

static void selectionSort()

{
int end = TOTAL - 1;
for (int i = 0; i < end; i++)
swap(i, getMinimum(i, end));
}

public static void main(String[] args) {
initelements();
display();
System.out.println("elements is sorted: " + isSorted());
System.out.println();
selectionSort();

System.out.println("No of swaps :" + totalSwaps);
display();
System.out.println("elements is sorted: " + isSorted());
System.out.println();
}
}

/*

OUTPUT:

The elements array is:
25 24 25 17 27 09 37 67 90 10
91 06 72 14 85 91 60 28 96 96
79 33 88 48 76 83 30 22 73 41
20 99 12 37 87 96 39 20 41 21
23 71 36 31 76 36 74 75 93 40

elements is sorted: false

No of swaps :49
The elements array is:
06 09 10 12 14 17 20 20 21 22
23 24 25 25 27 28 30 31 33 36
36 37 37 39 40 41 41 48 60 67
71 72 73 74 75 76 76 79 83 85
87 88 90 91 91 93 96 96 96 99

elements is sorted: true
*/

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.