0

Доброго времени суток. Никак не могу разобраться с алгоритмом быстрой сортировки. Решил вручную выполнить этот алгоритм на листочке, но застрял в одном месте. Допустим, у нас есть массив:

6 7 1 9 4 6 3 *10* 12 8 7 12 23 2 3 12 

Есть два указателя, один на нулевой элемент(left), другой на последний(right). Находим опорный элемент, в моем случае это 10. Слева от него нету элементов которые больше, поэтому указатель left перемещается на 10, а вот справа есть элементы которые меньше опорного, но обмен будет происходить уже с элементами правой части(так как left указывает на 10) и в итоге даже если элемент < опорного, он всё равно останется справа от него. А насколько я понял алгоритм, после первого прохода, слева от опорного должны остаться элементы которые меньше него и наоборот, справа, которые больше. Где я ошибаюсь?

P.S. Пишу на C++.

P.P.S. Если нужен код, могу добавить.

1 ответ 1

1

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

  var arr = [6, 7, 1, 9, 4, 6, 3, 10, 12, 8, 7, 12, 23, 2, 3, 12];

  function quicksort(data, left, right) { 
      if(left >= right) return;
      var pivot_index = Math.floor((left + right)/2);
      var pivot = arr[pivot_index];
      var part_index = partition(data, left, right, pivot);
      quicksort(data, left, part_index - 1);
      quicksort(data, part_index, right);
 }

    function partition(data, left, right, pivot) {
      var temp;
      while(left <= right) {
        while(data[left] < pivot) left++;
        while(data[right] > pivot) right--;
        if(left <= right) {
          temp = data[left];
          data[left] = data[right];
          data[right] = temp;
          left++;
          right--;
        }  
      }
      return left;
    }
    quicksort(arr, 0, arr.length - 1);
console.log(arr);

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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