This is a java program to perform sorting using Randomized Quick Sort. Randomized Quick Sort randomly selects a pivot element, after selecting pivot standard procedure is to be followed as quick sort.
Here is the source code of the Java Program to Implement Quick Sort Using Randomization. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to sort numbers using randomized quick sort import java.util.Random; public class Randomized_Quick_Sort { 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 RANDOMIZED QUICK SORT"); 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 Randomized_Quick_Sort.java $ java Randomized_Quick_Sort Sorting of randomly generated numbers using RANDOMIZED QUICK SORT Original Sequence: 98 95 22 64 77 49 11 98 56 63 84 18 9 68 4 69 2 20 68 4 Sorted Sequence: 2 4 4 9 11 18 20 22 49 56 63 64 68 68 69 77 84 95 98 98
Related posts:
Convert XML to JSON Using Jackson
The Registration API becomes RESTful
Java Program to Implement Self Balancing Binary Search Tree
Hướng dẫn Java Design Pattern – Command
Debug a JavaMail Program
Java Program to Permute All Letters of an Input String
A Quick Guide to Spring Cloud Consul
Returning Image/Media Data with Spring MVC
Từ khóa static và final trong java
Mệnh đề if-else trong java
Java Program to Implement PriorityBlockingQueue API
Guide to the ConcurrentSkipListMap
How to Use if/else Logic in Java 8 Streams
Quick Guide to Spring Controllers
Java – Write an InputStream to a File
Hướng dẫn Java Design Pattern – Abstract Factory
Java Program to Implement ConcurrentHashMap API
Spring Cloud AWS – S3
Java Program to Implement Heap Sort Using Library Functions
Java Program to Create the Prufer Code for a Tree
Spring Boot Configuration with Jasypt
Java Program to Check if it is a Sparse Matrix
Using a Mutex Object in Java
Java Program to Perform the Unique Factorization of a Given Number
The Difference Between Collection.stream().forEach() and Collection.forEach()
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
A Guide to JPA with Spring
Java Concurrency Interview Questions and Answers
Spring Boot - Servlet Filter
Hướng dẫn Java Design Pattern – Facade
Introduction to Spring Security Expressions
Merging Two Maps with Java 8