miwa_p
miwa_p

Reputation: 435

quicksort an array and do binary search in java

So I have to make a method which is using the quicksort as a sort algorithm without using the Java API. Then I have to write another method that gives the sorted array back and using the binary search return true if the searched element is found in it. I have no idea where am I making the stupid mistake.

public class Aufgabe1 {
    public static void sort(int[] array) {
        /* TODO: add code here */
        sort(array, 0, array.length - 1);

    }

    public static void sort(int[] array, int start, int end) {
        int i = start;
        int j = end;
        int pivot = array[(start+end)/2];
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (pivot < array[j]) {
                j--;
            }

            if (i <=j) {
                int h = array[i];
                array[i] = array[j];
                array[j] = h;
                i++;
                j--;
            }
        }
        if (start < i-1) {
            sort(array, start, i - 1);
        }
        if (i < end) {
            sort(array, i, end);
        }

    }

    public static boolean binSearch(int[] array, int elem) {
        /* TODO: add code here */

        int i = 0; //the first element
        int j = array.length -1; // the last element

        while (i<=j) {
            int k = i + ((i+j)/2); //try the middle word
            if (elem == array[k]){
                return true;
            }
            if (elem < array[k]) {
                j = k-1;
                return false;
            }else {
                i = k+1;
                return false;
            }
        }
        return false;
    }

    //just for testing
    public static void main(String[] args) {

        int[] arr = new int[] {5, 3, 7, 2, 1, 6};

        sort(arr);

        for(int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");

        }
        binSearch(arr,5);

    }

Upvotes: 3

Views: 649

Answers (1)

James
James

Reputation: 1501

Try this, fixed a few small errors, you had a couple of i and j in the wrong places. Although, I suggest you modularise your code a bit as this will make things easier to read and give you a better idea of what is happening. Note that you are not actually returning in the correct places, so it will always return false unless the element is in the middle. On a side note, the use of static is also discouraged.

EDIT: Also, I have just noticed you have a '}' missing at the end where you should close the class.

public class Main
{
    public static void sort(int[] array) 
    {
        /* TODO: add code here */
        sort(array, 0, array.length - 1);
    }

    public static void sort(int[] array, int start, int end) 
    {
        int i = start;
        int j = end;
        int pivot = array[(start+end)/2];

        while (i <= j)
        {
            while (array[i] < pivot) 
            {
                i++;
            }

            while (pivot < array[j]) 
            {
                j--;
            }

            if (i <=j)
            {
                int h = array[i];
                array[i] = array[j];
                array[j] = h;
                i++;
                j--;
            }
        }

        if (start < i-1)
        {
            sort(array, start, i - 1);
        }

        if (i < end) 
        {
            sort(array, i, end);
        }
    }

    public static boolean binSearch(int[] array, int elem) 
    {
        /* TODO: add code here */

        int i = 0; //the first element
        int j = array.length -1; // the last element
        int k = i + ((i+j)/2); //try the middle word

        while (k >= 0 && k < array.length) 
        {
            if (elem == array[k])
            {
                return true;
            }

            if (elem < array[k]) 
            {
                k--;
            }

            else
            {
                k++;
            }
        }

        return false;
    }

    //just for testing
    public static void main(String[] args)
    {
        int[] arr = new int[] {5, 3, 7, 2, 1, 6};

        sort(arr);

        for(int i = 0; i < arr.length; i++)
        {
            System.out.print(arr[i] + " ");
        }

        if (binSearch(arr,5))
        {
            System.out.println("TRUE");
        }
    }
}

Upvotes: 1

Related Questions