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. }