Advertisement
Gistrec

Моя быстрая сортировка

Dec 6th, 2017
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.96 KB | None | 0 0
  1. #pragma once
  2. #include <vector>
  3. #include <iostream>
  4.  
  5. struct Class {
  6.     int value;
  7.     Class(int value) {
  8.         this->value = value;
  9.     }
  10. };
  11.  
  12. void printArray(std::vector<Class> &vector) {
  13.     for (int i = 0; i < vector.size(); i++) {
  14.         std::cout << vector[i].value << " ";
  15.     }
  16.     std::cout << std::endl;
  17. }
  18.  
  19. void qsort(std::vector<Class> &vector, int left, int right) {
  20.    
  21.     int main = right; // Порядок опорного элемента в векторе
  22.  
  23.     int local_left = left;
  24.     int local_right = right;
  25.  
  26.     while (local_left < local_right) {
  27.  
  28.         /*std::cout << "----------------- START --------------------------" << std::endl;
  29.         std::cout << "Vector: "; printArray(vector);
  30.         std::cout << "Left: " << local_left << std::endl;
  31.         std::cout << "Right: " << local_right << std::endl << std::endl;*/
  32.  
  33.         // сдвигаем левую границу пока элемент vector[loval_right] больше [опорного элемента]
  34.         while ((vector[local_left].value <= vector[main].value) && (local_left < local_right))
  35.             local_left++;
  36.  
  37.         if (local_right != local_left) {// если границы не сомкнулись
  38.             // Если элемент [left] соседний с [main]
  39.             // Свопаем их
  40.             if (local_left + 1 == main) {
  41.                 std::swap(vector[local_left], vector[main]);
  42.             // Иначе перемещаем элемент [right] на место разрешающего
  43.             } else {
  44.                 std::swap(vector[local_left], vector[main-1]);
  45.                 std::swap(vector[main-1], vector[main]);
  46.                 main--;
  47.             }
  48.             // сдвигаем левую границу вправо
  49.             local_right--;
  50.         }
  51.        
  52.     }
  53.     // Левая часть
  54.     if (local_left != left) qsort(vector, left, main - 1);
  55.     // Правая часть
  56.     if (local_right != right) qsort(vector, main, right);
  57.  
  58.         /*std::cout << "Vector[local_left]: " << vector[local_left].value << std::endl;
  59.         std::cout << "Main: " << vector[main].value << std::endl;
  60.         if (vector[local_left].value > vector[main].value && (local_left + 1) != main) {
  61.             std::cout << "Swap: " << vector[local_left].value << " to "<< vector[local_right - 1].value << std::endl;
  62.             std::swap(vector[local_left], vector[local_right - 1]);
  63.             std::cout << "Swap: " << vector[local_right - 1].value << " to " << vector[local_right].value << std::endl;
  64.             std::swap(vector[local_right - 1], vector[local_right]);
  65.             main--;
  66.             local_right--;
  67.         } else if ((local_left + 1) == main) {
  68.             std::swap(vector[local_left], vector[main]);
  69.             main++;
  70.         }
  71.         std::cout << "----------------- MIDDLE --------------------------" << std::endl;
  72.         std::cout << "Vector: "; printArray(vector);
  73.         std::cout << "Left: " << local_left << std::endl;
  74.         std::cout << "Right: " << local_right << std::endl << std::endl;
  75.         if (vector[local_left].value < vector[main].value) {
  76.             local_left++;
  77.         }
  78.         std::cout << "----------------- END --------------------------" << std::endl;
  79.         std::cout << "Vector: "; printArray(vector);
  80.         std::cout << "Left: " << local_left << std::endl;
  81.         std::cout << "Right: " << local_right << std::endl << std::endl;
  82.     }
  83.  
  84.     std::cout << std::endl;
  85.     std::cout << " ------------- END FUNCTION ---------- " << std::endl;
  86.     std::cout << "NO Left: " << left << std::endl;
  87.     std::cout << "NO Right: " << right << std::endl;
  88.     if ((local_left + 2) != left) {
  89.  
  90.     }
  91.     if ((local_right + 2) != right) {
  92.         std::cout << "LOCAL LEFT" << std::endl;
  93.         qsort(vector, local_left, right);
  94.     }*/
  95. }
  96.  
  97. int main() {
  98.     std::vector<Class> vector;
  99.  
  100.     vector.push_back(Class(1));
  101.     vector.push_back(Class(8));
  102.     vector.push_back(Class(5));
  103.     vector.push_back(Class(3));
  104.     vector.push_back(Class(2));
  105.  
  106.     vector.push_back(Class(1));
  107.     vector.push_back(Class(8));
  108.     vector.push_back(Class(8));
  109.     vector.push_back(Class(1));
  110.     vector.push_back(Class(4));
  111.     vector.push_back(Class(9));
  112.     vector.push_back(Class(2));
  113.     vector.push_back(Class(7));
  114.     printArray(vector);
  115.     std::cout << std::endl;
  116.     qsort(vector, 0, vector.size() - 1);
  117.     printArray(vector);
  118.     system("pause");
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement