import java.util.ArrayList;
import java.util.Random;
public class Sorting
{
public static int numOfComps = 0, // Number of comparisons
numOfSwaps = 0; // Number of swaps
public static void main(String[] args)
{
System.out.println("\n\nSelection Sort:");
System.out.println("\n\nQuick Sort:");
System.out.println("\nOriginal order:\n");
int size = 5;
ArrayList<Integer> list = new ArrayList<Integer>(size);
for(int i = 1; i <= size; i++)
{
list.add(i);
}
Random rand = new Random();
while(list.size() > 0)
{
int index = rand.nextInt(list.size());
System.out.print(list.remove(index) + " ");
}
//Sort the array
selectionSort(list);
quickSort(list);
System.out.println("\nSorted order: ");
System.out.print(list + " ");
}
public static void selectionSort(int[] array)
{
int startScan; // Starting position of the scan
int index; // To hold a subscript value
int minIndex; // Element with smallest value in the scan
int minValue; // The smallest value found in the scan
// The outer loop iterates once for each element in the
// array. The startScan variable marks the position where
// the scan should begin.
for (startScan = 0; startScan < (array.length-1); startScan++)
{
// Assume the first element in the scannable area
// is the smallest value.
minIndex = startScan;
minValue = array[startScan];
// Scan the array, starting at the 2nd element in
// the scannable area. We are looking for the smallest
// value in the scannable area.
for(index = startScan + 1; index < array.length; index++)
{
if (array[index] < minValue)
{
minValue = array[index];
minIndex = index;
numOfSwaps ++;
}
numOfComps ++; //get 15 comparisons here
}
// Swap the element with the smallest value
// with the first element in the scannable area.
array[minIndex] = array[startScan];
array[startScan] = minValue;
//numOfComps ++; // Get 5 comparisons here
}
System.out.println("\n\nNumber of comps = " + numOfComps);
System.out.println("Number of swaps = " + numOfSwaps);
}
public static void quickSort(int array[])
{
doQuickSort(array, 0, array.length - 1);
System.out.println("\n\nNumber of comps = " + numOfComps);
System.out.println("Number of swaps = " + numOfSwaps);
}
/**
The doQuickSort method uses the QuickSort algorithm
to sort an int array.
@param array The array to sort.
@param start The starting subscript of the list to sort
@param end The ending subscript of the list to sort
*/
private static void doQuickSort(int array[], int start, int end)
{
int pivotPoint;
if (start < end)
{
numOfComps++;
// Get the pivot point.
pivotPoint = partition(array, start, end);
// Sort the first sub list.
doQuickSort(array, start, pivotPoint - 1);
// Sort the second sub list.
doQuickSort(array, pivotPoint + 1, end);
}
}
/**
The partiton method selects a pivot value in an array
and arranges the array into two sub lists. All the
values less than the pivot will be stored in the left
sub list and all the values greater than or equal to
the pivot will be stored in the right sub list.
@param array The array to partition.
@param start The starting subscript of the area to partition.
@param end The ending subscript of the area to partition.
@return The subscript of the pivot value.
*/
private static int partition(int array[], int start, int end)
{
int pivotValue; // To hold the pivot value
int endOfLeftList; // Last element in the left sub list.
int mid; // To hold the mid-point subscript
// Find the subscript of the middle element.
// This will be our pivot value.
mid = (start + end) / 2;
// Swap the middle element with the first element.
// This moves the pivot value to the start of
// the list.
swap(array, start, mid);
// Save the pivot value for comparisons.
pivotValue = array[start];
// For now, the end of the left sub list is
// the first element.
endOfLeftList = start;
// Scan the entire list and move any values that
// are less than the pivot value to the left
// sub list.
for (int scan = start + 1; scan <= end; scan++)
{
if (array[scan] < pivotValue)
{
endOfLeftList++;
swap(array, endOfLeftList, scan);
//numOfSwaps ++;
}
numOfComps++;
}
// Move the pivot value to end of the
// left sub list.
swap(array, start, endOfLeftList);
// Return the subscript of the pivot value.
return endOfLeftList;
}
/**
The swap method swaps the contents of two elements
in an int array.
@param The array containing the two elements.
@param a The subscript of the first element.
@param b The subscript of the second element.
*/
private static void swap(int[] array, int a, int b)
{
int temp;
temp = array[a];
array[a] = array[b];
array[b] = temp;
numOfSwaps++;
}
}
How do I clone or copy the random generated numbers to the Selection Sort and Quicksort methods so that both sort methods have the same random generated numbers? And did I correctly place the number of comparisons and number of swaps codes into each sort method? I have thoroughly searched on Google for these answers to no avail. Please help. Thank you.
Aucun commentaire:
Enregistrer un commentaire