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:
Java Program to Optimize Wire Length in Electrical Circuit
Spring Boot - Building RESTful Web Services
Deque và ArrayDeque trong Java
The Registration API becomes RESTful
Stack Memory and Heap Space in Java
Period and Duration in Java
Introduction to Spring MVC HandlerInterceptor
Java Program to Implement Shoelace Algorithm
Ép kiểu trong Java (Type casting)
Handling Errors in Spring WebFlux
Giới thiệu Aspect Oriented Programming (AOP)
Java Program to Find Nearest Neighbor for Static Data Set
Debug a HttpURLConnection problem
Java Program to Solve Knapsack Problem Using Dynamic Programming
The DAO with Spring and Hibernate
Java Program to Solve Travelling Salesman Problem for Unweighted Graph
Class Loaders in Java
How to Read a Large File Efficiently with Java
Vấn đề Nhà sản xuất (Producer) – Người tiêu dùng (Consumer) và đồng bộ hóa các luồng trong Java
Lập trình mạng với java
Java Program to implement Bit Set
Java Program to Implement AA Tree
Hướng dẫn Java Design Pattern – Factory Method
Java Program to Implement Bloom Filter
Java Program to Implement Weight Balanced Tree
Spring MVC and the @ModelAttribute Annotation
Java equals() and hashCode() Contracts
Java Program to Check Whether a Directed Graph Contains a Eulerian Path
Spring Boot - Cloud Configuration Server
Practical Java Examples of the Big O Notation
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Java Program to Implement Ternary Search Tree