QuickSort алгоритм объяснения

Question

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

private static void quickSort (ArrayList <String> list, int first, int last){ 

     int g = first; 
     int h = last; 

     int midIndex = (first + last)/2; 
     String dividingValue = list.get(midIndex); 

     do{ 
      while (list.get(g).compareTo(dividingValue) < 0) g++; 
      while (list.get(h).compareTo(dividingValue) > 0) h--; 
      if (g <= h) 
      { 
       swap(list,g,h); 
       g++; 
       h--; 
      } 
     } 

     while (g < h); 

     if (h > first) quickSort (list,first,h); 
     if (g < last) quickSort (list,g,last);  
    } 

    private static void swap (ArrayList <String> list, int first, int h) 
    { 
     String temp = list.get(first); 
     list.set(first, list.get(h)); 
     list.set(h, temp); 
    } 

я работает, но это на самом деле не имеет смысла для меня. Может ли кто-нибудь объяснить мне этот код? Или дать более простой код для быстрой сортировки, если это возможно?

Answer 1

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

private static void quickSort (ArrayList <String> list, int first, int last) { 

    int g = first; 
    int h = last; 

    int midIndex = (first + last)/2; 
    String dividingValue = list.get(midIndex); 

Затем мы начинаем с противоположных концов диапазона и работаем вовнутрь. Мы хотим, чтобы все слева от стержня было меньше, а все справа было больше. Таким образом, мы пропускаем любые элементы, которые уже удовлетворяют этому.

do { 
     while (list.get(g).compareTo(dividingValue) < 0) g++; 
     while (list.get(h).compareTo(dividingValue) > 0) h--; 

Когда мы достигаем двух элементов, которые одновременно нарушают свойство мы обменять их, чтобы они на правильной стороне, а затем двигаться дальше внутрь. Проверка if (g <= h) необходима, поскольку мы применяем g++ и h-- вслепую (в отличие от проверки значения как в петлях while) после замены. Кажется, что он меняет свод, чтобы не иметь противоположного элемента для обмена. Это определенно необходимо протестировать для обеспечения правильности.

 if (g <= h) 
     { 
      swap(list, g, h); 
      g++; 
      h--; 
     } 

Мы продолжаем делать это, пока мы не достигнем пивот (слегка неявное, так как стержень может быть заменен).

} while (g < h); 

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

if (h > first) 
     quickSort(list, first, h); 
    if (g < last) 
     quickSort(list, g, last);  
} 

private static void swap (ArrayList <String> list, int first, int h) 
{ 
    String temp = list.get(first); 
    list.set(first, list.get(h)); 
    list.set(h, temp); 
}