Quick Sort

二元排序

為之後搜尋準備

背景知識

雙指針
遞迴
Lomuto partition scheme(In-place)

理解問題

排序列表

思路視覺化

[10, 4, 40, 2, 3]

pivot: 3, 4, 40
left: [2], [2, 3], [2, 3,  4, 10, 40]
right:[40, 10, 4], [10, 40], []

1. Travel from left to the end, if number < right number, swap it and left number
2. Swap number of left and right
3. Recursive left and right part

Java

TC: O(nlogn): log base is 2, half each time
SC: O(n): use whole array

import java.util.*;
class QuickSort {
    private static void swap(int[] nums, int low, int high){
        int temp;
        temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
    }
    private static int partition(int[] nums, int low, int high){
        int pivot = nums[high], i = (low - 1);
        for (int j = low; j < high; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums, i, j);
            }
        }
        swap(nums, i + 1, high);
        return (i + 1);
    }
    private static void quickSort(int [] nums, int left, int right){
        if(left < right){
            int pivot = partition(nums, left, right);
            quickSort(nums, left, pivot - 1);
            quickSort(nums, pivot + 1, right);
        }
    }
    public static void main(String[] args) {
        int[] nums = { 10, 4, 40, 2, 3 };
        
        quickSort(nums, 0, nums.length - 1);
        System.out.println("Sorted array: "+ Arrays.toString(nums));
    }
}

Python

TC: O(nlogn): log base is 2, half each time
SC: O(1): in-space

def quickSort(nums, left, right):
    if left < right:
        pivot = partition(nums, left, right)
        # recursive 
        quickSort(nums, left, pivot - 1) # left part
        quickSort(nums, pivot + 1, right) # right part

def partition(nums, left, right):
    for i in range(left,len(nums)-1):
        if nums[i] < nums[right]: # right is pivot
            nums[left], nums[i] = nums[i],nums[left] # swap smaller to left 
            left += 1 # to next
    nums[left], nums[right] = nums[right], nums[left] # swap pivot
    print(nums, nums[right])
    return left

nums = [ 10, 4, 40, 2, 3 ]
print(nums)
quickSort(nums, 0, len(nums) -1)

print('Sorted Array in Ascending Order:')
print(nums)

>
[10, 4, 40, 2, 3]
[2, 3, 40, 10, 4] 4
[2, 3, 4, 10, 40] 40
[2, 3, 4, 10, 40] 40
Sorted Array in Ascending Order:
[2, 3, 4, 10, 40]

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)