Implement Quick Sort in Java.

-
*QuickSort:
           Quicksort or partition-exchange sort, is a fast sorting algorithm, which is using divide and conquer algorithm. Quick sort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quick sort can then recursively sort the sub-lists.

 Steps to implement Quick sort:

1) Choose an element, called pivot, from the list. Generally pivot can be the middle index element or u can choose any.
2) Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3) Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
Related image


//Write a Java program to implement quick sort algorithm.

public class QuickSort
{
    public static void main(String[] args)
    {
        // This is unsorted array
        Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };

        // Let's sort using quick sort
        quickSort( array, 0, array.length - 1 );

        // Verify sorted array
        System.out.println(Arrays.toString(array));
    }

    public static void quickSort(Integer[] arr, int low, int high)
    {
        //check for empty or null array
        if (arr == null || arr.length == 0){
            return;
        }
       
        if (low >= high){
            return;
        }

        //Get the pivot element from the middle of the list
        int middle = low + (high - low) / 2;
        int pivot = arr[middle];

        // make left < pivot and right > pivot
        int i = low, j = high;
        while (i <= j)
        {
            //Check until all values on left side array are lower than pivot
            while (arr[i] < pivot)
            {
                i++;
            }
            //Check until all values on left side array are greater than pivot
            while (arr[j] > pivot)
            {
                j--;
            }
            //Now compare values from both side of lists to see if they need swapping
            //After swapping move the iterator on both lists
            if (i <= j)
            {
                swap (arr, i, j);
                i++;
                j--;
            }
        }
        //Do same operation as above recursively to sort two sub arrays
        if (low < j){
            quickSort(arr, low, j);
        }
        if (high > i){
            quickSort(arr, i, high);
        }
    }
   
    public static void swap (Integer array[], int x, int y)
    {
        int temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }
}

Output: [3, 6, 10, 12, 13, 24, 70, 90]

Popular posts from this blog

Priority Scheduling Algorithm Java Program.

-
import java.util.Scanner; public class priority{ public static void main(String args[]) { Scanner s = new Scanner(System.in); int x,n,p[],pp[],bt[],w[],t[],awt,atat,i; p = new int[10]; pp = new int[10]; bt = new int[10]; w = new int[10]; t = new int[10]; //n is number of process //p is process //pp is process priority //bt is process burst time //w is wait time // t is turnaround time //awt is average waiting time //atat is average turnaround time System.out.print("Enter the number of process : "); n = s.nextInt(); System.out.print("\n\t Enter burst time : time priorities \n"); for(i=0;i<n;i++) { System.out.print("\nProcess["+(i+1)+"]:"); bt[i] = s.nextInt(); pp[i] = s.nextInt(); p[i]=i+1; } //sorting on the basis of priority for(i=0;i<n-1;i++) { for...
Read more

Implement UNIX system calls like ps, fork, join, exec family, and wait for process management (use shell script/ Java/ C programming).

-
//A small example to show how to use execvp() function in C. We will have two .C files , EXEC.c and execDemo.c and we will replace the execDemo.c with EXEC.c by calling execvp() function in execDemo.c . //EXEC.c  #include<stdio.h>  #include<unistd.h>  int main()   {        int i;       printf("This  is EXEC.c, called by execvp() ");        printf("\n");       return 0;   }  Now,create an executable file of EXEC.c using command  gcc EXEC.c -o EXEC //execDemo.c #include<stdio.h> #include<stdlib.h>  #include<unistd.h>  int main()  {     //A null terminated array of character      //pointers       char *args[]={"./EXEC",NULL};       execvp(args[0],args);     /*All statements are ignored after execvp() call as this whole process(execDemo.c) is replaced by ...
Read more

Implement a class CppArray which is identical to a one-dimensional C++ array (i.e., the index set is a set of consecutive integers starting at 0) except for the following : 1. It performs range checking. 2.It allows one to be assigned to another array through the use of assignment operator. 3.It supports a function that returns the size of the array.

-
#include<iostream> #include<math.h> using namespace std; class array {      int a[10],b[10],i,j,temp,n;           public:             void accept();             void display();             void range();             void sort();             void exchange();             int size(); }; void array::accept() {     cout<<"How many Elements you want to insert into the array=\n";     cin>>n;     cout<<"Enter the array Elements=\n";     for(i=0;i<n;i++)        {             cout<<...
Read more