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 Implement Find all Forward Edges in a Graph
Instance Profile Credentials using Spring Cloud
Java Program to Find kth Largest Element in a Sequence
Hướng dẫn Java Design Pattern – Visitor
Lập trình hướng đối tượng (OOPs) trong java
Java Program to Implement Knight’s Tour Problem
Java Program to Implement Insertion Sort
Converting Strings to Enums in Java
Java CyclicBarrier vs CountDownLatch
Guide to DelayQueue
Java Program to Solve any Linear Equations
Validate email address exists or not by Java Code
Java Program to Implement vector
Guava – Join and Split Collections
Java Program to add two large numbers using Linked List
Hướng dẫn Java Design Pattern – DAO
Guide to WeakHashMap in Java
Dynamic Proxies in Java
How to Remove the Last Character of a String?
REST Web service: Tạo ứng dụng Java RESTful Client với Jersey Client 2.x
Overview of Spring Boot Dev Tools
Java Program to Implement Hopcroft Algorithm
Java Program to Compute DFT Coefficients Directly
Java Program to Implement the linear congruential generator for Pseudo Random Number Generation
Handle EML file with JavaMail
Pagination and Sorting using Spring Data JPA
Java Program to Perform String Matching Using String Library
Guide to Mustache with Spring Boot
So sánh HashMap và HashSet trong Java
Exploring the Spring 5 WebFlux URL Matching
Giới thiệu về Stream API trong Java 8
Hướng dẫn Java Design Pattern – Flyweight