Почему мой quicksort сортирует массив в обратном порядке?

Question

Я пытаюсь реализовать quicksort для массива строк, но кажется, что он сортирует массив, но в обратном порядке, мне интересно, почему это так и как я могу решить эту проблему, чтобы сортировать ее нормально ... Это моя реализация:

public class Main { 

    public static void main(String[] args) { 
     String[] list = {"a", "f", "c", "b"}; 
     quickSort(list, 0, list.length - 1); 
     for (String s : list) { 
      System.out.println(s); 
     } 
    } 

    private static void quickSort(String[] list, int start, int end) { 
     if (start < end) { 
      int pIndex = partition(list, start, end); 
      quickSort(list, start, pIndex - 1); 
      quickSort(list, pIndex + 1, end); 
     } 
    } 

    private static int partition(String[] list, int start, int end) { 
     String pivot = list[end]; 

     int leftCounter = start; 
     int rightCounter = end; 

     while (leftCounter < rightCounter) { 
      while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) { 
       leftCounter++; 
      } 
      while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) { 
       rightCounter--; 
      } 
      if (leftCounter < rightCounter) { 
       swap(list, leftCounter, rightCounter); 
      } 
     } 
     swap(list, start, end); 
     return end; 
    } 

    private static void swap(String[] list, int start, int end) { 
     String aux = list[start]; 
     list[start] = list[end]; 
     list[end] = aux; 
    } 
} 

Answer 1

Реализация, представленная в вопросе, меня смущает. Это не значит, что это неверно (или, по крайней мере, близко к правильному), но я считаю это трудным для чтения (что, возможно, более важно). Возможно, что я просто медленно, и эта реализация на самом деле очень интуитивно понятна, но я склоняюсь к ней, делая ее более умной, чем последовательной.

В общем, quicksort - это рекурсивный алгоритм, который разбивает набор данных на три ячейки по сравнению с точкой поворота (меньше, равно и больше), затем сортирует неравные бункеры (используя тот же алгоритм) , а затем объединяет результаты для формирования отсортированного набора данных. На английском языке очень интуитивно понятно, как он должен работать. Нет причин, по которым он не может быть одинаковым в коде. Я бы всегда стремился написать код, который вы можете понять (а затем сделать его более эффективным по мере необходимости), вместо того, чтобы пытаться написать что-то, что вы не можете понять, а затем подняться на ручей, когда он не работает.

Ниже приведено более подробное воплощение, которое (по крайней мере, для меня) кажется более ясным в его работе. Он также очень неэффективен (он составляет полдюжины различных списков и массивов только для сортировки одного набора данных). Я не извиняюсь за это; Я предполагаю, что этот вопрос носит академический характер. Если вам нужно сделать его более эффективным, это упражнение для пользователя, но нет причин, чтобы его нельзя было разбить на интуитивные шаги, как это сделано ниже (это сэкономит вам много головной боли).

public class QuickSortTest { 
    private static String[] data = new String[] {"a", "b", "c", "f", "b", "e", "b"}; 

    public static void main(String[] args) { 
     String[] sortedData = quickSort(data); 
     for (String str : sortedData) { 
      System.out.println(str); 
     } 
    } 

    private static String[] quickSort(String[] data) { 
     // Edge case: return just the data if there are 0 or 1 elements (already sorted) 
     if (data.length <= 1) { 
      return data; 
     } 

     // Initialize the return structure 
     String[] sortedData = new String[data.length]; 

     // Choose the pivot (can be any value) 
     String pivot = data[data.length - 1]; 

     // Initialize the bins 
     ArrayList<String> lessThan = new ArrayList<String>(); 
     ArrayList<String> equalTo = new ArrayList<String>(); 
     ArrayList<String> greaterThan = new ArrayList<String>(); 

     // Place the data into bins (based on the pivot) 
     for (String str : data) { 
      int compareValue = str.compareTo(pivot); 
      if (compareValue < 0) { 
       lessThan.add(str); 
      } 
      else if (compareValue > 0) { 
       greaterThan.add(str); 
      } 
      else { 
       equalTo.add(str); 
      } 
     } 

     // Sort the non-equal data 
     String[] lessThanSorted = quickSort(lessThan.toArray(new String[0])); 
     String[] greaterThanSorted = quickSort(greaterThan.toArray(new String[0])); 

     // Merge the data 
     int length = 0; 
     for (String less : lessThanSorted) { 
      sortedData[length++] = less; 
     } 
     for (String equal : equalTo) { 
      sortedData[length++] = equal; 
     } 
     for (String greater : greaterThanSorted) { 
      sortedData[length++] = greater; 
     } 

     return sortedData; 
    } 
} 

Как и в сторону, если кто-то ищет, чтобы отсортировать данные в практике, просто использовать Collections.sort()

Answer 2

Проблема заключается в вашем partition методе:

private static int partition(String[] list, int start, int end) { 
     String pivot = list[end]; 

     int leftCounter = start; 
     int rightCounter = end; 

     while (leftCounter < rightCounter) { 
      while (list[leftCounter].compareTo(pivot) <= 0 && leftCounter < end && rightCounter > leftCounter) { 
       leftCounter++; 
      } 
      while (list[rightCounter].compareTo(pivot) >= 0 && rightCounter > start && rightCounter >= leftCounter) { 
       rightCounter--; 
      } 
      if (leftCounter < rightCounter) { 
       swap(list, leftCounter, rightCounter); 
      } 
     } 

Вплоть до этого момента, это в основном стандарт Hoare partition. В конце этого цикла ваш список будет выглядеть как [l1, l2, ..., lx, g1, g2, ..., gy, pivot], где l1, l2, ..., lx все меньше или равно оси, а g1, g2, ..., gy больше или равно оси. leftCounter указывает на g1 и rightCounter указывает на lx. Вы должны убедиться, что стержень разделяет два множества, и что вы возвращаетесь правильный индекс:

 swap(list, start, end); 
     return end; 
    } 

Эти две линии являются источником вашей проблемы. Вам нужно сделать swap(list, leftCounter, end), чтобы переместить шарнир в нужное место в списке. Теперь ваш список будет выглядеть как [l1, l2, ..., lx, pivot, g2, g3, ..., gy, g1]. Вам нужно вернуть индекс стержня, который равен leftCounter.

---

Относительно почему это отсортировано в обратном порядке: вам повезло. Попробуйте на других входах, он не всегда сортируется в обратном порядке.

String[] list = { "a", "c", "a", "b","c","f","g","a","b" } 

[а, г, Ь, а, е, с, с, Ь, а]