Thread: Quick Sort using java

Forum : New To Java   15-12-2017 11:28:16 AM
User Image
Amritk

Newbie

Joined: May 8, 2017

Points: 230

Threads: 57

Posts: 211

Quick Sort using java

| Quote Date : Dec 15, 2017    Views:308    

Quick sort is a similar to merge sort. This is also based on divide and Conquer concept.

Quick sort is a very fast in sorting and it takes very less space compare to merge sort.

Introduction:

Quick sort we generally prefered when we have big data volumes. First we partitioned the array, then recursively sorting each partition. In Partition , one of the array elements is selected as a pivot value. We can pick randomely any one value that value is called as pivot value. Values smaller than the pivot value are placed to the left of the pivot, while larger values are placed to the right.

Example- int arr[]={5,3,4,6,1,8};

Now apply divide and conqure alogorithm...

1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be any value, which is in range of sorted values, even if it doesn't present in the array.

Suppose i selected 4 as a pivot element.
 
2. Now we neet to rearrange elements in such a way, that all elements which are lesser than the pivot go to the left side of the array.

3.And all elements greater than the pivot, go to the right side of the array. Values equal to the pivot can stay in any part of the array.

Now apply rule 2 and 3, it will look like this..

1,3,4,6,5,8

3.Sort these both parts. now we will apply quicksort algorithm recursively to the left and the right parts.

1,3,4,5,6,8

In short, we have three main parts:

1.Elements less than the Pivot element
2.Pivot element(Central element)
3.Elements greater than the pivot element



Sort {1, 11, 8, 30, 9, 15, 2, 6, 1} using quicksort.

How to implemente?

Pivot element=9(assume)

There are two indexes i and j, where i will point to the first element in the array and j points to the last element.

Then index i forward, until an element with value greater or equal to the pivot is found.
Index j is moved backward, until an element with value lesser or equal to the pivot is found.

If i ≤ j then they are swapped and i steps to the next position (i + 1), j steps to the previous one (j - 1). till, i becomes greater than j.

After partition, all values before i-th element are less or equal than the pivot and all values after j-th element are greater or equal to the pivot.


Programe:

public class QuickSortTest{

    public static void main(String args[]) {

        // unsorted integer array
        int[] unsorted = {1, 11, 8, 30, 9, 15, 2, 6, 1};
        System.out.println("Unsorted array :" + Arrays.toString(unsorted));

        QuickSortImpl quick = new QuickSortImpl();

       
        quick.sort(unsorted);

        // printing sorted array
        System.out.println("Sorted array :" + Arrays.toString(unsorted));

    }

}

class QuickSortImpl {

    private int arrayInput[];
    private int length;

    public void sort(int[] numbers) {

        if (numbers == null || numbers.length == 0) {
            return;
        }
        this.arrayInput = numbers;
        length = numbers.length;
        quickSort(0, length - 1);
    }

    /*
     * This method implements in-place quicksort algorithm recursively.
     */
    private void quickSort(int low, int high) {
        int i = low;
        int j = high;

        // pivot is middle index
        int pivot = arrayInput[low + (high - low) / 2];

        // Dividing into two arrays
        while (i <= j) {
           //rule 2 and 3
            while (input[i] < pivot) {
                i++;
            }
            while (input[j] > pivot) {
                j--;
            }
            if (i <= j) {
                swap(i, j);
                // move index to next position on both sides
                i++;
                j--;
            }
        }

        // calls quickSort() method recursively
        if (low < j) {
            quickSort(low, j);
        }

        if (i < high) {
            quickSort(i, high);
        }
    }

    private void swap(int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}



Load More

No More Comments