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.
package com.sanfoundry.combinatorial; import java.util.Random; public class QuickSortComplexityConstraint { public static int N = 20; public static int[] sequence = new int[N]; public static void QuickSort(int left, int right) { if (right - left <= 0) return; else { Random rand = new Random(); int pivotIndex = left + rand.nextInt(right - left + 1); swap(pivotIndex, right); int pivot = sequence[right]; int partition = partitionIt(left, right, pivot); QuickSort(left, partition - 1); QuickSort(partition + 1, right); } } public static int partitionIt(int left, int right, long pivot) { int leftPtr = left - 1; int rightPtr = right; while (true) { while (sequence[++leftPtr] < pivot) ; while (rightPtr > 0 && sequence[--rightPtr] > pivot) ; if (leftPtr >= rightPtr) break; else swap(leftPtr, rightPtr); } swap(leftPtr, right); return leftPtr; } public static void swap(int dex1, int dex2) { int temp = sequence[dex1]; sequence[dex1] = sequence[dex2]; sequence[dex2] = temp; } static void printSequence(int[] sorted_sequence) { for (int i = 0; i < sorted_sequence.length; i++) System.out.print(sorted_sequence[i] + " "); } public static void main(String args[]) { System.out .println("Sorting of randomly generated numbers using QUICK SORT with complexity less than n^2"); Random random = new Random(); for (int i = 0; i < N; i++) sequence[i] = Math.abs(random.nextInt(100)); System.out.println("\nOriginal Sequence: "); printSequence(sequence); System.out.println("\nSorted Sequence: "); QuickSort(0, N - 1); printSequence(sequence); } }
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
Related posts:
@DynamicUpdate with Spring Data JPA
Java Program to Find the Edge Connectivity of a Graph
Hướng dẫn Java Design Pattern – Template Method
How to Implement Caching using Adonis.js 5
Vector trong Java
Guide to CountDownLatch in Java
Java Program to Implement Sorted Doubly Linked List
Spring Security Form Login
The Basics of Java Security
Java Program to Implement Ternary Search Tree
Java Program to Create a Random Graph Using Random Edge Generation
Java Program to Check Whether Graph is DAG
Java Program to Implement AVL Tree
A Guide to Concurrent Queues in Java
Java Program to Generate Random Hexadecimal Byte
Java Program to Optimize Wire Length in Electrical Circuit
Java Program to Print only Odd Numbered Levels of a Tree
Java Program to Represent Graph Using 2D Arrays
Introduction to Spliterator in Java
Java – Delete a File
Vòng lặp for, while, do-while trong Java
Java Program to Implement Treap
Migrating from JUnit 4 to JUnit 5
Guide to Java 8’s Collectors
Spring Security 5 for Reactive Applications
Copy a List to Another List in Java
Sorting Query Results with Spring Data
Java Program to Represent Graph Using Adjacency List
Java Program to Test Using DFS Whether a Directed Graph is Weakly Connected or Not
Java Program to Implement Efficient O(log n) Fibonacci generator
Introduction to Spring Boot CLI
Working with Tree Model Nodes in Jackson