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 Check whether Graph is a Bipartite using DFS
Spring Boot - Thymeleaf
Performance Difference Between save() and saveAll() in Spring Data
Hướng dẫn tạo và sử dụng ThreadPool trong Java
Checking for Empty or Blank Strings in Java
Spring’s RequestBody and ResponseBody Annotations
Java program to Implement Tree Set
Lập trình đa luồng với CompletableFuture trong Java 8
Java Program to Implement the Bin Packing Algorithm
The HttpMediaTypeNotAcceptableException in Spring MVC
Java Program to Find Location of a Point Placed in Three Dimensions Using K-D Trees
Java Program to Describe the Representation of Graph using Adjacency List
Debug a HttpURLConnection problem
Java Program to Implement Sorted Circular Doubly Linked List
Creating a Web Application with Spring 5
Spring MVC and the @ModelAttribute Annotation
Getting a File’s Mime Type in Java
Stack Memory and Heap Space in Java
Java – Write a Reader to File
Java Timer
Java Program to Find Nearest Neighbor for Dynamic Data Set
Convert Character Array to String in Java
Converting Between an Array and a Set in Java
Java Deep Learning Essentials - Yusuke Sugomori
Introduction to Spring Data JPA
Spring Boot: Customize Whitelabel Error Page
Spring Data JPA @Modifying Annotation
Sorting Query Results with Spring Data
Guide to java.util.concurrent.Locks
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Java Streams vs Vavr Streams
Java Program to Compute Discrete Fourier Transform Using Naive Approach