3
\$\begingroup\$

So I'm writing a program that compares Bubble, Selection, Merge, and Quick Sort. All 4 methods are given a randomized array of 1000 elements and I count to see how many times it takes a method to perform to fully sort the array. My question revolves around the placement of my counts. I know I should look at the Big O complexities for each to get a ballpark estimate of the number but I'm just asking if I put the counts in the right spots.

import java.util.*;

public class SortingComparison1 
{
   //Creates class variables
   static Random random = new Random();
   static int bubbleCount = 0;
   static int totalBubbleCount = 0;
   static int totalSelectionCount = 0;
   static int totalMergeCount = 0;
   static int totalQuickCount = 0;
   static int mergeCount = 0;
   static int selectionCount = 0;
   static int quickCount = 0;
   static int [] arr;
   static int [] copyArr;
   static int [] copyArr2;
   static int [] copyArr3;

public static void main(String[] args) 
{
    System.out.println("Welcome to the sort tester.");
    //runs this 20 times
    for(int i = 0; i <20; i++)
    {
        //assigns array arr to the gen array method
        arr = generateRandomArray();
        //creates copy arrays and copies the arr array
        copyArr = Arrays.copyOf(arr, arr.length);
        copyArr2 = Arrays.copyOf(arr, arr.length);
        copyArr3 = Arrays.copyOf(arr, arr.length);
        //Call each method for the different sorts
        System.out.println();
        bubble();
        System.out.println();
        selection();
        System.out.println();
        merge();
        System.out.println();
        quick();
    }
    System.out.println();
    System.out.println("The average number of checks were:");
    System.out.println("Bubble Count " + (totalBubbleCount / 20));
    System.out.println("Selection Count " + (totalSelectionCount / 20));
    System.out.println("Merge Count "+ (totalMergeCount / 20));
    System.out.println("QuickSort Count " + (totalQuickCount / 20));
}

public static void bubble()
{
    //assigns int[]a to arr
    int[] a = arr;
    System.out.println("Array Before Bubble Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out unsorted array
        System.out.print(a[i] + " ");
    }
    //sorts array with bubble sort method
    bubbleSort(a);
    System.out.println("");
    System.out.println("Array After Bubble Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out bubble sorted array
        System.out.print(a[i] + " ");
    }
    System.out.println();
    //Prints out number of checks to sort array
    System.out.println("Bubble checks: " + bubbleCount);
    totalBubbleCount += bubbleCount;
    //resets bubbleCount
    bubbleCount = 0;
}

public static void selection()
{
    // assigns int[] a to the copied array
    int[] a = copyArr;
    System.out.println("Array Before Selection Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out unsorted array
        System.out.print(a[i] + " ");
    }
    //sorts int[] a with selection sort
    selectionSort(a);
    System.out.println("");
    System.out.println("Array After Selection Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out selection sorted array
        System.out.print(a[i] + " ");
    }
    System.out.println();
    //Prints out number of selections counts
    System.out.println("Selection checks: " + selectionCount);
    totalSelectionCount += selectionCount;
    //resets selectionCount
    selectionCount = 0;
}

public static void merge()
{   
    //assigns int[] a to second copied array
    int[] a = copyArr2;
    System.out.println("Array Before Merge Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints unsorted array
        System.out.print(a[i] + " ");
    }
    //sorts array with mergeSort method
    mergeSort(a);
    System.out.println("");
    System.out.println("Array After Merge Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out merge sorted array
        System.out.print(a[i] + " ");
    }
    System.out.println();
    //Prints out number of checks
    System.out.println("Merge checks: " + mergeCount);
    totalMergeCount += mergeCount;
    //resets mergeCount
    mergeCount  = 0;
}

public static void quick()
{
    //assigns int[] a to third copied array
    int[] a = copyArr3;
    System.out.println("Array Before Quick Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out unsorted array
        System.out.print(a[i] + " ");
    }
    //sorts array by calling quickSort method
    quickSort(a, 0, a.length - 1);
    System.out.println("");
    System.out.println("Array After Quick Sort");
    for (int i = 0; i < a.length; i++) 
    {
        //Prints out quick sorted array
        System.out.print(a[i] + " ");
    }
    System.out.println();
    //prints out quickCount and resets quickCount back to 0
    System.out.println("QuickSort checks: " + quickCount);
    totalQuickCount += quickCount;
    //prints avg num of checks
    quickCount = 0;
}

private static int[] generateRandomArray() 
{
    //generates array of size 1000 and fill it with random numbers, 0-999
    int size = 20;
    int[] a = new int[size];
    for (int i = 0; i < size; i++) 
    {
        a[i] = random.nextInt(1000);
    }
    return a;       
}

public static int[] bubbleSort(int[] a)
{
    boolean done = false;
    int n = a.length;
    while(done == false)//runs n times
    {
        done = true;
        for(int i = 0; i < n-1; i++)//runs n times
        {

            if(a[i] > a[i+1])//Swap
            {
                bubbleCount++;
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                done = false;
            }

        }
    }
    return a;
}

public static void mergeSort(int [] a)
{
    //put counter for checks inside method
    int size = a.length;
    if(size < 2)//Halt recursion
    {
        return;
    }
    int mid = size/ 2;
    int leftSize = mid;
    int rightSize = size - mid;
    int[] left = new int[leftSize];
    int[] right = new int[rightSize];
    //populate left
    for(int i = 0; i < mid; i++)
    {
        mergeCount++;
        left[i] = a[i];
    }
    //populate right
    for(int i = mid; i < size; i++)
    {
        mergeCount++;
        right[i-mid] = a[i];
    }
    mergeSort(left);
    mergeSort(right);
    //merge
    merge(left, right, a);
}

public static void merge(int[] left, int[] right, int[] a)
{
    int leftSize = left.length;
    int rightSize = right.length;
    int i = 0;//index for left
    int j = 0;//index for right
    int k = 0;//index for a
    while(i < leftSize && j < rightSize)//compares until the end is reach in either 
    {
        if(left[i] <= right[j])
        {
            //assigns a[k] to left[i] and increments both i and k
            a[k] = left[i];
            i++;
            k++;
        }
        else
        {
            //assigns a[k] to right [j] and increments j  and k
            a[k] = right[j];
            j++;
            k++;
        }
    }
    //fills in the rest
    while(i<leftSize)
    {
        a[k] = left[i];
        i++;
        k++;
    }
    while(j<rightSize)
    {
        a[k] = right[j];
        j++;
        k++;
    }
}

public static void selectionSort(int[] a )
{
    for (int i = 0; i < a.length - 1; i++) 
    {
        int pos = i;
        for (int j = i + 1; j < a.length; j++) 
        {
            // increments selection count
            selectionCount++;
            // if a[j] is less than a[pos], set pos to j
            if (a[j] < a[pos]) 
            {
                pos = j;
            }   
        }

        // swaps a[i] and a[pos]
        int temp = a[i];
        a[i] = a[pos];
        a[pos] = temp;
    }
}
public static void quickSort(int[] a, int left, int right)
{
    int index = partition(a, left, right);
    if(left < index - 1)
    {
        //increments quickCount and calls quickSort recursively
        quickCount++;
        quickSort(a, left, index-1);    
    }
    if(index < right)
    {
        //increments quickCount and calls quicSort recursively
        quickCount++;
        quickSort(a, index, right);
    }
}
public static int partition(int[] a, int left, int right)
{
    int i = left;
    int j = right;
    int pivot = a[((left+right)/2)];
    while(i<=j)
    {
        while(a[i] < pivot)
        {
            i++;//correct position so move forward
        }
        while(a[j] > pivot)
        {
            j--;//correct position 
        }
        if(i <= j)
        {
            //swaps and increments i and decrements j
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}
}
\$\endgroup\$
  • \$\begingroup\$ What are you countng? Comparisons or swaps? Right now it looks like your counts are not counting either one correctly. \$\endgroup\$ – JS1 Feb 20 '16 at 3:13
  • \$\begingroup\$ Well I'm trying to count how many times it takes to a sort an array, but I think I'm just going to end up doing comparisons. I moved the bubbleCount right above the if statement, moved the mergeCount into the merge method in the first while loop, and then I moved the quickCount into the partition method where a[i] is < or > the pivot. So hopefully that is right. @JS1 \$\endgroup\$ – USC23 Feb 20 '16 at 3:24
  • \$\begingroup\$ Welcome to Code Review! Please declare your cross-post. \$\endgroup\$ – 200_success Feb 20 '16 at 4:36
2
\$\begingroup\$

Magic number

20 - the number of iterations - should be replaced with a static final variable, so that you can freely modify the number of iterations to perform.

Printing arrays

Arrays.toString(int[]) gives you a nice String representation for printing to the console, so you do not have to loop yourself.

Too much static

You are currently using too many static variables to store your data and counts, and that can make it unwieldy.

An alternative modeling approach

How about considering that each test should implement an interface that provides a count of every run, and other useful metrics?

public interface Sorter {

    /**
     * Sorts an array.
     *
     * @param the array to sort
     * @return the number of steps it takes to sort an array
     */
    int sort(int[] array);

    /**
     * Gets the number of method calls to {@link #sort(int[])} so far.
     *
     * @return the number of iterations done
     */
    int getIterations();

    /**
     * Gets the total sorting count so far.
     *
     * @return the total number of sorting steps done
     */
    long getTotalCount();
}

Then you can have implementations...

public class BubbleSorter implements Sorter {

    int iterations = 0;
    long totalCount = 0;

    @Override
    public int sort(int[] array) {
        int countResult = 0;
        // do sorting while calling countResult++ where appropriate
        iterations++;
        totalCount += countResult;
        return countResult;
    }

    @Override
    public int getIterations() {
        return iterations;
    }

    public long getTotalCount() {
        return totalCount;
    }
}

You can then rely on the methods to give you your results.

public static void main(String[] args) {
    Sorter bubbleSort = new BubbleSorter();
    int lastCount = 0;
    for (int i = 0; i < ITERATIONS; i++) {
        lastCount = bubbleSort.sort(getNewRandomArray());
    }
    System.out.println("Last count: " + lastCount);
    System.out.println("Average: " +
            ((bubbleSort.getTotalCount() * 1.0) / bubbleSort.getIterations());
}

Note that this simplified approach does not take multi-threading into consideration. With some slight tweaks to how iterations and totalCount can be accumulated in a thread-safe manner, making calls to each sorting algorithms' sort() method concurrently to reduce execution time is certainly achievable.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.