Сортировка внутри наблюдений: некоторые популярные алгоритмы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 | ****************************************************************************************** * СОРТИРОВКА ВНУТРИ НАБЛЮДЕНИЙ: РЕАЛИЗАЦИЯ НЕКОТОРЫХ ПОПУЛЯРНЫХ СОРТИРОВОЧНЫХ АЛГОРИТМОВ * ****************************************************************************************** *Кирилл Орлов. 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)<v(#i-1). /*Если в данном варе значение ниже чем в предыдущем [для сортировки по убыванию - выше чем в нем] - comp #sorted= 0. /*То, пометив что сортировка требуется - comp #temp= v(#i). /*Обмениваем наши два вара значениями (temp это временное хранилище одного из значений) - comp v(#i)= v(#i-1). - comp v(#i-1)= #temp. - end if. -end loop. end loop if #sorted. /*Процедуру (итерации) прекращаем, если, просмотрев так все вары (пары), не обнаружим больше необходимости сортировать exec. *Если в данных есть пропущ. значения, то они остаются на своих местах и служат как бы границами "подвекторов": сортировка будет *только внутри подвекторов. Напр., кейс есть 5 4 . 5 6 4, на выходе будет 4 5 . 4 5 6. *Если нужно чтобы этой "разбивки" не было и все missing сортировались в хвост вектора, к 'do if' условию добавь: 'or miss(v(#i-1))'. *************** BUBBLE (=EXCHANGE) алгоритм, НЕ-УСТОЙЧИВЫЙ ВАРИАНТ ******************. *Этот вариант синтаксиса bubble-сортировки несколько быстрее предыдущего, но он не "устойчивый". *Тут пару варов составляют не смежные вары, а традиционные попарные "сочетания". vector v= v1 to v13. -loop #i= 1 to 13-1. /*Берем один вар - loop #j= #i+1 to 13. /*Берем ему в пару другой вар - do if v(#j)<v(#i). /*Если значение в во 2-м меньше чем в 1-м (для сортировки по убыванию - выше чем в нем) - comp #temp= v(#j). - comp v(#j)= v(#i). /*Обмениваем наши два вара значениями (temp это временное хранилище одного из значений) - comp v(#i)= #temp. - end if. - end loop. -end loop. exec. *Если в данных есть missing, сортировка будет неправильной. Во избежание этого *к do if условию добавь: 'or miss(v(#i))', и все missing отсортируются в хвост вектора. ******** SELECTION (=EXTREMUM) алгоритм, ВАРИАНТ С ОБМЕНОМ (НЕ-УСТОЙЧИВЫЙ) *********. *Selection-алгоритм ищет в векторе экстремальное значение (минимальное или максимальное - в зависимости от *того нужна ли сортировка во возрастанию или убыванию) и перемещает его в начало вектора, *затем это же повторяется на оставшейся части вектора - и так далее пока весь он не отсортируется. *Это самый интуитивно понятный алгоритм сортировки. *Данная версия - не "устойчивая". Среди простых алгоритмов Selection алгоритм быстрее чем bubble-алгоритм, *но медленнее чем insertion-алгоритм. *(Хотя здесь напрашивается использование встроенных функций MIN (MAX), в действительности они были бы тут *неэкономичны (при строгом подходе), т к подразумевают скрытую пробежку процессором вектора значений, - но нам и так *придется делать пробежку, чтобы узнать позицию данного min или max значения. Так что получилась был лишняя пробежка). vector v= v1 to v13. loop #i= 1 to 13-1. /*Берем по значению -comp #m= #i. /*m это будет позиция наименьшего (наибольшего, при сорт-ке по убыванию) значения; допустим пока что это и есть взятое значение -loop #j= #i+1 to 13. /*Пробегаем оставшиеся справа значения - if v(#j)<v(#m) #m= #j. /*сравнивая их с якобы-наименьшим (наибольшим) и запоминая номер из них меньшего [для убыв сортировки - большего, т е > вместо <] -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)<v(#m) #m= #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)<v(#c). /*Сравниваем мать и большую [меньшую] дочь и обмениваем их местами, если дочь больше [меньше, для убыв сорт: > вместо <] матери - 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)<v(#c)' добавь: 'or miss(v(#c))'. ************************ QUICKSORT алгоритм *****************************. *Это быстрый алгоритм для больших векторов, быстрее чем heapsort, но занимающий больше памяти (т.к. алгоритм пишет себе памятки). *Он не "устойчивый". Идея его в том, что вектор все более дробно сортируется по принципу "разделяй и властвуй". Все значения, *большие некоторого выбранного значения, собираются по одну сторону от него, а все значения, *меньше него, собираются по другую сторону от него. В каждом из этих двух подвекторов опять выбирается *некое значение в качестве разделяющего, и процедура повторяется, - и так далее. Т.о., сущностью метода является *разделение (под)вектора на левое и правое крылья, относительно произвольно выбранного pivot-значения. *Существует целый ряд версий алгоритма, вот одна. vector v= v1 to v13 /#s #e (13). /*Векторы s и e - для хранения координат подвекторов (только левых крыльев), получаемых в рез-те разделения больших подвекторов recode #s1 to #s13 (else=0). /*Страхуемся от перенесенных значений с предыдущего кейса, ибо имеем дело со скретчами comp #s(1)= 1. /*Начинаем с comp #e(1)= 13. /*подвектора, ктр есть сам вектор: s - позиция начала, e - позиция конца comp #w= 2. /*Запись координат дальше начнем, стало быть, отсюда (w это позиция для записи в векторы s и e) loop #r= 1 to 13 if #s(#r)>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 из средней части (под)вектора, как делает синтаксис выше. *Или можно выбирать его случайно. |