Реализация быстрой сортировки на функциональном языке - PullRequest
Новая
       93

Реализация быстрой сортировки на функциональном языке

1 голос
/ 31 октября 2011

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

В Wikipedia есть код быстрой сортировки в Standard 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)). Фильтр вернет список всего в xs меньше p *, который объединяется с p, который добавляется во все> = p. *

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

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

функция быстрой сортировки (массив, «влево», «вправо») 

  // 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'

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

Ответы [ 2 ]

2 голосов
/ 31 октября 2011

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

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

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

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

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

1 голос
/ 31 октября 2011

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

Filta вернет список всего в xs меньше p *, который объединяется с p, который добавляется во все> = p. *

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

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

...