Все функции, представленные в базовой сортировке, выполняются с временной сложностью O (n2). Такие алгоритмы, как сортировка вставкой и пузырьковая сортировка, хотя и удобны для ситуаций собеседования и общих академических знаний, редко используются в производственном коде. Однако алгоритм Быстрая сортировка имеет более широкое практическое применение. Часто используемый алгоритм можно найти как в библиотеках кода, так и в реальных проектах. Quicksort имеет временную сложность O (n log n) и применяет стратегию разделяй и властвуй. Эта комбинация приводит к повышенной алгоритмической производительности.

Как это работает

Quicksort применяет ряд правил для «замены» пар значений. События подкачки выполняются на месте, поэтому никаких дополнительных структур для обработки данных не требуется. В нашей реализации специальные переменные с именами wall и pivot помогут управлять процессом обмена:

На приведенном выше рисунке показан алгоритм в начале процесса сортировки. Функция начинается со сравнения каждого значения индекса со значением «сравнения» (например, сводным). Стена отображает положение значений, которые были заменены или оценены. Поскольку мы только что начали процесс сортировки, текущие индексы и индексы стены отображаются с одинаковым значением (например, 7).

Проведение сравнений

Как показано ниже, на следующем шаге сравниваются текущее и сводное значения. Поскольку текущее значение (например, 7) больше, чем точка поворота (например, 4), свопинга не происходит. Однако текущий индекс переходит на следующую позицию.

На этом этапе текущее значение (например, 2) снова сравнивается с точкой поворота. Поскольку 2 меньше 4, стена заменяется текущим значением индекса. По завершении стена переместится на следующую позицию индекса.

Преодоление разрыва

Процесс сравнения и замены происходит до тех пор, пока текущий индекс не встретится с точкой поворота. По завершении ось меняется местами со значением индекса стены. Интересно, что после смены точки поворота она считается отсортированной. Несмотря на то, что большинство значений остаются несортированными (на этом этапе), все значения меньше 4 теперь расположены слева. И наоборот, все значения больше 4 располагаются вправо.

Начальное значение поворота, равное 4, использовалось, чтобы показать, как Quicksort может разделить коллекцию на относительно равные сегменты. Этот процесс называется секционированием. Чтобы отсортировать оставшиеся значения, каждое значение слева или справа от начальной точки поворота также рассматривается как точка поворота, и процесс повторяется.

КОД

В Swift полный алгоритм выражается двумя функциями. Основная функция quickSort управляет общим выполнением, в частности, выбором каждого значения поворота. Подобно другим нашим алгоритмам сортировки, реализация quickSort написана как расширение Array. Однако вложенная функция применяет рекурсию в качестве основной управляющей структуры:

extension Array where Element: Comparable {
  
  mutating func quickSort() -> Array<Element> {        
        
        func qSort(start startIndex: Int, _ pivot: Int) {
            
            if (startIndex < pivot) {
                let iPivot = qPartition(start: startIndex, pivot)
                qSort(start: startIndex, iPivot - 1)
                qSort(start: iPivot + 1, pivot)
            }
        }   
        
        qSort(start: 0, self.endIndex - 1)
        return self
        
    }          
}

Наконец, процесс qPartition сортирует выбранное значение поворота в правильное положение индекса:

//sorts selected pivot
mutating func qPartition(start startIndex: Int, _ pivot: Int) -> Int {
        
   var wallIndex: Int = startIndex
                
   //compare range with pivot
   for currentIndex in wallIndex..<pivot {
            
       if self[currentIndex] <= self[pivot] {
             if wallIndex != currentIndex {
                self.swapAt(currentIndex, wallIndex)
             }
                
            //advance wall
            wallIndex += 1
       }
   }
        
        
   //move pivot to final position
   if wallIndex != pivot {
     self.swapAt(wallIndex, pivot)
   }        
      return wallIndex     
   }
//execute sort
var sequence: Array<Int> = [7, 2, 1, 6, 8, 5, 3, 4]
let results = sequence.quickSort()

Понравилось это эссе? Прочтите и откройте для себя другой мой контент на Medium или получите полную книгу в формате EPUB, PDF или Kindle.