1b IMPLEMENTATION OF QUICK SORT

1b. IMPLEMENTATION OF QUICK  SORT

          

          AIM:

     To write a java program to implement quick sort.

ALGORTIHM:

1. Choose an element, called pivot, from the list. Generally pivot can be the middle index element

        2. Reorder the list so that all elements with values less than the pivot come before the pivot

       3. 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.

4. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

5. Stop the Program.

PROGRAM:

 

import java.util.Scanner;

public class MergeSort

{

public static void sort(int[] a, int low, int high)

{

int N = high - low;

if (N <= 1)

return;

int mid = low + N/2;

sort(a, low, mid);

sort(a, mid, high);

int[] temp = new int[N];

int i = low, j = mid;

for (int k = 0; k < N; k++)

{

if (i == mid)

temp[k] = a[j++];

else if (j == high)

temp[k] = a[i++];

else if (a[j]<a[i])

temp[k] = a[j++];

else

temp[k] = a[i++];

}

for (int k = 0; k < N; k++)

a[low + k] = temp[k];

}

public static void main(String[] args)

{

Scanner scan = new Scanner( System.in );

System.out.println("Merge Sort Test\n");

int n, i;

System.out.println("Enter number of integer elements");

n = scan.nextInt();

int arr[] = new int[ n ];

System.out.println("\nEnter "+ n +" integer elements");

for (i = 0; i < n; i++)

arr[i] = scan.nextInt();

sort(arr, 0, n);

System.out.println("\nElements after sorting ");

for (i = 0; i < n; i++)

System.out.print(arr[i]+" ");

System.out.println();

}

}