Quicksort иногда не заканчивается?

Question

Я сделал кучу попыток алгоритма быстрой сортировки, который я просто не могу заставить работать. Этот код является самым близким я получил, за исключением того, что он примерно один раз в пять раз не полностью сортирует - он выводит что-то вроде 266, 186, 219, 276, 357, 405, 686, 767, 834, 862. Я попытался найти общность между всеми наборами чисел, которые делают это, но я ничего не могу найти. Я провел много часов, пробираясь через него с помощью отладчика, но ничего не вижу (хотя я чувствую, что мне не хватает чего-то очевидного). Что я делаю не так?

public static void sort(ArrayList<Integer> arr, int left, int right) { 
    int i = left - 1, j = right, v = arr.get(right); 
    if(right - i == 0 || right - i == 1)return; 

    for(;;) { 
     while(arr.get(++i) < v); 
     while(v < arr.get(--j) && j != 0) 
      if(j == 1)break; 
     if(i >= j)break; 

     Collections.swap(arr, i, j); 
    } 
    Collections.swap(arr, i, right); 

    sort(arr, left, i - 1); 
    sort(arr, i, right); 
} 

Answer 1

Я сделал две вещи, чтобы ваш код, чтобы заставить его работать:

в начале метода установить j = right +1 и двигаться v = arr.get(right) к после первой, если заявление.

должен выглядеть примерно так:

public static void sort(ArrayList<Integer> arr, int left, int right) { 
     int i = left - 1; 
     int j = right + 1; 
     if (right - i == 0 || right - i == 1) return; 
     int v = arr.get(right); 

     for (;;) { 
      while (arr.get(++i) < v); 
      while (v < arr.get(--j) && j != 0) 
       if (j == 1) break; 
      if (i >= j) break; 

      Collections.swap(arr, i, j); 
     } 
     Collections.swap(arr, i, right); 

     sort(arr, left, i - 1); 
     sort(arr, i, right); 
    } 

Но это было действительно нечитаемым код, вы должны прочитать книгу CleanCode.