Блог

Мне нужно реализовать быструю сортировку в SML для домашнего задания, и я заблудился. Ранее я не был знаком с тем, как была реализована быстрая сортировка, поэтому я прочитал об этом, но каждая реализация, о которой я читал, была обязательной. Это не выглядит слишком сложным, но я понятия не имел, как реализовать быструю сортировку функционально.

В Википедии есть код быстрой сортировки на стандартном ML (который является языком, необходимым для моего задания), но я не понимаю, как это работает.

Код Википедии:

 val filt = List.filter
fun quicksort << xs = let
fun qs [] = []
 | qs [x] = [x]
 | qs (p::xs) = let
     val lessThanP = (fn x => << (x, p))
     in
       qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs))
     end
in
  qs xs
end
 

В частности, я не понимаю эту строку: qs (filt lessThanP xs) @ p :: (qs (filt (not o lessThanP) xs)) . filt вернет список всего, что меньше xs, чем p *, который объединяется с p, что соответствует everything >= p .*

* предполагая, что функция << (x, p) возвращает true, когда x < p . Конечно, это не обязательно должно быть так.

На самом деле, ввод этого помогает мне немного понять, что происходит. В любом случае, я пытаюсь сравнить эту функцию SML с псевдокодом быстрой сортировки wiki, который следует ниже.

функция быстрой сортировки (массив, ‘left’, ‘right’)

   // If the list has 2 or more items
  if 'left' < 'right'

      // See "Choice of pivot" section below for possible choices
      choose any 'pivotIndex' such that 'left' ≤ 'pivotIndex' ≤ 'right'

      // Get lists of bigger and smaller items and final position of pivot
      'pivotNewIndex' := partition(array, 'left', 'right', 'pivotIndex')

      // Recursively sort elements smaller than the pivot
      quicksort(array, 'left', 'pivotNewIndex' - 1)

      // Recursively sort elements at least as big as the pivot
      quicksort(array, 'pivotNewIndex'   1, 'right')
 

Где раздел определяется как

 // left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
//   number of elements in subarray = right-left 1
function partition(array, 'left', 'right', 'pivotIndex')
  'pivotValue' := array['pivotIndex']
  swap array['pivotIndex'] and array['right']  // Move pivot to end
  'storeIndex' := 'left'
  for 'i' from 'left' to 'right' - 1  // left ≤ i < right
      if array['i'] < 'pivotValue'
          swap array['i'] and array['storeIndex']
          'storeIndex' := 'storeIndex'   1
  swap array['storeIndex'] and array['right']  // Move pivot to its final place
  return 'storeIndex'
 

Итак, где именно происходит разделение? Или я неправильно думаю о быстрой сортировке SMLs?

Итак, где именно происходит разделение? Или я неправильно думаю о быстрой сортировке SMLs?

Чисто функциональная реализация быстрой сортировки работает путем структурной рекурсии в списке ввода (IMO, это стоит упомянуть). Более того, как вы видите, два вызова «filt» позволяют разделить входной список на два подсписка (скажем, A и B), которые затем можно обрабатывать по отдельности. Здесь важно то, что:

• все элементы A меньше или равны элементу pivot («p» в коде)
• все элементы B больше, чем элемент pivot

Императивная реализация работает на месте, меняя местами элементы в одном и том же массиве. В предоставленном вами псевдокоде постинвариантность функции «partition» заключается в том, что у вас есть два подмассива, один из которых начинается с «left» входного массива (и заканчивается на «pivotIndex»), а другой начинается сразу после «pivotIndex» и заканчивается на «right». Здесь важно то, что два подмассива можно рассматривать как представления подсписков A и B.

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

Вы сказали это:

filt вернет список всего, что меньше xs, чем p *, который объединяется с p, что соответствует everything >= p .*

Это не совсем точно. filt вернет список всего, что меньше xs p , но этот новый список не будет немедленно объединен с p . Новый список фактически передается qs (рекурсивно), и все, что qs возвращается, объединяется с p .

В версии псевдокода разделение происходит на месте в array переменной. Вот почему вы видите swap в partition цикле. Разбиение на разделы на месте намного лучше для производительности, чем создание копии.