Advertisement
zozohoang

Dutch National Flag Algorithm

Mar 19th, 2025
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <utility>
  4.  
  5. void PrintArr(const std::vector<int>& arr, bool isBreakLine = true)
  6. {
  7.     for (const auto& i : arr)
  8.     {
  9.         std::cout << i << " ";
  10.     }
  11.    
  12.     if (isBreakLine)
  13.         std::cout << "\n";
  14. }
  15.  
  16. void Swap(int* num1, int* num2)
  17. {
  18.     int tmp = *num1;
  19.     *num1 = *num2;
  20.     *num2 = tmp;
  21. }
  22.  
  23. // Dutch Flag Algorithm
  24. void SortThreeType(std::vector<int>& unsorted_arr)
  25. {
  26.     int low = 0, mid = 0;
  27.     int high = unsorted_arr.size() - 1;
  28.    
  29.     while(mid <= high)
  30.     {
  31.         if (unsorted_arr[mid] == 0)
  32.         {
  33.             Swap(&unsorted_arr[low], &unsorted_arr[mid]);
  34.             low++;
  35.             mid++;
  36.         }
  37.         else if(unsorted_arr[mid] == 1)
  38.         {
  39.             mid++;
  40.         }
  41.         else
  42.         {
  43.             Swap(&unsorted_arr[mid], &unsorted_arr[high]);
  44.             high--;
  45.         }
  46.     }
  47. }
  48.  
  49. // Partition Around Range
  50. void PartitionAroundRange(std::vector<int>& unsorted_arr, const std::pair<int, int>& range)
  51. {
  52.     int first = range.first;
  53.     int last = range.second;
  54.    
  55.     int low = 0, mid = 0;
  56.     int high = unsorted_arr.size() - 1;
  57.    
  58.    
  59.     while (mid <= high)
  60.     {
  61.         if (unsorted_arr[mid] < first)
  62.         {
  63.             Swap(&unsorted_arr[low], &unsorted_arr[mid]);
  64.             low++;
  65.             mid++;
  66.         }
  67.         else if (unsorted_arr[mid] >= 5 && unsorted_arr[mid] <= 10)
  68.         {
  69.             mid++;
  70.         }
  71.         else
  72.         {
  73.             Swap(&unsorted_arr[mid], &unsorted_arr[high]);
  74.             high--;
  75.         }
  76.     }
  77. }
  78.  
  79. int main()
  80. {
  81.     std::vector<int> unsorted_arr = {0, 1, 2, 0, 1, 2};
  82.     SortThreeType(unsorted_arr);
  83.    
  84.     PrintArr(unsorted_arr);
  85.    
  86.    
  87.     std::vector<int> unsorted_arr1 = {10, 5, 6, 3, 20, 9, 40};
  88.     std::pair<int, int> range{5, 10};
  89.    
  90.     PartitionAroundRange(unsorted_arr1, range);
  91.     PrintArr(unsorted_arr1);
  92.    
  93.     return 0;
  94. }
Tags: dsa
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement