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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

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