Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=, в котором для любого 1<=i<=n элемент K’(i) <=»K’(i+1).» При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют. Наиболее [...]
Упорядоченный массив B’ получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,…,N выполняется вставка узла Кi в B’ так, что B’ остается упорядоченным списком длины i. Например, для начального списка B=<20,-5,10,8,7> имеем: B=<20,-5,10,8,7> B’=<> B=<-5,10,8,7> B’=<20> B=<10,8,7> B’=<-5,20> B=<8,7> B’=<-5,10,20> B=<7> B’=<-5,8,10,20> B=<> [...]
Упорядоченный список В’ получается из В многократным применением выборки из В минимального элемента, удалением этого элемента из В и добавлением его в конец списка В’, который первоначально должен быть пустым. Например: B=<20,10,8,-5,7>, B’=<> B=<20,10,8,7>, B’=<-5> B=<20,10,8>, B’=<-5,7> B=<20,10>, B’=<-5,7,8> B=<20>, B’=<-5,7,8,10> B=<>, B’=<-5,7,8,10,20> . Функция select упорядочивает массив s [...]
Упорядоченные списки А и В длин М и N сливаются в один упорядоченный список С длины М+N, если каждый элемент из А и В входит в С точно один раз. Так, слияние списков А=<6,17,23,39,47> и В=<19,25,38,60> из 5 и 4 элементов дает в качестве результата список С=<6,17,19,23,25,38,39,47,60> из 9 элементов. Для слияния списков А и [...]
Для получения упорядоченного списка B’ последовательность значений В= разделяют на N списков В1=, B2=,…,Bn=, длина каждого из которых 1. Затем осуществляется функция прохода, при которой М>=2 упорядоченных списков B1,B2,…,Bm заменяется на М/2 (или (М+1)/2) упорядоченных списков, B(2i-1)-oго и B(2i)-ого ( 2i<=M ) и добавлением Вm при нечетном М. Проход повторяется до тех пор пока не [...]
Быстрая сортировка состоит в том, что список В= реорганизуется в список B’,,B», где В’ – подсписок В с элементами, не большими К1, а В» – подсписок В с элементами, большими К1. В списке B’,,B» элемент К1 расположен на месте, на котором он должен быть в результирующем отсортированном списке. Далее к спискам B’ и В» снова [...]
Предположим, что элементы линейного списка В есть Т-разрядные положительные десятичные числа D(j,n) – j-я справа цифра в десятичном числе n>=0, т.е. D(j,n)=floor(n/m)%10, где m=10^(j-1). Пусть В0,В1,…,В9 – вспомогательные списки (карманы), вначале пустые. Для реализации распределяющей сортировки выполняется процедура, состоящая из двух процессов, называемых распределение и сборка для j=1,2,…,T. PАСПРЕДЕЛЕНИЕ заключается в том, что элемент Кi [...]
