0 Replies - 413 Views - Last Post: 28 November 2017 - 03:29 PM Rate Topic: -----

#1 ThatKidRib  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 28-November 17

Issue with my tables and saving each comparison value

Posted 28 November 2017 - 03:29 PM

Hi, I thought that I had completed this code correctly but when I turned it in to my teacher I was told that the way I print my tables isn't correct. First, the table is supposed to print once for each of the sorts (insertion, merge, quick) instead of for each repeat of the sorts. Second, the table is supposed to display the max, min, and average number of comparisons in the repeats of the sorts, not the max, min and average of the random integers. I've tried messing around with the code to get this to happen but I can't figure out how to do it. I'm not sure where I would put my prints at since the sorts are all supposed to run recursively. I also don't know how I would save the comparisons of each repeat of a sort because it runs recursively so the way I see it, whatever variable I set it to would get saved over after each run. If anyone has any ideas on what I could do and would lead me in that direction I would be grateful. Sorry for posting the entire program but I think the problem can be resolved by examining each individual method for the sorts.


//*********************************************************************
// FILE NAME    : SortDecoder.java
// DESCRIPTION  : This file contains the class SortDecoder.
//*********************************************************************
//Program by: Robert D
package sortdecoder;

/**
 *
 * @author Robert
 */
import java.util.*;
public class SortDecoder 
{
    // These variables keep track of the occurences while sorting.
    private static int mergeCalls = 0, mergeMoves = 0, mergeComps = 0;
    private static int quickCalls = 0, quickComps = 0, quickMoves = 0;
    // Set to TRUE to print the array contents before and after sorting
    private static final boolean FULLPRINT = true;
    static int max = 0;
    static int min = 1000000000; //Large number so that min has to be in array
    static int avg;
    static int total;
    
public static void main(String[] args) 
{
    Scanner input = new Scanner(System.in);
    System.out.print("Array size?");
    int size = input.nextInt();
    System.out.print("How many repeats? ");
    int repeats = input.nextInt();
    

    System.out.println("INSERTION SORT");
    for (int z=0; z < repeats; z++) 
    {
	insertion(sortTest(size), z);
	if (FULLPRINT && z < repeats-1) 
        {
            System.out.println();
        }
    }
    

    System.out.println("MERGE SORT");
    for (int z=0; z < repeats; z++) 
    {
	mergesort(sortTest(size), z);
	if (FULLPRINT && z < repeats-1)
        {
            System.out.println();
        }
    }

    
    System.out.println("QUICK SORT");
    for (int z=0; z < repeats; z++) 
    {
	quicksort(sortTest(size), z);
	if (FULLPRINT && z < repeats-1)
        {
            System.out.println();
        }
    } 
}	
// Makes an array with random numbers to test the sorting algorithms.
private static int[] sortTest(int size) 
{
    int[] a = new int[size];
    Random rand = new Random();
    for (int i=0; i < size; i++) 
    {
        a[i] = rand.nextInt(10000); 
        total += a[i];
        if(a[i] > max)
        {
           max = a[i]; 
        }
        if(a[i] < min)
        {
            min = a[i];
        }
        
    }
    avg = total / a.length;
    return a;
}	
// Prints the array if FULLPRINT is true
private static void print(int[] a) 
{
    if (!FULLPRINT)
    {
        return;
    }
    System.out.print("\t");
    for (int i=0; i < a.length; i++) 
    {
        System.out.print(a[i]);
        if (i < a.length-1) 
        {
            System.out.print(", ");
        }
    }
    System.out.println();
}	
// Checks that the sorted array is in order
private static boolean inOrder(int[] a) 
{
    boolean inOrder = true;
    for (int i=1; i < a.length; i++)
    {
        if (a[i] < a[i-1])
        {
            inOrder = false;
        }
    }
    return inOrder;
}	
// Insertion sort. O(n^2) comparisons and swaps
private static void insertion(int[] a, int repeat) 
{
    long moves = 0, comps = 0; // Number of moves and comparisons
    print(a); // Print unsorted
    long startTime = System.currentTimeMillis();	
    int temp;
    int j;
    // Go through the list. Starts at the second element
    for (int i=1; i < a.length; i++) 
    {
	for (j = i; j > 0 && a[j-1] > a[j]; j--) 
        {
            comps++;		
            temp = a[j]; // Store the int so we don't lose it
            a[j] = a[j-1]; // Move the smaller int where the bigger int was
            a[j-1] = temp; // Put the bigger int where the smaller int was
            moves++;
	}
    }	
    long endTime = System.currentTimeMillis();
    print(a); // Print sorted
    System.out.println("\tRepeat " + (repeat+1) + "\tSize: " + a.length + "\tTime to sort: " + (endTime-startTime) + " milliseconds" + "\tMoves: " + moves + "\tComparisons: " + comps + "\tIn Order: " + inOrder(a));
    System.out.println("\nTABLE");
    System.out.println("\nMax entry " + max);
    System.out.println("Min entry " + min);
    System.out.println("Average entry " + avg + "\n");
    // Reset the counters
    max = 0; min = 10000000; total = 0;
}
// Merge sort is O(n log n).
private static void mergesort(int[] a, int repeat) 
{
    print(a); // Print unsorted
    long startTime = System.currentTimeMillis(); 
    mergesort(a, 0, a.length-1);	
    long endTime = System.currentTimeMillis(); 
    print(a); // Print sorted
    System.out.println("\tRepeat " + (repeat+1) + "\tSize: " + a.length + "\tTime to sort: " + (endTime-startTime) + " milliseconds" + "\tMoves: " + mergeMoves + "\tComparisons: " + mergeComps + "\tIn Order: " + inOrder(a) + "\tMerge Calls: " + mergeCalls);
    System.out.println("\nTABLE");
    System.out.println("\nMax entry " + max);
    System.out.println("Min entry " + min);
    System.out.println("Average entry " + avg + "\n");
    // Reset the counters
    max = 0; min = 10000000; total = 0;
    mergeCalls = 0; mergeMoves = 0; mergeComps = 0;
}		
//The mergesort algorithm. Splits the array in half and then sorts smaller pieces.
private static void mergesort(int[] a, int top, int bottom) 
{
    mergeCalls++;
    if (top != bottom) 
    {
        int middle = (top + bottom) / 2;
	mergesort(a, top, middle);
	mergesort(a, middle+1, bottom);
	merge(a, top, bottom);
    }
}	
private static void merge(int[] a, int top, int bottom) 
{
    int t = top;
    int middle = (top + bottom) / 2;
    int b = middle + 1;
    int i = 0;
    int[] s = new int[bottom - top + 1];
    while (t <= middle && b <= bottom) 
    {			
        if (a[t] < a[b]) 
        {
            s[i] = a[t];
            t++;
	}
        else 
        {
            s[i] = a[b];
            b++;
	}
	i++;
        mergeComps++;
	mergeMoves++;
    }	
    int last = middle;
    if (b <= bottom) 
    {
        t = b;
        last = bottom;
    }	
    while (t <= last) 
    {
        s[i] = a[t];
	t++;
	i++;
	mergeMoves++;
    }	
    for (i = 0; i < s.length; i++) 
    {
        a[i + top] = s[i];
	mergeMoves++;
    }
}	 
private static void quicksort(int[] a, int repeat) 
{
    print(a); // Print unsorted
    long startTime = System.currentTimeMillis();
    quicksort(a, 0, a.length-1);
    long endTime = System.currentTimeMillis();
    print(a); // Print sorted
    System.out.println("\tRepeat " + (repeat+1) + "\tSize: " + a.length + "\tTime to sort: " + (endTime-startTime) + " milliseconds" + "\tMoves: " + quickMoves + "\tComparisons: " + quickComps + "\tIn Order: " + inOrder(a) + "\tQuickSort Calls: " + quickCalls);
    System.out.println("\nTABLE");
    System.out.println("\nMax entry " + max);
    System.out.println("Min entry " + min);
    System.out.println("Average entry " + avg + "\n");
    // Reset the counters
    max = 0; min = 10000000; total = 0;
    quickCalls = 0; quickComps = 0; quickMoves = 0; // Reset the counters
}	
// The quicksort algorithm
private static void quicksort(int[] a, int bottom, int top) 
{
    quickCalls++;		
    if (bottom < top) 
    {
	int p = partition(a, bottom, top);
	quicksort(a, bottom, p-1);
	quicksort(a, p+1, top);
    }
}	
// Returns an array index that assures the array has been sorted so that all entires before are bigger and all entries after are smaller
private static int partition(int[] a, int bottom, int top) 
{
    int temp = a[bottom]; // The int that is being switched	
    while (bottom != top) 
    {		
        while (bottom < top && temp <= a[top]) 
        {
            // Move the top cursor down until we find a value smaller than temp/bottom
            top--;
            quickComps++;
	}
	if (bottom != top) 
        {
            a[bottom] = a[top]; // Swap them
            quickMoves++;
	}		
	while (bottom < top && temp >= a[bottom]) 
        {
            // Move the bottom cursor up until we find a value bigger than temp/top
            bottom++;
            quickComps++;
	}		
	if (bottom != top) 
        {
            a[top] = a[bottom]; // Swap them
            quickMoves++;
	}
    }	
    a[bottom] = temp; // Finish the switch
    return bottom;
}
}



Is This A Good Question/Topic? 0
  • +

Page 1 of 1