Sorting Objects with the Quicksort Algorithm The IntQuickSorter class presented

Question

Sorting Objects with the Quicksort Algorithm The IntQuickSorter class presented in this chapter sorts an array of int values. Create an ObjectQuickSorter class that can sort Comparable objects. Demonstrate the class in a program that sorts an array of String objects. (java)

intquicksorter class in java

public class quicksort
{
public static void quickSort(int[] arr)
{
     doQuickSort(arr,0,arr.length-1);
}

private static void doQuickSort(int a[], int start, int end)
{
      int pivot;

     if(start < end)
     {
       pivot = partition(a,start,end);

       doQuickSort(a,start,pivot - 1);

       doQuickSort(a, pivot + 1, end);
     }
}

private static int partition(int ar[], int start, int end)
{
     int pivotval,endoflist,mid;

     mid = (start + end) / 2;

    swap(ar,start,mid);

    pivotval = ar[start];

    endoflist = start;

   for(int i = start + 1; i <= end; i++)
   {
       if(ar[i] < pivotval)
       {
          endoflist++;
          swap(ar,endoflist,i);
       }
   }

    swap(ar,start,endoflist);

    return endoflist;
}

   private static void swap(int[] array, int a, int b)
   {
      int temp;
      temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

}

Explanation / Answer

import java.util.List;
import java.lang.Math;
public class QuickSort
{

private int array[];
private int length;

public void sort(int[] arr)

{
if (arr == null || arr.length == 0)
{
return;
}
this.array = arr;
length = arr.length;
partition(0, length - 1);
}

private void partition(int start, int end)
{

int i = start;
int j = end;
int pivot = array[start+(end-start)/2];
  
while (i <= j) {
  
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swap(i, j);
  
i++;
j--;
}
}
  
if (start < j)
partition(start, j);
if (i < end)
partition(i, end);
}

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

public static void main(String a[]){

QuickSort sorter = new QuickSort();
int[] input = {32,5,46,10,36,78,9,46,99,13,12};
sorter.sort(input);
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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