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 из средней части (под)вектора, как делает синтаксис выше.
*Или можно выбирать его случайно.