Java Program to Implement Quick Sort with Given Complexity Constraint

This is a java program to perform quick sort with complexity constraint of time less than n^2.

Here is the source code of the Java Program to Implement Quick Sort with Given Complexity Constraint. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1.  
  2. package com.sanfoundry.combinatorial;
  3.  
  4. import java.util.Random;
  5.  
  6. public class QuickSortComplexityConstraint
  7. {
  8.     public static int N = 20;
  9.     public static int[] sequence = new int[N];
  10.  
  11.     public static void QuickSort(int left, int right)
  12.     {
  13.         if (right - left <= 0)
  14.             return;
  15.         else
  16.         {
  17.             Random rand = new Random();
  18.             int pivotIndex = left + rand.nextInt(right - left + 1);
  19.             swap(pivotIndex, right);
  20.             int pivot = sequence[right];
  21.             int partition = partitionIt(left, right, pivot);
  22.             QuickSort(left, partition - 1);
  23.             QuickSort(partition + 1, right);
  24.         }
  25.     }
  26.  
  27.     public static int partitionIt(int left, int right, long pivot)
  28.     {
  29.         int leftPtr = left - 1;
  30.         int rightPtr = right;
  31.         while (true)
  32.         {
  33.             while (sequence[++leftPtr] < pivot)
  34.                 ;
  35.             while (rightPtr > 0 && sequence[--rightPtr] > pivot)
  36.                 ;
  37.             if (leftPtr >= rightPtr)
  38.                 break;
  39.             else
  40.                 swap(leftPtr, rightPtr);
  41.         }
  42.         swap(leftPtr, right);
  43.         return leftPtr;
  44.     }
  45.  
  46.     public static void swap(int dex1, int dex2)
  47.     {
  48.         int temp = sequence[dex1];
  49.         sequence[dex1] = sequence[dex2];
  50.         sequence[dex2] = temp;
  51.     }
  52.  
  53.     static void printSequence(int[] sorted_sequence)
  54.     {
  55.         for (int i = 0; i < sorted_sequence.length; i++)
  56.             System.out.print(sorted_sequence[i] + " ");
  57.     }
  58.  
  59.     public static void main(String args[])
  60.     {
  61.         System.out
  62.                 .println("Sorting of randomly generated numbers using QUICK SORT with complexity less than n^2");
  63.         Random random = new Random();
  64.         for (int i = 0; i < N; i++)
  65.             sequence[i] = Math.abs(random.nextInt(100));
  66.         System.out.println("\nOriginal Sequence: ");
  67.         printSequence(sequence);
  68.         System.out.println("\nSorted Sequence: ");
  69.         QuickSort(0, N - 1);
  70.         printSequence(sequence);
  71.     }
  72. }

Output:

$ javac QuickSortComplexityConstraint.java
$ java QuickSortComplexityConstraint
 
Sorting of randomly generated numbers using QUICK SORT with complexity less than n^2
 
Original Sequence: 
29 19 67 48 23 99 72 40 23 93 0 79 70 87 43 24 56 67 51 71 
Sorted Sequence: 
0 19 23 23 24 29 40 43 48 51 56 67 67 70 71 72 79 87 93 99

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.