Advertisement
uopspop

Untitled

Jan 28th, 2022
732
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.BT_QuickSort;
  2.  
  3.  
  4. public class QuickSort {
  5.  
  6.     public static void quick_sort(int[] nums){
  7.         quick_sort(nums, 0, nums.length - 1);
  8.     }
  9.  
  10.     /**
  11.      * Quick Sort is very much liks BST's Pre-order traversal !
  12.      */
  13.     public static void quick_sort(int[] nums, int left_i, int right_i){
  14.         /** end condition - one-element array is sorted already **/
  15.         if (left_i == right_i) return; // one element means sorted already
  16.         if (left_i > right_i) return; // out of boundary sub-array
  17.  
  18.         /** main logic - conquer - pick pivot **/
  19.         int pivot_i_guess = pick_pivot_index(nums, left_i, right_i);
  20.  
  21.         /** main logic - conquer - sort the current array chunk - pivot index would be moved around here **/
  22.         int pivot_i_final = sort(nums, left_i, pivot_i_guess, right_i);
  23.  
  24.         /** data flow - divide **/
  25.         quick_sort(nums, left_i, pivot_i_final-1);
  26.         quick_sort(nums, pivot_i_final+1, right_i);
  27.  
  28.     }
  29.  
  30.     public static int sort(int[] nums, int start_i, int pivot_i_guess, int end_i) {
  31.  
  32.         /** goal: use existing space only ! **/
  33.         int pivot_i_now = pivot_i_guess;
  34.  
  35.         /** step01: swap pivot value to the last element **/
  36.         /** purpose: 讓左側部分先整理好 (最後再將pivot element放到適當位置) **/
  37.         swap(nums, pivot_i_now, end_i); // swap value
  38.         pivot_i_now = end_i; // update index
  39.  
  40.         /** step02: sort the rest of the array **/
  41.         int left_i = start_i;
  42.         int right_i = end_i - 1; // exclude pivot from the following process
  43.         while (true) {
  44.  
  45.             while (true) {
  46.                 if (left_i == right_i) break;                    /** end condition **/
  47.                 if (nums[left_i] > nums[pivot_i_now]) break;     /** main logic - 找出不應該出現在「左」側的數 **/
  48.                 left_i++;                                        /** next step **/
  49.             }
  50.  
  51.             while (true) {
  52.                 if (left_i == right_i) break;                    /** end condition **/
  53.                 if (nums[right_i] < nums[pivot_i_now]) break;    /** main logic - 找出不應該出現在「右」側的數 **/
  54.                 right_i--;                                       /** next step **/
  55.             }
  56.  
  57.             if (left_i == right_i) break;                         /** end condition **/
  58.  
  59.             swap(nums, left_i, right_i);                          /** main logic - swap **/
  60.  
  61.         }
  62.  
  63.         /** step03: put pivot element to the right place **/
  64.         int meeting_point_i = left_i; // or meeting_point_i = right_i
  65.         if (nums[meeting_point_i] >= nums[pivot_i_now]) {
  66.             swap(nums, pivot_i_now, meeting_point_i);
  67.             pivot_i_now = meeting_point_i;
  68.         }
  69.  
  70.         return pivot_i_now;
  71.     }
  72.  
  73.     private static void swap(int[] nums, int left_i, int right_i) {
  74.         int tmp = nums[left_i];
  75.         nums[left_i] = nums[right_i];
  76.         nums[right_i] = tmp;
  77.     }
  78.  
  79.     public static int pick_pivot_index(int[] nums, int left_i, int right_i) {
  80.         int result = (left_i+right_i)/2;
  81.         return result;
  82.     }
  83.  
  84.  
  85.  
  86.     public static void main(String[] args) {
  87. //        int[] ary = {5,4,3,2,1};
  88. //        int[] ary = {7,6,5,4,3,2,1};
  89. //        int[] ary = {1,2,3,4,5};
  90. //        int[] ary = {5,4,3,3,3};
  91. //        int[] ary = {3,3,3,2,1};
  92. //        int[] ary = {24,2,45,20,56,75,2,56,99,53,12};
  93.         int[] ary = {20,10,50,30,70,60,40};
  94.         QuickSort.quick_sort(ary);
  95.         System.out.println();
  96.     }
  97.    
  98. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement