Algorithms

[Python] Quick sort

Algorithms、Python / 2022 年 4 月 11 日
def quick_sort(nums, left=None, right=None):
    def _partition(nums, left, right, pivot_idx):
        pivot = nums[pivot_idx]
        nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
        tmp_idx = left
        for idx in range(left, right):
            if nums[idx] <= pivot:
                nums[tmp_idx], nums[idx] = nums[idx], nums[tmp_idx]
                tmp_idx += 1
        nums[tmp_idx], nums[right] = nums[right], nums[tmp_idx]
        return tmp_idx

    if left is None:
        left = 0
    if right is None:
        right = len(nums)-1
    if left >= right:
        return

    new_pivot_idx = _partition(nums, left, right, left)
    quick_sort(nums, left, new_pivot_idx-1)
    quick_sort(nums, new_pivot_idx+1, right)


# inputs = input()
# inputs = [int(c) for c in inputs.split()]
inputs = [3, 5, 1, 2, 6, 4, 7]
quick_sort(inputs)
print(inputs)

[C++] Permutation

Algorithms、C++ / 2016 年 9 月 5 日
  • Rotate example: [ 1 2 3 4]-> 4 1 2 3 (right shift)
  • Permutation of 1 2 3 4: [] = rotate, () = recursion
    • [1] => 1 (2 3 4)
    • [1 2] => 2 (1 3 4)
    • [1 2 3] => 3 (1 2 4)
    • [1 2 3 4] => 4 (1 2 3)

  • Code
#include<iostream>
#include<vector>
using namespace std;

int count = 0;

void rotate(vector<int> &list, int x, int y) {
    int tmp = list[y];
    for (int i = y; i > x; i--) {
        list[i] = list[i-1];
    }
    list[x] = tmp;
}

void perm(int a, int n, vector<int> list){
    if (a < n){
        for (int i = a; i < n; i++) {
            vector<int> tmplist(list);
            rotate(tmplist, a, i);
            perm(a+1, n, tmplist);
        }
    }
    else{
        for (int i = 0; i < n; i++) {
            cout<<list[i]<<" ";
        }
        cout<<endl;
        count++;
    }
}

int main()
{
    int n;
    vector<int> list;
    cin>>n;
    list.resize(n);
    for (int i = 0;i < n; i++) {
        cin>>list[i];
    }
    perm(0, n, list);
    cout<<"count="<<count<<endl;
    return 0;
}