JAVA class QuickSort> implements Sorter { private E[] array; private void swap (

Question

JAVA

class QuickSort>

implements Sorter {

private E[] array;

private void swap (int i, int j) {

E data = array[i];

array[i] = array[j];

array[j] = data;

}

public void sort (E[] array) {

this.array = array;

sort(0, array.length-1);

}

private void sort(int left, int right) {

if (left >= right)

return;

swap(left, (left + right) / 2);

E pivot = array[left];

int a = left + 1;

int b = right;

while (a <= b) {

// Move a forward if array[a] <= pivot

// Move b backward if array[b] > pivot

// Otherwise swap array[a] and array[b]

}

swap(left, b);

sort(left, b-1);

sort(b+1, right);

}

}

Explanation / Answer

Here is solution. If this doesn't match your requirement then please lay your requirement clearly

QuickSort.java

class QuickSort<E extends Comparable> {

private E[] array;

private void swap(int i, int j) {
E data = array[i];
array[i] = array[j];
array[j] = data;
}

public void sort(E[] array) {
if (array == null || array.length == 0) {
return;
}
  
this.array = array;
sort(0, array.length - 1);
}

@SuppressWarnings("unchecked")
private void sort(int left, int right) {
E pivot = array[(left + right) / 2];
int a = left;
int b = right;
while (a <= b) {
// Move a forward if array[a] <= pivot
// Move b backward if array[b] > pivot
// Otherwise swap array[a] and array[b]
while(array[a].compareTo(pivot) < 0)
{
a++;
}
while(array[b].compareTo(pivot) > 0)
{
b--;
}
if (a <= b) {
swap(a, b);
a++;
b--;
}
}

if (left < b)
sort(left, b);
if (a < right)
sort(a, right);
}
}

Testing it using following class

QuickSortTest.java

import java.util.Random;

public class QuickSortTest {

public static void main(String[] args)
{
Random rn = new Random();
  
QuickSort<Integer> q = new QuickSort<>();
Integer[] arr = new Integer[10];
  
for(int i = 0; i < 10; i++)
{
arr[i] = rn.nextInt() % 100;
}
  
System.out.println("Array before sorting");
for(int i = 0; i < 10; i++)
{
System.out.print(arr[i] + " ");
}
  
System.out.println();
  
q.sort(arr);
  
System.out.println("Array after sorting");
for(int i = 0; i < 10; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
}

Sample run

Array before sorting
-40 7 -42 -92 60 -9 15 98 -79 -63
Array after sorting
-92 -79 -63 -42 -40 -9 7 15 60 98

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

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