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:
Using a Mutex Object in Java
Java Program to Implement Bit Array
The HttpMediaTypeNotAcceptableException in Spring MVC
Sort a HashMap in Java
Immutable ArrayList in Java
Java Program to Implement Flood Fill Algorithm
Java Program to Generate All Possible Combinations Out of a, b, c, d, e
Spring @RequestMapping New Shortcut Annotations
Java Program to Check whether Directed Graph is Connected using DFS
Hướng dẫn sử dụng luồng vào ra nhị phân trong Java
Java Program to Implement Euclid GCD Algorithm
Zipping Collections in Java
Practical Java Examples of the Big O Notation
OAuth2 for a Spring REST API – Handle the Refresh Token in AngularJS
Introduction to Eclipse Collections
Truyền giá trị và tham chiếu trong java
Extract links from an HTML page
Abstract class và Interface trong Java
Quick Guide to @RestClientTest in Spring Boot
Java Program to Implement Gaussian Elimination Algorithm
@Lookup Annotation in Spring
Java Program to Implement RoleUnresolvedList API
Giới thiệu Swagger – Công cụ document cho RESTfull APIs
Spring Cloud Series – The Gateway Pattern
Configuring a DataSource Programmatically in Spring Boot
A Guide to TreeMap in Java
Java Program to Implement Kosaraju Algorithm
Logging a Reactive Sequence
Java Program to Implement HashTable API
Java Program to Find the Longest Path in a DAG
Find the Registered Spring Security Filters
A Quick Guide to Spring Cloud Consul