Gistrec

Быстрая сортировка

Dec 5th, 2017
346
0
Never
1
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.26 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. // Функция быстрой сортировки
  4. void quickSort(int *numbers, int left, int right)
  5. {
  6.   int pivot; // разрешающий элемент
  7.   int l_hold = left; //левая граница
  8.   int r_hold = right; // правая граница
  9.   pivot = numbers[left];
  10.   while (left < right) // пока границы не сомкнутся
  11.   {
  12.     while ((numbers[right] >= pivot) && (left < right))
  13.       right--; // сдвигаем правую границу пока элемент [right] больше [pivot]
  14.     if (left != right) // если границы не сомкнулись
  15.     {
  16.       numbers[left] = numbers[right]; // перемещаем элемент [right] на место разрешающего
  17.       left++; // сдвигаем левую границу вправо
  18.     }
  19.     while ((numbers[left] <= pivot) && (left < right))
  20.       left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]
  21.     if (left != right) // если границы не сомкнулись
  22.     {
  23.       numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
  24.       right--; // сдвигаем правую границу вправо
  25.     }
  26.   }
  27.   numbers[left] = pivot; // ставим разрешающий элемент на место
  28.   pivot = left;
  29.   left = l_hold;
  30.   right = r_hold;
  31.   if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива
  32.     quickSort(numbers, left, pivot - 1);
  33.   if (right > pivot)
  34.     quickSort(numbers, pivot + 1, right);
  35. }
  36. int main()
  37. {
  38.   int a[10];
  39.   // Заполнение массива случайными числами
  40.   for (int i = 0; i<10; i++)
  41.     a[i] = rand() % 20 - 10;
  42.   // Вывод элементов массива до сортировки
  43.   for (int i = 0; i<10; i++)
  44.     printf("%d ", a[i]);
  45.   printf("\n");
  46.   quickSort(a, 0, 9); // вызов функции сортировки
  47.   // Вывод элементов массива после сортировки
  48.   for (int i = 0; i<10; i++)
  49.     printf("%d ", a[i]);
  50.   printf("\n");
  51.   getchar();
  52.   return 0;
  53. }
Advertisement
Comments
  • User was banned
Add Comment
Please, Sign In to add comment