leetcode/sorting/912_sortAnArray.cpp at main · Akadil/leetcode · 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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <vector>
#include <stdlib.h>

using namespace std;

class Solution {
public:
    void    sortArray_quickSort(vector<int>& nums, int i_start, int i_end) {
        /*
            sort using quicksort
        */
        if (i_start >= i_end)
            return ;

        // Choose a random pivot position
        int randomIndex = i_start + rand() % (i_end - i_start + 1);
        // int randomIndex = chooseRandomIndex(nums, i_start, i_end);
        swap(nums, randomIndex, i_end);

        int pivot = nums[i_end];
        int i_left = i_start;

        // Partition: position lower numbers on the left side
        for (int i = i_start; i < i_end; i++) {
            if (nums[i] < pivot) {
                if (i != i_left)
                    swap(nums, i, i_left);
                i_left++;
            }
        }

        // Position the pivot position in corresponding place
        swap(nums, i_left, i_end);

        // Conquer the divided region
        sortArray_quickSort(nums, i_start, i_left - 1);
        sortArray_quickSort(nums, i_left + 1, i_end);
    }

    void    swap(vector<int>& nums, int i_one, int i_two) {
        int temp;

        temp = nums[i_one];
        nums[i_one] = nums[i_two];
        nums[i_two] = temp;
    }

    int     chooseRandomIndex(vector<int> &nums, int i_start, int i_end) {
        int index1 = i_start + rand() % (i_end - i_start + 1);
        int index2 = (i_end + i_start) / 2;

        int lowestIndex = index1;

        // Compare the values at index2, index3, and index4
        if (nums[index2] < nums[lowestIndex]) {
            lowestIndex = index2;
        }
        if (nums[i_start] < nums[lowestIndex]) {
            lowestIndex = i_start;
        }
        if (nums[i_end] < nums[lowestIndex]) {
            lowestIndex = i_end;
        }
        return(lowestIndex);
    }
    // vector<int> sortArray_insertion(vector<int>& nums) {
    //     for (int i = 1; i < nums.size(); ++i) {
    //         int j = i;
    //         while (j != 0 && nums[j - 1] > nums[j]) {
    //             int temp = nums[j];

    //             nums[j] = nums[j - 1];
    //             nums[j - 1] = temp;
    //             j--;
    //         }
    //     }
    //     return (nums);
    // }

    // void    sortArray_merge(vector<int>& nums, int i_begin, int i_middle, int i_end) {
    //     vector<int> array_left(nums.begin() + i_begin, nums.begin() + i_middle + 1);
    //     vector<int> array_right(nums.begin() + i_middle + 1, nums.begin() + i_end + 1);

    //     int j_left = 0;
    //     int j_right = 0;
    //     int k = i_begin;

    //     while (j_left != array_left.size() && j_right != array_right.size()) {
    //         if (array_left[j_left] < array_right[j_right])
    //             nums[k++] = array_left[j_left++];
    //         else
    //             nums[k++] = array_right[j_right++];
    //     }

    //     while (j_left != array_left.size())
    //         nums[k++] = array_left[j_left++];
    //     while (j_right != array_right.size())
    //         nums[k++] = array_right[j_right++];
    // }

    // void sortArray_mergeSort(vector<int>& nums, int i_begin, int i_end) {
    //     if (i_begin == i_end)
    //         return ;

    //     int i_middle = (i_end - i_begin) / 2 + i_begin;

    //     sortArray_mergeSort(nums, i_begin, i_middle);
    //     sortArray_mergeSort(nums, i_middle + 1, i_end);
    //     sortArray_merge(nums, i_begin, i_middle, i_end);
    //     return ;
    // }

    vector<int> sortArray(vector<int>& nums) {
        // sortArray_insertion(nums);
        // sortArray_mergeSort(nums, 0, nums.size() -1);
        sortArray_quickSort(nums, 0, nums.size() - 1);
        return (nums);
    }
};