Справка по быстрой сортировке, не знаю, почему разбиение возвращает индекс, а не массив

Question

Мне было интересно, может ли кто-нибудь помочь мне в быстрой сортировке. Я понимаю общую идею для разделения, но не уверен, почему он возвращает индекс

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

      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--;
            }
      }

      return i;
}

void quickSort(int arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

Я понимаю всю часть перестановки. это имеет смысл для меня, но я не уверен, почему раздел возвращает только индекс. я думал, что это должно было вернуть массив? как если бы проблема была в ... Сортировке {1, 12, 5, 26, 7, 14, 3, 7, 2} Я думал, что это вернется ...

1, 2, 5, 7, 3, 14, 7, 26, 12

Наверное, поэтому я не понимаю действительную функцию быстрой сортировки. но если бы кто-то мог помочь объяснить это ясно и легко понять, это было бы очень ценно. Большое спасибо!

Answer 1

Индекс, который был возвращен, существует только для определения конца рекурсии в алгоритме быстрой сортировки.В основном это индекс элемента pivot, который используется для определения меньших и больших чисел.

AND: Вы имеете в виду усовершенствованный алгоритм быстрого поиска.В базовой версии алгоритма QuickSearch возвращаемый индекс не понадобится.

Он также будет работать с: (но намного медленнее)

void quickSort(int arr[], int left, int right) 
{
      if (left < right)
      {
         int index = partition(arr, left, right);
         quickSort(arr, left, index - 1);
         quickSort(arr, index+1, right);
      } 
}

Answer 2

Ваша функция секционирования модифицирует массив на месте. Целое число, которое оно возвращает, является индексом, перед которым значения меньше, чем сводная, и начиная с которой значения больше, чем сводная. Два рекурсивных вызова сортируют меньшие и большие элементы; условие, проверенное перед рекурсивными вызовами, служит базовым случаем.