Быстрая сортировка с использованием первого элемента в виде сводной таблицы

Question

Я выполнил быструю сортировку, выбрав первый элемент в качестве точки поворота. он отлично работает для общих тестовых примеров, но рассмотрим случай, когда массив отсортирован по обратному адресу, например, 5 4 3 2 1. Я понимаю, где он бросает ошибку времени выполнения. но я не могу исправить это правильно. Является ли реализация для первого элемента правильной? Пожалуйста, предложите изменения.

public static void quicksort(int low,int high) 
    { 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<=small_index) 
    { 
     while(a[small_index]>pivot) 
     small_index--; 

     while(a[large_index]<pivot) 
     large_index++; 

     if(large_index<=small_index) 
     { 
     temp = a[large_index]; 
     a[large_index]= a[small_index]; 
     a[small_index]= temp; 
     large_index++; 
     small_index--; 
     } 
    } 

    temp = a[small_index]; 
    a[small_index]= a[low]; 
    a[low]= temp; 


    quicksort(low,small_index-1); 
    quicksort(small_index+1,high); 
    } 

    } 

Answer 1

Следующий цикл продолжается выше high, когда large_index начинается уже выше оси и случается так, что ось больше, чем каждый элемент, расположенный после него:

while(a[large_index]<pivot) 
large_index++; 

Там могут быть и другие ошибки, конечно.

Answer 2

Были многочисленные недостатки:

а) Ненужные обменивать вне цикла

Темп = а [small_index]; a [small_index] = a [низкий]; a [низкий] = темп;

b) Неправильная инициализация large_index.

c) Вызов рекурсивной функции без проверки значений small_index и large_index.

Я исправила их,

теперь функция будет выглядеть следующим образом:

if (low < high) { 
      int temp = 0; 
      int pivot = a[low]; 
      int large_index = low; 
      int small_index = high; 

      while (large_index <= small_index) { 
       while (a[small_index] > pivot) 
        small_index--; 

       while (a[large_index] < pivot) 
        large_index++; 

       if (large_index <= small_index) { 
        temp = a[large_index]; 
        a[large_index] = a[small_index]; 
        a[small_index] = temp; 
        large_index++; 
        small_index--; 
       } 
      } 

      if(low < small_index) 
      { 
       quicksort(low, small_index); 
      } 
      if(large_index < high) 
      { 
       quicksort(large_index, high); 
      } 
     } 

Теперь, наблюдая переменные в вашей части коды: (ваш код будет терпеть неудачу в конечной итерации любой данный вход, если входной сигнал не не отсортирован)

Рассмотрим на вход 2,1

1st iteration: 

pivot = 2 
large_index = 1; 
small_index = 1; 


while1: 
1<=1 -> true 
    while2: 1>2 false. 
    while3: 1<2 true. -> large_index++ 
       2nd time in while loop large_index =2 which is > the size of a. 

Результатом является IndexArrayOutOfBounds.

Что показывает, что ваша инициализация big_index была неправильной.

Должно быть: large_index = low; вместо низкого + 1;

Надеюсь, это поможет.

Answer 3

После некоторых попыток я смог выполнить функцию Quicksort, и теперь она отлично работает. @BatScream Я все еще использовал small_index = low + 1 в своем коде. Так что я не ошибся. И первоначальный алгоритм быстрой сортировки следует этому механизму. Для справки смотрите лекцию на QuickSort профессором Принстона Робертом Седжуиком. Пожалуйста, напомните, есть ли недостаток в отредактированном алгоритме быстрой сортировки.

public static void quicksort(int low,int high) 
{ 

    if(low<high) 
    { 
    int temp=0; 
    int pivot=a[low];      
    int large_index=low+1; 
    int small_index=high; 

    while(large_index<small_index) 
    { 

    while(a[large_index]<pivot) { 
    if(large_index==high) 
    break; 
    large_index++; 
    } 

    while(a[small_index]>pivot) 
    { 
    if(small_index==low) 
    break; 
    small_index--; 
    } 

    if(large_index<small_index) { 
    temp = a[large_index]; 
    a[large_index]= a[small_index]; 
    a[small_index]= temp; 
    large_index++; 
    small_index--; 
    } 
    } 

    if(a[small_index]<pivot) {        
     temp = a[small_index]; 
     a[small_index]= a[low]; 
     a[low]= temp; 
    } 

    if(low<small_index)         //Recursively sort the left half. 
    { 
    quicksort(low,small_index-1); 
    } 

    if(high>small_index)         //Recursively sort the right half. 
    { 
    quicksort(small_index+1,high); 
    } 
    } 

    }