****************************************************************************************** * СОРТИРОВКА ВНУТРИ НАБЛЮДЕНИЙ: РЕАЛИЗАЦИЯ НЕКОТОРЫХ ПОПУЛЯРНЫХ СОРТИРОВОЧНЫХ АЛГОРИТМОВ * ****************************************************************************************** *Кирилл Орлов. kior@comtv.ru *Ниже дан SPSS-синтаксис некоторых известных сортировочных алгоритмов. *В данном случае алгоритмы применены для сортировки значений внутри наблюдений (кейсов). *Замените число 13 на то число переменных, сколько вы собираетесь ввести в сортировку, и запустите *тот синтаксис того или иного алгоритма. *Следующие алгоритмы рассмотрены: *ПРОСТЫЕ СОРТИРОВОЧНЫЕ АЛГОРИТМЫ: BUBBLE, SELECTION, INSERTION. *АЛГОРИТМЫ ДЛЯ БЫСТРОЙ СОРТИРОВКИ БОЛЬШИХ ВЕКТОРОВ: SHELL's INSERTION, HEAPSORT, QUICKSORT. *Что такое "устойчивый" сортировочный алгоритм: *Если в данных (векторе) есть одинаковые значения, то "устойчивый" сортировочный алгоритм *гарантирует, что порядок среди них будет соблюден, т.е. что значение, исходно бывшее в векторе *более ранним (левым) чем другое, равное ему, значение, на выходе обязательно *будет левее его. Не-"устойчивый" сортировочный алгоритм не гарантирует этого. ****************************************************************************************** *Создадим данные. input prog. vector v (13 f2). loop #c= 1 to 20. -loop #v= 1 to 13. - comp v(#v)= rnd(rv.uniform(1,13)). -end loop. -end case. end loop. end file. end input prog. exec. *************** BUBBLE (=EXCHANGE) алгоритм, УСТОЙЧИВЫЙ ВАРИАНТ ******************. *Вары перебираются попарно и, когда надо, обмениваются значениями. *Процедура повторяется до тех пор, пока больше обмена не требуется. *Этот алгоритм считается самым медленным из простых сортировочных алгоритмов. "Устойчивый". vector v= v1 to v13. loop #it= 1 to 13. /*Максимум может потребоваться столько итераций процедуры, сколько варов -comp #sorted= 1. /*Это сигнал, что вектор отсортирован, пока что допустим что он отсортирован -loop #i= 2 to 13-#it+1. /*Пробегаем вары, беря пару: данный вар и предыдущий (можно бы и наоборот: данный и последующий - неважно) /*Можно бы написать просто 'to 13', но 'to 13-#it+1' экономнее (дело в том что на каждой итерации наибольшее (при по убыванию - наименьшее) значение /*всей серии обязательно окажется в хвосте, след-но, на след итерации этого хвоста уже можно не касаться - не проверять, нужен ли там обмен) - do if v(#i) вместо <] -end loop. /*так что по выходе из пробежки m это точно номер наименьшего (наибольшего) значения -comp #temp= v(#i). /*Теперь совершаем обмен: temp это временная выписка значения -comp v(#i)= v(#m). /*Вот - на место i вставляем наименьшее (наибольшее) значение -comp v(#m)= #temp. /*а бывшее на месте i вставляем на место где было наименьшее (наибольшее) значение end loop. /*Берем следующее значение, стоящее на i+1, в качестве якобы-экстремума exec. *Если в данных есть пропущ. значения, они остаются на местах. Чтобы они отсортировались в хвост *вектора, добавь к к условию if-команды, что стоит внутри лупа: 'or miss(v(#m))'. ******** SELECTION (=EXTREMUM) алгоритм, ВАРИАНТ СО СДВИГОМ (УСТОЙЧИВЫЙ) *********. *Этот вариант основан на предыдущем, но вместо обмена 2-х значений - данного и экстремума - позициями *он затевает дополнительную пробежку со сдвиганием всех значений слева от экстремума на позицию вправо. *Ценой такого удлинения (замедления) работы достигается "устойчивость". vector v= v1 to v13. loop #i= 1 to 13-1. /*Берем по значению -comp #m= #i. /*m это будет позиция наименьшего (наибольшего, при сорт-ке по убыванию) значения; допустим пока что это и есть взятое значение -loop #j= #i+1 to 13. /*Пробегаем оставшиеся справа значения - if v(#j) вместо <] -end loop. /*так что по выходе из пробежки m это точно номер наименьшего (наибольшего) значения -comp #temp= v(#m). /*Выписываем найденный экстремум во временное хранилище -loop #j= #m-1 to #i by -1. /*Затеваем сдвижку: берем по одному значения слева от экстремума - comp v(#j+1)= v(#j). /*И сдвигаем на позицию вправо -end loop. -comp v(#i)= #temp. /*в итоге освобождая позицию i, куда и записываем наш экстремум end loop. /*Берем следующее значение, стоящее на i+1, в качестве якобы-экстремума exec. *************************** INSERTION алгоритм ****************************. *Заключается в том что берет значения по порядку (начиная со 2-го) и, *сканируя значения влево от него, отыскивает там правильное место, куда его вставить *(вручную так обычно сортируют картотеки). Вставляя, тем самым раздвигает этот левый подвектор вправо на одно значение. *Вставляя так значения за значением из правого подвектора в сортированный левый, наращивает последний. *Из простых алгоритмов этот считается довольно быстрым, в среднем он быстрее чем selection и гораздо быстрее чем bubble алгоритмы. *Однако его преимущество над selection - только на данных, которые исходно уже недалеки от сортированности в нужном направлении. *Алгоритм "устойчивый". Еще его плюс в том, что он разрешает, чтобы данные поступали (к примеру, порождались) постепенно, по значению ("онлайн"-сортировка). vector v= v1 to v13. loop #ins= 2 to 13. /*Берем по значению, начиная со 2-го (ins это его порядковый номер, номер вара) -comp #val= v(#ins). /*и запоминаем его; слева от него находятся значения, которые уже отсортированы алгоритмом -loop #i= #ins-1 to 1 by -1 if v(#i)>#val. /*Мы должны отыскать среди них место, куда вставить наше значение /*Поэтому, если примыкающее к нему слева больше него [меньше - для убывающей сортировки], пробегаем справа налево отсортированные значения - comp v(#i+1)= v(#i). /*сдвигая их вправо на позицию по одному, пока не дойдем до значения, ктр не больше чем наше -end loop. -comp v(#i+1)= #val. /*И тогда вставим наше значение рядышком справа от него; левая, сортированная часть вектора расширилась на 1 значение end loop. /*Берем следующее по порядку значение и т д exec. *Если в данных есть пропущ. значения, то они остаются на своих местах и служат как бы границами "подвекторов": сортировка будет *только внутри подвекторов. Напр., кейс есть 5 4 . 5 6 4, на выходе будет 4 5 . 4 5 6. *Если нужно чтобы этой "разбивки" не было и все missing сортировались в хвост вектора, к if условию в loop добавь: 'or miss(v(#i))'. *************************** SHELL's INSERTION алгоритм ****************************. *Шелл (1959) предложил, как ускорить insertion-алгоритм в ситуации больших, а также далеких от сортированности векторов. *Суть заключается в том, что значения "слева" - среди которых ищется место для вставки данного взятого значения - сканируются *через большой шаг (т.е. шаг не 1, а больший), что ускоряет отыскание места для вставки. Когда все значения так вставлены, и вектор *стал ближе к сортированности, процедура повторяется с меньшим шагом, потом еще с более меньшим. В конце делается с шагом 1 (т.е. *обычный insertion-алгоритм, когда вектор уже почти отсортирован). *Например, есть вектор из 13-ти значений. Сначала берется такой шаг, чтобы вектор разбился на подвекторы по 2 значения, *отстоящие друг от друга на шаг: 13/2=6.5, т е шаг будет 6. Это значения с номерами 1-7, 2-8, 3-9, и т.д. *В этих подвекторах - между этими значениями - и идет insertion сортировка. Затем берется разбивка, где по 4 эл-та в подвекторе, *отстоящих друг от друга на шаг 3 (13/4=3.25). Это значения с номерами 1-4-7-10, 2-5-8-11, 3-6-9-12. Сортируются эти подвекторы. *Под конец сортировка проводится над всем вектором. *Сортировка Шелла не является "устойчивой", как и "онлайн-сортировкой". vector v= v1 to v13. loop #n= 1 to 13. /*Будем делать "разбивки" вектора (разбивок будет в действительности меньше 13, т к закончим раньше чем n дойдет до 13) -comp #n= 2**#n. /*по n элементов в подвекторе: при первой разбивке n=2, при второй n=4, при третьей n=8 и т д -comp #step= trunc(13/#n). /*Элементы в подвекторе - не смежные, а отстоят друг от друга на шаг step, ктр есть след-но и число полных (с n элементами) подвекторов -if #step=1 #n= 13. /*В том случае если полный подвектор - единственный, берем в качестве его замены весь вектор -loop #sv= 1 to #step. /*Для каждой "разбивки", пускаем для каждого ее подвектора insertion-сортировку в нем, sv это порядковый номер подвектора *****Отчеркнутая далее секция - это insertion алгоритм, нюанс только в том что все делается с шагом не 1, а step. - loop #ins= #sv+#step to #sv+#step*(#n-1) by #step. - comp #val= v(#ins). - loop #i= #ins-#step to #sv by -#step if v(#i)>#val. /*[для убывающей сортировки: < вместо >] - comp v(#i+#step)= v(#i). - end loop. - comp v(#i+#step)= #val. - end loop. *****. -end loop. end loop if #step=1. /*Если подвектор - единственный, это сигнал кончать работу, сортировка сделана exec. *Если в данных есть пропущ. значения, то к if условию в 'loop #i' добавь: 'or miss(v(#i))', и они будут отсортированы в хвост. *Без этой вставки при наличии пропусков алгоритм даст несуразный рез-т. ************************ HEAPSORT алгоритм ******************************. *Это быстрый алгоритм для больших векторов. Он не "устойчивый". *Работа состоит из 2-х этапов. На 1-м вектор сортируется в частично сортированный вектор, наз. пирамидой (heap). *На 2-м этапе пирамида досортировывается в результат. *Пирамида это иерархическая структура типа "мать с 2-мя дочерьми", где элемент-мать больше чем ее дочери (тогда пирамида наз. нисходящей) *или мать меньше чем дочери (тогда пирамида наз. восходящей). Пирамида хранится как вектор, где каждому элементу на позиции p *отвечают дочери на позициях 2*p и 2*p+1. Пример нисходящей пирамиды в виде рисунка и в виде вектора: * 10 * 8 6 * 3 6 5 1 * 3 2 3 5 4 * *позиц 1 2 3 4 5 6 7 8 9 10 11 12 *знач 10 8 6 3 6 5 1 3 2 3 5 4 * *На обоих этапах алгоритм один и тот же, обменный: сравниваются эл-ты, находящиеся на материнских позициях, с их дочерьми, *и если окажется, что одна из дочерей больше (при восходящей пирамиде - меньше) чем мать, она меняется с ней позицией. *Разница между этапами в распорядке алгоритма: на 1-м этапе проверяются подряд все матери, и это приводит к пирамиде, где *1-й эл-т - корневая мать - наибольший (наименьший) из всех. На 2-м этапе эта мать изымается из обмена, и оставшаяся часть вектора *подвергается пирамидизации, опять корневая мать изымается и вектор укорачивается, и т.д.: вектор все укорачивается и кроме того *с каждым разом все меньше нуждается в досортировывании. *Хотя это кажется на 1-й взгляд парадоксом, но к сортированности по возрастающей ведет построение как раз нисходящей пирамиды, *а к сортированности по убыванию - восходящей пирамиды. vector v= v1 to v13. comp #end= 13. loop #stage= 1 to 2. /*Две стадии: на 1-й создаем пирамиду, на 2-й сортируем пирамиду -loop #p= trunc(13*#stage/2) to 1 by -1. /*На 1-й стадии p - это позиция матери: просматриваем всех матерей (т е все эл-ты от середины вектора и левее) /*На 2-й же стадии значение p пробегает все эл-ты от конца вектора налево - do if #stage=2. /*На 2-й стадии есть отличия от 1-й: - comp #temp= v(1). /*Обменяем 1-й элемент (самую старшую мать) на последний (самую правую дочь) в векторе - comp v(1)= v(#p). - comp v(#p)= #temp. - comp #end= #p-1. /*И "исключим" из вектора последний элемент - он уже сортирован: самый большой (меньший, при убыв сорт-ке) на данный момент; /*так что на 2-й стадии длина несортированной части вектора будет все уменьшаться - comp #p= 1. /*За мать же всегда исходно берется 1-й на данный момент элемент вектора - end if. *****Отчеркнутое это сопоставление/обмен матери с дочерью ("sifting"="percolating"). - loop #i= 1 to 13 if #p*2<=#end. /*Будем повторять, пока у матери есть дочь (т е позиц p матери такова, что 2*p не выходит за конец вектора) /*i нам не понадобится (ввели только чтобы не задавать SET MXLOOPS) и циклы закончатся раньше чем i=13 - comp #c= #p*2. /*Позиция дочери (левой) - do if #c+1<=#end. /*Когда дочерей две - if v(#c+1)>v(#c) #c= #c+1. /*то, если правая дочь больше [меньше, для убыв сорт: < вместо >] левой, за сравниваемую дочь берем правую - end if. - do if v(#p) вместо <] матери - comp #temp= v(#p). - comp v(#p)= v(#c). - comp v(#c)= #temp. - comp #p= #c. /*так что теперь мать находится на позиции дочери (так что дальше будем сопоставлять ее с дальшейшими дочерьми, бывшими прежде ее внучками) - else. /*Если же мать больше большей [меньше меньшей] дочери, выходим - break. - end if. - end loop. /*чтобы взять для процесса сопоставления другую мать *****. -end loop. end loop. exec. *В присутствии пропущ. значений сортировка будет с ошибками. Чтобы этого не было, а пропуски отсортировались в хвост вектора, *к условию 'if v(#c+1)>v(#c)...' добавь: 'or miss(v(#c+1))', а к условию 'do if v(#p)0. /*r это позиция для считки в векторах s и e: значения там - начало s и конец e входящего подвектора; работаем, пока в векторе s (и e) есть что-то записанное -comp #s= #s(#r). /*Координату начала скопируем, т к она будет изменяться (тогда как e - пока нет) -loop #w= #w to 13 if #s<#e(#r). /*Работа с входящим подвектором состоит в том, что будем повторительно раделять его правое крыло (т е его разделим, потом разделим его правое крыло, /*потом правое крыло правого крыла и т д, пока есть что разделять, т е пока конец дальше начала) /*w же это позиция в векторах s и e, куда будем писать координаты получающихся левых крыльев, ибо ими будем заниматься позднее ****Отчеркнутый фрагмент - разделение подвектора****. - comp #p= trunc((#s+#e(#r))/2). /*Выбираем pivot эл-т: пусть это будет середина подвектора - comp #temp= v(#p). /*Переносим pivot-элемент в начало разделяемого подвектора (убираем этот эл-т, в сохранное место) - comp v(#p)= v(#s). /*ну а начальный эл-т ставим на бывшую позицию pivot (обмен) - comp v(#s)= #temp. - comp #p= #e(#r). /*p теперь будет позицией для приема перекидываемых на правое крыло элементов (пока берем ее как конец подвектора); (в конце p станет итоговой позицией pivot эл-та) - loop #i= #e(#r) to #s+1 by -1. /*Делаем перекидку: берем по элементу в подвекторе (pivot эл-т не трогаем) - do if v(#i)>v(#s). /*Если эл-т больше [меньше, для сорт-ки по убыв: < вместо >] чем pivot эл-т, то - comp #temp= v(#i). /*вставляем его на принимающую позицию в правом крыле - comp v(#i)= v(#p). /*(обменивая на эл-т, который оную занимал) - comp v(#p)= #temp. - comp #p= #p-1. /*И сдвигаем принимающую позицию на 1 влево - end if. - end loop. /*Берем след-щий эл-т подвектора для сравнения с pivot и перекидки - comp #temp= v(#s). /*По окончании перекидки элементов в подвекторе вставляем на принимающую позицию pivot эл-т - comp v(#s)= v(#p). /*(обменивая на эл-т, который оную занимал) - comp v(#p)= #temp. /*Крылья готовы: все эл-ты справа от pivot эл-та (его позиция p) больше [меньше, при сорт-ке по убыв], а слева от pivot эл-та - не больше [не меньше] него ****. - comp #s(#w)= #s. /*Позиция начала левого крыла: выписываем ее в хранилище - comp #e(#w)= #p-1. /*Позиция конца левого крыла: выписываем ее в хранилище - comp #s= #p+1. /*Позиция начала правого крыла: на след витке разделим подвектор, ктр нач отсюда и кончается на позиции e -end loop. /*Переходим к его разделению end loop. /*Когда больше нечего разделять, берем след подвектор согласно очередным в хранилище координатам s(r) e(r) exec. *В присутствии пропущ. значений сортировка не нарушается, но позиции пропусков сдвигаются. Чтобы этого не было и *все missing отсортировались в конец вектора, к 'do if' условию добавь: 'or miss(v(#i))'. *Хотя pivot эл-т можно выбирать в (под)векторе произвольно, от его выбора зависит скорость. *Если входящий вектор уже частично сортирован, то выбор pivot эл-та у края (под)вектора существенно замедляет работу. *Поэтому оптимальнее и универсальнее всего брать pivot из средней части (под)вектора, как делает синтаксис выше. *Или можно выбирать его случайно.