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 pritns the final elements in order using quick sort.

Explanation / Answer

Answer for above question,example may be deferent you can give same code for string instead of integer,java code for Quicksorting with pivoting is given bellow:

class MySort
{
int division(int arr[], int low, int high)
{
int pvt = arr[high];
int i = (low-1);
for (int j=low; j<=high-1; j++)
{
if (arr[j] <= pvt)
{
i++;

int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
int tmp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = tmp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
int pi = division(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

static void showArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {100, 70, 80, 90, 10, 50};
int n = arr.length;
MySort ob = new MySort();
ob.sort(arr, 0, n-1);
System.out.println("Desired sorted array");
showArray(arr);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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