AlgorithmCode/sort_again.cpp at master · ZMK112/AlgorithmCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <vector>
using namespace std;

// void quickSort(int* nums, int left, int right)
// {
//     if (left < right)
//     {
//         int i = left, j = right;
//         int x = nums[left];

//         while (i < j)
//         {
//             while (i < j && nums[j] >= x){
//                 j--;
//             }
//             if (i < j){
//                 nums[i++] = nums[j];
//             }
//             while (i < j && nums[i] <= x){
//                 i++;
//             }
//             if (i < j){
//                 nums[j--] = nums[i];
//             }
//         }
//         nums[i] = x;
//         quickSort(nums, left, i - 1);
//         quickSort(nums, i + 1, right);
//     }
// }

int partition(vector<int>& nums, int left, int right)
{
        int i = left, j = right;
        int x = nums[left];

        while (i < j)
        {
            while (i < j && nums[j] >= x){
                j--;
            }
            if (i < j){
                nums[i++] = nums[j];
            }
            while (i < j && nums[i] <= x){
                i++;
            }
            if (i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = x;
        return i;
}

int partition_two(vector<int>& nums, int left, int right)
{
    int pivot = nums[left];
    int i = left + 1, j = right;
    while (i < j)
    {
        while(i < j && nums[i] <= pivot) i++;
        while(i < j && nums[j] >= pivot) j--;
        if (i < j){
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i], nums[left]);
    return i;
}

vector<int> quickSort(vector<int>& nums, int left, int right)
{
    if (left < right)
    {
        int i = partition_two(nums, left, right);
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
}

 vector<int> sortArray(vector<int>& nums) {
     int i = 0, j = nums.size() - 1;
     quickSort(nums, i, j);
     return nums;
}

int main()
{
    vector<int> num = {72,6,57,88,60,42,83,73,48,85};
    int nums[10] = {72,6,57,88,60,42,83,73,48,85};
    quickSort(num, 0, 9);
    return 0;

}