jTruBela

MyQuickSort

Dec 4th, 2021
975
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package testSpace;
  2.  
  3. public class QuickSort {
  4.  
  5.    
  6. public static int[] quick_sort (int[] array, int startIndex, int endIndex) {
  7.        
  8.     if (startIndex < endIndex) {
  9.         print("Starting array:",array);
  10.         //print_array(array);
  11.         print("\nGathering smaller number partition");
  12.         int q = partition(array,startIndex,endIndex);
  13.         quick_sort(array,startIndex,q-1);
  14.         quick_sort(array,q+1,endIndex);
  15.     }
  16.  
  17.     return array;
  18.    
  19.     }
  20.    
  21. public static int partition(int array[], int startIndex, int endIndex) {       
  22.     int pivot = array[endIndex];    //set pivot
  23.     int i = startIndex-1;           //set i to lowest index - 1
  24.                                
  25.     System.out.print("Partition array considered:");
  26.     int tempArray[] = new int[endIndex];
  27.     for (int i1=startIndex; i1<endIndex; i1++) {
  28.         tempArray[i1] = array[i1];
  29.     }
  30.    
  31.     print_array(tempArray);
  32.    
  33.     print(array[endIndex]);
  34.    
  35.     print("\nChoosing Pivot("+pivot+")");
  36.  
  37.     print_array(array);
  38.     //*************************************************************
  39.     //
  40.     //for each iteration through sub array
  41.     //swap values less than or equal to pivot
  42.     //
  43.     //*************************************************************
  44.  
  45.     for (int j=startIndex; j<endIndex; j++) {
  46.         print("\n---------------------------------------"
  47.                 +"\n\nfinding values <= to current pivot");
  48.  
  49.         if (array[j]<=pivot) {
  50.             print("value(" + array[j] + ") <= pivot(" + pivot + ") was found "
  51.                     + "\n~adding to smaller partition~\nBefore:");
  52.             print_array(array);
  53.  
  54.             i++;
  55.             //*************************************************************
  56.             //
  57.             //exchange smaller values to subarray
  58.             //
  59.             //*************************************************************
  60.            
  61.             System.out.print("(exchanging "+array[i]+ "->" +array[j]+")");
  62.             int temp = array[i];       
  63.             array[i] = array[j];
  64.             array[j] = temp;
  65.            
  66.             print("\nAfter:");
  67.             print_array(array);
  68.         }
  69.  
  70.     }
  71.     //*************************************************************
  72.    
  73.     //exchange pivot into correct place between subarrays
  74.    
  75.     //*************************************************************
  76.  
  77.     print("\n\n***************************************"
  78.          +"\nPartition complete\nExchanging/Placing Pivot("+pivot+")->" + array[i+1]
  79.          +"\n***************************************");
  80.  
  81.    
  82.     int temp = array[i+1];
  83.     array[i+1] = array[endIndex];
  84.     array[endIndex] = temp;
  85.    
  86.     return i+1;
  87. }
  88.    
  89.  
  90.     public static void print_array (int[] array) {
  91.         System.out.print("A: ");
  92.         for (int i = 0; i < array.length; i++)
  93.             System.out.print(array[i] + ", ");
  94.     }
  95.     public static void print(String string) {
  96.         System.out.print(string+ "\n");
  97.     }
  98.     public static void print(int integer) {
  99.         System.out.println("" + integer);
  100.     }
  101.     public static void print(String string, int[] array) {
  102.         string = "A: ";
  103.         System.out.println(string);
  104.         for (int i=0; i<array.length;i++) {
  105.             System.out.print(array[i] + ", ");
  106.         }
  107.     }
  108.    
  109.     public static void main(String[] args) {
  110.         // TODO Auto-generated method stub
  111.         int[] array = {2,8,7,1,3,5,6,4};
  112.         array = quick_sort(array, 0, array.length-1);
  113.         print_array(array);
  114.         print("\n\nArray is sorted\n");
  115.  
  116.     }
  117. }
RAW Paste Data