-5

как написать алгоритм Quick Sort?

2
  • Главное - правильно написать :)
    – Harry
    8 мая 2018 в 15:11
  • И там (по ссылке) и тут (в скопипасченном ответе) убогая реализация. В нормальной рекурсивной реализации, после разбиения массива сначала надо сортировать короткую часть (тогда стек никогда не переполнится). Ну, еще можно порассуждать о правильном выборе разделяющего элемента, который минимизирует вероятность сползания сложности алгоритма к квадратичной
    – avp
    8 мая 2018 в 20:39

1 ответ 1

0

Плохо ищете. В интернете полно статей. Код взял из Quick Sort

void quickSort(int arr[], int left, int right) {
  int i = left, j = right;
  int tmp;
  int pivot = arr[(left + right) / 2];

  /* partition */

  while (i <= j) {
        while (arr[i] < pivot)
              i++;
        while (arr[j] > pivot)
              j--;
        if (i <= j) {
              tmp = arr[i];
              arr[i] = arr[j];
              arr[j] = tmp;
              i++;
              j--;
        }
  };

  /* recursion */

  if (left < j)
        quickSort(arr, left, j);

      if (i < right)
            quickSort(arr, i, right);
}
1
  • что тут делает это строка int pivot = arr[(left + right) / 2];? 10 мая 2018 в 14:22

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.