Guest User

Untitled

a guest
Oct 10th, 2018
86
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class QuicksortOnly {
  2.  
  3.     /**
  4.      * @param args the command line arguments
  5.      */
  6.     public static void main(String[] args) {
  7.        
  8.         int[] arr = {45, 21, 44, 60, 32, 21, 0};
  9.        
  10.         sort(arr);
  11.        
  12.         for(int print: arr){
  13.            
  14.             System.out.print(print + " ");
  15.            
  16.                            }
  17.        
  18.     }
  19.    
  20.    
  21.     public static void sort(int[] arr){
  22.        
  23.        
  24.         quicksort(arr, 0, arr.length - 1);
  25.                                       }
  26.    
  27.    
  28.     public static void quicksort(int[] arr, int start, int end){
  29.        
  30.         if(end - start > 0){
  31.            
  32.             int p = partition(arr, start, end);
  33.             quicksort(arr, start, p - 1);
  34.             quicksort(arr, p + 1, end);
  35.            
  36.            
  37.                            }
  38.        
  39.        
  40.                                                                }
  41.    
  42.  
  43. public static int partition(int[] arr, int start, int end){
  44.  
  45.     int pivot = choosePivot(start, end);
  46.    
  47.     swap(arr, pivot, end);
  48.    
  49.     int high_border = end - 1;//suspiscious when sorting the right side of the array.
  50.     int low_border = start;
  51.    
  52.     while(low_border < high_border){
  53.        
  54.         if(arr[low_border] > arr[end] && arr[high_border] < arr[end]){
  55.            
  56.             swap(arr, low_border, high_border);
  57.             low_border++;
  58.             high_border--;
  59.            
  60.            
  61.                                                                      }
  62.        
  63.         else if(arr[low_border] > arr[end]){
  64.            
  65.             high_border--;
  66.  
  67.                                            }
  68.        
  69.         else if(arr[high_border] < arr[end]){
  70.            
  71.             low_border++;
  72.  
  73.                                             }
  74.        
  75.         else{
  76.            
  77.            
  78.             if(low_border != high_border){
  79.             low_border++;
  80.             high_border--;
  81.                                          }
  82.            
  83.             }
  84.        
  85.        
  86.        
  87.        
  88.                                    }
  89.     if(high_border < low_border){
  90.     swap(arr, low_border, end);
  91.                                 }
  92.    
  93.     else if(high_border == low_border){
  94.        
  95.         if(arr[low_border] > arr[end]){
  96.            
  97.             swap(arr, low_border, end);
  98.                                       }
  99.        
  100.                                       }
  101.    
  102.     return low_border;
  103.    
  104.    
  105.                                                           }
  106.  
  107.  
  108. //Randomly selects a pivot point between start and end.
  109. public static int choosePivot(int start, int end){
  110.  
  111.     Random gen = new Random();
  112.    
  113.     return gen.nextInt((end - start) + 1) + start;
  114.    
  115.  
  116.                                                  }
  117.  
  118. public static void swap(int[] arr, int ind1, int ind2){
  119.    
  120.     int temp = arr[ind1];
  121.    
  122.     arr[ind1] = arr[ind2];
  123.    
  124.     arr[ind2] = temp;
  125. }
  126.  
  127.  
  128. }
RAW Paste Data