Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <utility>
- void PrintArr(const std::vector<int>& arr, bool isBreakLine = true)
- {
- for (const auto& i : arr)
- {
- std::cout << i << " ";
- }
- if (isBreakLine)
- std::cout << "\n";
- }
- void Swap(int* num1, int* num2)
- {
- int tmp = *num1;
- *num1 = *num2;
- *num2 = tmp;
- }
- // Dutch Flag Algorithm
- void SortThreeType(std::vector<int>& unsorted_arr)
- {
- int low = 0, mid = 0;
- int high = unsorted_arr.size() - 1;
- while(mid <= high)
- {
- if (unsorted_arr[mid] == 0)
- {
- Swap(&unsorted_arr[low], &unsorted_arr[mid]);
- low++;
- mid++;
- }
- else if(unsorted_arr[mid] == 1)
- {
- mid++;
- }
- else
- {
- Swap(&unsorted_arr[mid], &unsorted_arr[high]);
- high--;
- }
- }
- }
- // Partition Around Range
- void PartitionAroundRange(std::vector<int>& unsorted_arr, const std::pair<int, int>& range)
- {
- int first = range.first;
- int last = range.second;
- int low = 0, mid = 0;
- int high = unsorted_arr.size() - 1;
- while (mid <= high)
- {
- if (unsorted_arr[mid] < first)
- {
- Swap(&unsorted_arr[low], &unsorted_arr[mid]);
- low++;
- mid++;
- }
- else if (unsorted_arr[mid] >= 5 && unsorted_arr[mid] <= 10)
- {
- mid++;
- }
- else
- {
- Swap(&unsorted_arr[mid], &unsorted_arr[high]);
- high--;
- }
- }
- }
- int main()
- {
- std::vector<int> unsorted_arr = {0, 1, 2, 0, 1, 2};
- SortThreeType(unsorted_arr);
- PrintArr(unsorted_arr);
- std::vector<int> unsorted_arr1 = {10, 5, 6, 3, 20, 9, 40};
- std::pair<int, int> range{5, 10};
- PartitionAroundRange(unsorted_arr1, range);
- PrintArr(unsorted_arr1);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement