My program seems to be written perfectly, but stops running and allows user input with no scanner?

Question

first time post here.

I am trying to create a class which compares quick sort, merge sort, bubble sort, and selection sort. I have implemented all of the sort methods and created a random array method which populates a random array with 1000 random ints. However when I run my program my main method stops after the initial welcome message and allows for user input. Any help would be greatly appreciated, I'm sure its some simple mistake I am missing.

import java.util.Random;
public class TestSort {
private static int selectCount;
private static int bubbleCount;
private static int mergeCount;
private static int quickCount;

public static void main(String[] args){
    System.out.println("Welcome to the search tester.  "
            + "We are going to see which algorithm performs the best out of 20 tests"); 

    int testSelection = 0;
    int testBubble = 0;
    int testQuick = 0;
    int testMerge = 0;

    //Check tests
        int[] a = new int[1000];
        populateArray(a);

        int[] select = a;
        int[] bubble = a;
        int[] quick = a;
        int[] merge = a;

        testSelection = selectionSort(select);
        testBubble = bubbleSort(bubble);
        testQuick = quickSort(quick,0,0);
        testMerge = mergeSort(merge);

        System.out.println("Selection sort number of checks: " + testSelection);
        System.out.println("Bubble sort number of checks: " + testBubble);
        System.out.println("Quick sort number of checks: " + testQuick);
        System.out.println("Merge sort number of checks: " + testMerge);
        System.out.println("");
    }


public static int[] populateArray(int[] a)
{
    Random r = new Random();
    a = new int[1000];


    for(int i=0; i < a.length; i++)
    {
        int num = r.nextInt(1000);
        a[i] = num;
    }
    return a;
}

//Sorting methods

public static int selectionSort(int[] a)
{
    for (int i = 0; i < a.length; i++)
    {
        int smallestIndex = i;
        for (int j=i; j<a.length; j++)
        {
            if(a[j]<a[smallestIndex])
            {
                smallestIndex = j;
            }
        }
        if(smallestIndex != i) //Swap
        {
            int temp = a[i];
            a[i] = a[smallestIndex];
            a[smallestIndex] = temp;
            selectCount++;
        }
    }
    return selectCount;
}

public static int bubbleSort (int[] a)
{
    boolean hasSwapped = true;
    while (hasSwapped == true)
    {
        hasSwapped = true;
        for(int i = 0; i<a.length-1; i++)
        {
            if(a[i] > a[i+1]) //Needs to swap
            {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                hasSwapped = true;
                bubbleCount++;
            }
        }
    }
    return bubbleCount;
}

public static int mergeSort(int [] a)
{
    int size = a.length;
    if(size<2)//recursive halting point
    {
        return 0;
    }

    int mid = size/2;
    int leftSize = mid;
    int rightSize = size-mid;
    int [] left = new int[leftSize];
    int [] right = new int[rightSize];

    for(int i = 0; i<mid; i++)
    { 
        mergeCount++;
        left[i] = a[i];
    }
    for(int i = mid; i<size; i++)
    {
        mergeCount++;
        right[i-mid]=a[i];
    }
    mergeSort(left);
    mergeSort(right);
    //merge
    merge(left,right,a);
    return mergeCount;
}
private static void merge(int [] left, int [] right, int [] a)
{
    int leftSize = left.length;
    int rightSize = right.length;
    int i = 0;//index of the left array
    int j = 0; //index of right array
    int k = 0; //index of the sorted array [a]

    while(i<leftSize && j<rightSize)
    {
        if(left[i]<=right[j])
        {
            a[k] = left[i];
            i++;
            k++;
        }
        else
        {
            a[k] = right[j];
            j++;
            k++;
        }
    }
    while(i<leftSize)
    {
        a[k] =left[i];
        i++;
        k++;
    }
    while(j<rightSize)
    {
        a[k] =right[j];
        j++;
        k++;
    }
}

public static int quickSort(int[] a, int left, int right)
{
    //partition, where pivot is picked 
    int index = partition(a,left,right);
    if(left<index-1)//Still elements on left to be sorted
        quickSort(a,left,index-1);
    if(index<right) //Still elements on right to be sorted
        quickSort(a,index+1,right);
        quickCount++;

    return quickCount;
}
private static int partition(int[] a, int left, int right)
{
    int i = left;
    int j = right; //Left and right are indexes
    int pivot = a[(left+right/2)]; //Midpoint, pivot

    while(i<j)
    {
        while(a[i]<pivot)
        {
            i++;
        }
        while(a[j]>pivot)
        {
            j--;
        }
        if(i<=j) //Swap
        {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
        return i;
    }
}

Might not be the actual problem, but @MichaelMarkidis is correct, there is an infinite loop in your code. `boolean hasValue` is never set to false. — Brydenr, Sep 23 '16 at 21:27
How do you run this code? Is it in IDE like Eclipse? If yes then consoles in such IDEs may allow you to write something in them when they are not used even if you are not asked to do so. You can get enough time for that when for instance your code will be busy doing some time-consuming tasks, or even when it enters infinite loop. — Pshemo, Sep 23 '16 at 21:28
BTW `int[] select = a; int[] bubble = a; int[] quick = a; int[] merge = a;` doesn't create copy of array held by `a`. You are simply assigning same array to many new variables, meaning that if you order that one array, you will see it ordered via all these variables. — Pshemo, Sep 23 '16 at 21:30
Okay I think it must be a problem with my bubblesort, however Pshemo what is a better way to go about copying the arrays? — Jake Lizama, Sep 23 '16 at 21:31
http://stackoverflow.com/questions/5785745/make-copy-of-array-java — Pshemo, Sep 23 '16 at 21:32

score 1 · Answer 1 · answered Sep 23 '16 at 21:28

Your infinite loop is in bubbleSort:

public static int bubbleSort(int[] a)
{
    boolean hasSwapped = true;
    while (hasSwapped == true)
    {
        hasSwapped = false; // Need to set this to false
        for (int i = 0; i < a.length - 1; i++)
        {
            if (a[i] > a[i + 1]) // Needs to swap
            {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
                hasSwapped = true;
                bubbleCount++;
            }
        }
    }
    return bubbleCount;
}

codemirel · Answer 2 · 2016-09-23T21:34:28.147

1

The problem is in your bubbleSort() method. The hasSwapped boolean is never set to false, so the while loops infinite times.

There is another problem in your code. In the main method, you will have to assign the array that the populateArray() method returns back to a. And the such assignments as int[] select = a; you do in the main method do not do what you want to do. Instead, just send the array a to your sorting methods.

Like this:

int[] a = new int[1000];
a=populateArray(a);

testSelection = selectionSort(a);
testBubble = bubbleSort(a);
testQuick = quickSort(a,0,0);
testMerge = mergeSort(a);

edited Sep 23 '16 at 21:34

answered Sep 23 '16 at 21:29

codemirel

160
10

1

Won't this not work because it will sort the already sorted arrays? – Jake Lizama Sep 23 '16 at 21:42

My program seems to be written perfectly, but stops running and allows user input with no scanner?

2 Answers2