This is in java. When implementing quicksort, if the array contains lots of dupl

Question

This is in java.

When implementing quicksort, if the array contains lots of duplicates, it may be better to perform a three-way partition (into elements less than, equal to, and greater than the pivot), to make smaller recursive calls.

Write a program that performs a three-way in-place partition of an N-element subarray using only N 1 three-way comparisons. If there are d items equal to the pivot, you may use d additional swaps, above and beyond the two-way partitioning algorithm. (Hint: As i and j move toward each other, maintain five groups of elements as shown below):

EQUAL    SMALL    UNKNOWN    LARGE    EQUAL

                                          i                      j   

You can design the menu however you want but make sure it completes all roles above and prints the final elements in order using quick sort.

Explanation / Answer

import java.util.Scanner;

/** Class QuickSort **/
public class QuickSort
{
/** Quick Sort function **/
public static void sort(int[] arr)
{
quickSort(arr, 0, arr.length - 1);
}
/** Quick sort function **/
public static void quickSort(int arr[], int low, int high)
{
int i = low, j = high;
int temp;
int pivot = arr[(low + high) / 2];

/** partition **/
while (i <= j)
{
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j)
{
/** swap **/
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;

i++;
j--;
}
}

/** recursively sort lower half **/
if (low < j)
quickSort(arr, low, j);
/** recursively sort upper half **/
if (i < high)
quickSort(arr, i, high);
}
/** Main method **/
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
int n, i;
/** Accept number of elements **/
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/** Create array of n elements **/
int arr[] = new int[ n ];
/** Accept elements **/
System.out.println(" Enter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/** Call method sort **/
sort(arr);
/** Print sorted Array **/
System.out.println(" Elements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.