Сортировки: вставками, выбором, слиянием, быстрая, пирамидальная, подсчётом, поразрядная — авторское изложение

ru · official · sha256:6536cafab93ab20f6c8e2db14e3c20ec5d1132a423048b28dc7f9251b2516f8cRU

§1. Порядок, устойчивость, работа на месте и нижняя оценка Сортировка есть перестановка элементов последовательности, после которой она упорядочена неубывающе по ключу. Требование ПЕРЕСТАНОВКИ существенно: описание, выдающее упорядоченную последовательность иного состава, задачи не решает. Устойчивость: сортировка устойчива, когда элементы с равными ключами сохраняют взаимный порядок. Устойчивость есть свойство ОПИСАНИЯ, а не задачи: у одной задачи бывают устойчивые и неустойчивые варианты, и выбор между ними осмыслен только при равных ключах и различимых элементах. Работа на месте: описание работает на месте, когда дополнительная память не зависит от длины входа либо растёт не быстрее логарифма. Соглашение о логарифме названо прямо, потому что глубина рекурсии обычно считается допустимой, а буфер длины n — нет. Инверсия — пара позиций i < j, у которых ключ в i больше ключа в j. Число инверсий есть мера неупорядоченности: сортировка вставками делает ровно столько перемещений, сколько инверсий во входе, и потому приспособляема к почти упорядоченным данным. Нижняя оценка для сортировок, основанных на СРАВНЕНИЯХ: всякое такое описание в худшем случае делает не менее логарифма по основанию два от n факториал сравнений, что есть величина порядка n·log n. Доказательство ведётся через дерево решений и остаётся в источнике. Оценка не относится к сортировкам подсчётом и поразрядной: они читают структуру ключа, а не только результат сравнения, и потому оценке не подчиняются — их стоимость зависит от диапазона и длины ключа. Куча — последовательность, для которой при всякой позиции i ключ не меньше ключей в позициях 2i + 1 и 2i + 2, когда те существуют. Такое размещение задаёт двоичное дерево без указателей и есть основа пирамидальной сортировки.

Referencing norms: AnswersHere, f-17ba9173fe40995736f4c3b9, f-1be4924c5db7d3cf453740e7, f-1ef5bfe772261470faff8ccc, f-243e99caceec53b86ab0908d, f-41f018b7488fd75c8696c70d, f-421888c6faa99d63d025caf0, f-428813b8a9f4730783cce79b, f-45c06f61628661ffa7a31af3, f-4d31ea5e38c781a75cc582d5, f-57aa14b7df9bb45aa6e575d5, f-5d7a1307c97c6cc4cd3bf50e, f-619a7482cc42d46ec7041878, f-61c448f7538006d7fd2cd348, f-62c11abbb45fd44c50c64e98, f-69f86138460b704821842bd8, f-6b7ee457a89873e7dc99439e, f-81241d559cf1f744de1ccc1a, f-9c93ad0bad037b24609467b2, f-9d1231cb6c26b10770021fa9, f-a04e24f494cdbddd2c11dc5e, f-a9ad47ff05c6ec1ab6c8bace, f-ab3726af653696ca2fa9c7af, f-b109112383527ec5ad6a5ece, f-b16f813d058eca00d4fc646a, f-bf7c0df520264cadd12ffee8, f-c15b328fc2df7b80c6ba4f3e, f-c865426e48a5ca85be327220, f-cf7d595e6a15a8b02a30f18c, f-d2826305a72fbb95e6f430f3, f-de8c99231676cf1d962423d0, f-dedbe2c519939e6568f38be5, f-e52c557942b060aea732e336, f-e731bcd8447ec22803c5a7b8, f-f3a5fe571f830776a730bed0, f-f42aed7e1f80a2087f1dafec, f-f60fe3c147ff3ca40de592c1

ru · official · sha256:2893e1af00678bf9a4202a199608163377bc594ffee79893994d815ebd7dee00RU

§2. Сортировка вставками Задача: упорядочить последовательность. Вариант — последовательное включение очередного элемента в уже упорядоченное начало, сдвигом вправо больших элементов. Начало последовательности из одного элемента упорядочено тождественно. Далее для каждой следующей позиции текущий элемент откладывается, элементы упорядоченного начала, строго большие отложенного, сдвигаются на одну позицию вправо, и отложенный элемент помещается в освободившееся место. Сравнение СТРОГОЕ — сдвигаются только строго большие элементы. Именно это и даёт устойчивость: равный элемент не сдвигается, и отложенный встаёт за ним. Инвариант: перед обработкой позиции i начальный участок длины i упорядочен и состоит из тех же элементов, что исходный участок той же длины. Мера убывания — число необработанных позиций. Крайние случаи: пустая последовательность и последовательность из одного элемента упорядочены тождественно; уже упорядоченный вход даёт лучший случай — n − 1 сравнений и ни одного сдвига; обратно упорядоченный вход даёт худший — порядка n в квадрате сдвигов. Оценка: число перемещений равно числу инверсий во входе. Отсюда приспособляемость: на почти упорядоченных данных описание близко к линейному, и это его главное практическое достоинство.

Referencing norms: f-01db7d81eefbc8004252085a, f-0241618454270184ea27887d, f-0b57dce1862276eb05404edd, f-0ca0f30f3bb1606f2e7c16d6, f-0d3ab4b418a07b3f91bd39d7, f-0e128b96f7836311baaa9a52, f-1249aee1a839d23317129ed4, f-128b2ec66c6298f92317a6a1, f-1683649c003d0cdd7149c480, f-1951198e3ef1a3d481e65135, f-1bdc499038d47c964e7e2529, f-1e4267cdd35f12c8e40f3ee4, f-1f61874f828318ab9e6aaec1, f-205eb81317ded7f8b3167986, f-208ca43ab51dfa377980c188, f-251376a33ce0c18d39854ffe, f-26417f61cff4d6e4c1471a6c, f-271a91be7459eb19a194fff7, f-279ae0f133f39f5c743aca49, f-2800e406643956264a2e1bce, f-2a91dafc630c0c2d41cfa0a2, f-2d7cf3e7da30c23f6217b230, f-2fd2a56aa8a9d4ea64e83d8b, f-3a0ba5d633dde45b0138f1a4, f-3b4022ab256462a86063e766, f-3b727d3863dbc8e2e57e5df9, f-3de251314ad347cedd5dd501, f-3ef0b068c4c53fce48daedf4, f-3f8ce7237cffa90b5d48b348, f-40628a1f659571c47dc42cbc, f-40d75c640feed0cc9724c15c, f-4aec05ce805c7616378551ad, f-4bc5f20d4d934c26050f91dc, f-4ce89b25ff479f046262b71b, f-4fa74065175ff65da4b614df, f-519c816863d93dfa0a6503bf, f-5331a953dfba7ec39da60ede, f-558026ed2171b367ef05142f, f-563406e8731d70ceb5c0fe9d, f-57a94070bed801964779330e, f-61a788b622b6cac54d15bf4c, f-62b9c8dfe1244f4ddd6bd9e1, f-683b34d4c17062727acc21a8, f-69aa14bec55cd391464620d3, f-709de7855279c75ae25a3775, f-799c7a63df1ea3cae822d206, f-7bf5e6c374829bc70e76251e, f-7c4064c3e956d41ea9d7ff9a, f-7cebd1eb31907c972e973f79, f-823b703352767bd02f6311df, f-84432777d6de09674c9b4129, f-8b4a7e869f19e91c2e89b041, f-8e70437d7f52e0a17399564b, f-8ee4d8157979655cc3192043, f-927aeb42768bc28cd2b46269, f-93a88d983954bb83c6b203df, f-93c99b31c33095f95fc2dc02, f-99e150130e42c2c35da1faad, f-9bd04a90bff0cca3f1b13c4c, f-9c08105aeffef7b8d9214ebb, f-9da722cfdfd600899a177640, f-a293de8840286e6f41957473, f-a45c11c5c9bc9d700c939a37, f-a52a9eb47728788aea627fa3, f-a85f34c68f6ad2d3abd1e6a5, f-a8978aefc2beaa7169c4a80f, f-ab701ec5c81877d0c87e417f, f-abf67531474950128525e1cb, f-ad979c5914155246c988e8b8, f-aefb184ba997c10f5cd1e1cb, f-af1bc437d9884b89861a0425, f-b11835d7faa57b4bdcf812dc, f-ba21419d961d55eb878d06d1, f-ba303f4c99d6b57431fc76bf, f-be34e33e7b7991be7a948d6c, f-c06bf98530108f2d75a6e586, f-ca0cae253c6ad8c8ad91c54a, f-d478b4bd7ccac845d1b0ef63, f-d4c11b4139395362e4738618, f-d643ee9a2a72197b63eef8e4, f-dae1c31f546ed9725a21c0a0, f-e40e7163c54ea3184eec4e78, f-e540c16ede33466c87a4e535, f-e58c27303896925d707a00d3, f-e8b9a7ccb09f95a94ef6e9d6, f-e957b8816bb3b7c36b857ff2, f-eb1d109c75601c3de5595e3c, f-ecb0defbd3bb598c50e3a601, f-ecb80b6cf1de6a24158b0838, f-eda1c6448c0166660964ab14, f-f133928016232a3fba408ea8, f-f1ba313291d5828a77d99f9e, f-f2514902bbaaed78765166c1, f-f98e5298385723c4b69e73c2, f-f9f90502d9f8cf4863855edc, f-fa30c7cba8ad82c38969a87c, f-fbaee62e264cd6f0efcf3f97

ru · official · sha256:f97e57360aedeeaf892064a8ef6229cee9a2733abfd70432339852528e943524RU

§3. Сортировка выбором Задача та же. Вариант — повторный выбор наименьшего элемента из необработанного хвоста и обмен его с первым элементом хвоста. Для каждой позиции i от нуля просматривается хвост от i до конца, находится позиция наименьшего элемента, и элементы в позициях i и найденной обмениваются. Обмен разрывает устойчивость, и это существенное отличие от §2: перенос дальнего наименьшего элемента через равные ему переставляет равные между собой. Вариант со сдвигом вместо обмена устойчив, но перестаёт работать за постоянную дополнительную память в прежнем смысле; настоящее изложение фиксирует вариант с обменом и говорит о его неустойчивости прямо. Число СРАВНЕНИЙ у этого описания одинаково при любом входе и равно n·(n − 1)/2: приспособляемости у него нет вовсе. Число ОБМЕНОВ, напротив, не превосходит n − 1, и это единственное, ради чего вариант выбирают: он делает наименьшее возможное число перемещений среди простых сортировок. Инвариант: перед обработкой позиции i начальный участок длины i упорядочен и содержит i наименьших элементов последовательности целиком.

Referencing norms: f-05a98c9494018ddaa9917d06, f-0a234d7ef7f1546db1001493, f-1018e247d59be050546f7257, f-16130230d65dab101920c546, f-17a482dd05c1025cf7bb3d67, f-1deebed507a72e2760aba4d9, f-2044ccd0938455ade549f1e0, f-23635cb91de52d3fe161fa33, f-246940153978f38c63a55d37, f-2b9f39880d0be0badf6f3b01, f-2d880bd574be6b7af41d8b29, f-2f0d8da5970b0f69f41f4836, f-309ba9f4d8cdb18d6cf0768a, f-30f4200c9984be621aa378d5, f-31344b3cb88d0a449b5f9f18, f-34ecda098beca0ce9da8d96f, f-37d7ccafdcb621840fc998ac, f-39db17a3f5b6fd38c4f872f1, f-3ac48736909c5d706349474d, f-3d488889b6fa584c9420ee37, f-3dca6127580c82e2a88a88ab, f-4a1a4ad4d8a8404998caaccd, f-4e6e5263cf31ae6ad3126fef, f-5331af641a33a32226e2ac80, f-5bb1a752b74ccdf3d45d12eb, f-5bd4f1a491715c0f59cf4de9, f-5df765338065b666e7b2b239, f-61a2f5f8d71641d65c997b09, f-6200315c8384602b8906854e, f-67f81759fabce4c2f0bfa793, f-6921d2ecc62b828c0c6c76d2, f-6b5c18633c50f060963ae226, f-6d6e56ec21e883782a0f9a2f, f-6f1c1ecec19a3a9c6732fd78, f-73eb475b0ba04423fc15b855, f-7703dc79680352b22b632491, f-78662c5ceb565e5079149e63, f-7a47626fb0367a57ba23420c, f-7a5be5e4a0709c0396eb53c1, f-7a6626a9ac6c19fada385931, f-7ba813da767b326d96eaf375, f-7f82b11e67a602428afa384e, f-81da76b4e578c5535700e1cb, f-829f1b4069693fe160ad66ae, f-839b26a2bcd1cbbe5fa0e076, f-90b21e3ad2ec17c7b785d6ce, f-94d19a1fbf51ff68f6bc3655, f-97f26f4b0447718495b4fb71, f-9d69966de1090eabb457e2ba, f-a2fdc631352e9d563004d9b2, f-aac461b83d320f53a5dc8bdd, f-b0357321c49da5bd8de1043a, f-b139b2a21aca1f9e3bf6c8f1, f-b50cfc72aae280b5e64afee7, f-b740dc121184ab692b49ee33, f-be0f430045147125ed7697c9, f-becc1439195372b025b14943, f-c25e8855d86c2bae80f24de8, f-c669f52f5286588aa62766a4, f-c6b7fd45dbba4d2c0dcaf91e, f-c6e172d1889207ede3d2b7ae, f-c818030ce135be551b3d2cad, f-c87ce7ac7e3d6bdac61f1148, f-ccdba80d07fe8658814e135a, f-d06b7bb636fabaf6a0d39158, f-d3fa61c0c5fa8384c13aa294, f-dec741c0c1c9288f8604a0e9, f-e0cf7b83d2e792b0b8bdd796, f-e42313ece4cf0ae1d2960fbc, f-e505e59b2fa58d3f0087d32c, f-e7259b543a59e170dffabc34, f-e80f9af868e5374c7a05543d, f-ecdecf0ccb537c82a72056f3, f-ee7cc555c2b2fdd9b583ded3, f-f2cf132b4f10324dc93edbaf, f-f33dcdcfdddaef583cde257b, f-fb612671095aeceafb888a11, f-fc3b1b0d17af02923e284549, f-ff1e9f5f2a8adbc826cba215

ru · official · sha256:2a7bcaa39bd3836a7516d34f4d6fccabb0bc56120c71520a3a1fef724da2cab0RU

§4. Сортировка слиянием Задача та же. Вариант — рекурсивный, сверху вниз: последовательность делится пополам, половины сортируются тем же описанием, результаты сливаются. Слияние двух упорядоченных участков ведётся двумя указателями: сравниваются текущие элементы участков, меньший переносится в выход, его указатель сдвигается; при исчерпании одного участка остаток другого дописывается. Сравнение при переносе НЕСТРОГОЕ в пользу левого участка — при равных ключах берётся элемент левого. Именно это и даёт устойчивость; вариант, берущий правый, устойчивость теряет, оставаясь верным. Основание разделения — то, что слияние двух упорядоченных участков даёт упорядоченный участок из тех же элементов. Основание завершения — рекурсия на строго меньших участках вместе с базой длины не больше единицы. Мера убывания — длина сортируемого участка. База рекурсии обязана быть названа: участок длины ноль либо один упорядочен тождественно, и без этой базы рекурсия не завершается. Крайние случаи: нечётная длина — половины различаются на один элемент, и это не требует особого разбора при полуинтервальной записи границ; уже упорядоченный вход не ускоряет вариант — число сравнений остаётся порядка n·log n. Оценка: время порядка n·log n при любом входе, дополнительная память порядка n на буфер слияния. Именно буфер, а не время, есть цена варианта; слияние на месте существует, оно сложнее и в настоящее описание не входит.

Referencing norms: f-0292bfb5f618ceaef415c362, f-0319f3337e20d4fb6b963f2b, f-053856dfbda8ecd152df725c, f-125459ab467752d7cbae9b2c, f-143b41c1e9a4e47a8c2da5f9, f-14f5b02854256d97d88be070, f-16425168964683cb6d222799, f-17c784017982fe70d8453380, f-1af1a786ce0d730e499cf8e8, f-1b3f495551ccc98572f5dc93, f-1b6b8d46ee9a9698023b0f21, f-1ec5524d061f622f1ad9cc94, f-23aaf98f026714cb30d8265f, f-260cb1d98d6c3e8db2b7ab22, f-2956746291265ff8b7a74d42, f-2d215afc26fa1860b80ab158, f-2ed4251324a2faf9fa03de1c, f-307b1b045e3285f94f5c3f27, f-3147229267654dd159ee11d7, f-3521171d529520b676e30c38, f-3658c1153eab71356d5c48ba, f-37dcacd1b9d7329e2a98d18e, f-389754b46f264a843d1fefde, f-3c9d71c5af9538819c18c544, f-3e964dafe8b671fa35d4b69c, f-3eed133da4ccec8cccc32974, f-4091bebfd796b32049195b85, f-45d9597ca2734f62445a682b, f-48c30f680871113e1ba3209b, f-4aef8343f4602208f88fed0f, f-4d98bee950110bccc2241ff0, f-50fc6d76150c3ba5ab9afcdf, f-53bdd6b65d0542bd6ec87b50, f-57691605609dbf4981d79a23, f-5d343909101886d2c42bf4f1, f-5f3dc53e8d18edd8b929e248, f-608cf42f36655b6c53fe739e, f-626e38177ea8b269a6135935, f-62f931624d5523c51872ef36, f-68c51a752d2bf8a92df33ea7, f-6c6d2451486e2e1d48c5cbc6, f-6cc92b5ff04ff7d433ba58f7, f-6db5f23a39701aaea4a321d4, f-6f4697331b9d83da739c9f0c, f-72ad5fc1c9af3667d7cc91da, f-766ac585d3e45761989b7bbe, f-778012c33aa413169e68c3a5, f-7d2763af3267b44cadeff5c5, f-7fcded84c44df2f1df3529c1, f-80b42043cf77c5b5a4818e64, f-80d96e85850ca72d8f8069b4, f-81cc4f7dd7c358feb557db49, f-82ccef31cba61040e2092431, f-8372e1e4d820aac0645a63c6, f-86b9f7dffc0cee27a2dba773, f-8aff68f8e5276ecf59edcb9e, f-8b74c2d0b46793ace9acb04b, f-9462584bde93ab543bc9ed16, f-990b063d0807a0ac2164c66c, f-9b7d611d9db6b16de027a9b2, f-9bbbf910fac4d4c175e1e719, f-9dd0a006ca11d898c1fcbbbb, f-9f562442b5f299535694eaf2, f-a3a577ac6141a323e2466386, f-a4e3f30e4ba1cd98a68fd2ad, f-a85fd98f03cc6124f130044d, f-ac2d550f3d6ca23bb3f7e087, f-aeaf3140066b864be8bd4bec, f-aefa3da4d3304c5fe5c5a9ff, f-b63706728c8b4e3c487846e0, f-b6f3115085903ee392144b2d, f-b9599e04404756f860496fa9, f-c0e4de3783e09b8b9b2609c4, f-c6f9e2294c2621868aefdb64, f-c7542861e1acf75793e7fa43, f-c8ea3fa6abb4605c86961791, f-caa0a1b2732dfb784788cf11, f-cb6c7cb65dedf60e72ea9f93, f-cfc2dc646f2bfee037bde08f, f-dcf9250821ca790a44817ec9, f-dfe94f7202eb71e554881508, f-e0799585bc8d84564c6a985b, f-e6b5b8bd9bfa996a0d76faf5, f-e85b0c4993a6ff26a24a4052, f-ed9adfd90dde217f72953b9c, f-eebde3e97f03e4d4ccb947a1, f-ef1b896ddecc459014d4da77, f-ef6ad20d7949e34fc223fe9b, f-f0849768e4f14fbfdc814f39, f-f09b1c989a6757de6c98315b, f-f56d40ca6afe509e0a726ef0, f-f8430ce0a2b189546ece0c83, f-fb533d4ee12ad1d788f1d624, f-fcaa97f41db4d4d7fbb91da6, f-fe744f69b1b381a657bdd106

ru · official · sha256:f4f3b9bc9e1de4cec8a9b000afb6c2c44f7a5d333775c47e90b4e65c0f6c9e3aRU

§5. Быстрая сортировка Задача та же. Вариант — рекурсивный с разделением Ломуто по опорному элементу, взятому последним в участке. Разделение проходит участок слева направо, поддерживая границу: элементы левее границы не больше опорного. Встретив элемент не больше опорного, описание обменивает его с элементом на границе и сдвигает границу. В конце опорный элемент обменивается с элементом на границе и оказывается на своём окончательном месте. Далее тем же описанием сортируются участки слева и справа от него. Опорный элемент после разделения стоит там, где стоял бы в упорядоченной последовательности, — это и есть основание, по которому его больше не трогают. Разделение Ломуто выбрано изложением ради простоты инварианта; разделение Хоара делает меньше обменов и обрабатывает равные элементы иначе. Это ДРУГОЙ вариант, и смешивать их нельзя: у них разные инварианты и разное поведение на входе из равных элементов. Худший случай — порядка n в квадрате — достигается, когда опорный элемент оказывается наибольшим либо наименьшим на каждом шаге; при выборе последнего элемента опорным это происходит на уже упорядоченном входе. Утверждение о среднем n·log n верно при СЛУЧАЙНОМ выборе опорного либо при случайном входе, и условие это обязано называться вместе с оценкой. Устойчивости у варианта нет: обмен переносит элементы через равные им.

Referencing norms: f-018a91444f4c2a245e4920e6, f-05d93efee3da530b6fb44746, f-066a01d6d130ad03b00de51f, f-066d7ecc95b846a22b5eafbc, f-07d47eaee7d20fbd5f10041d, f-0897a2a3a992748405b5170e, f-0a8de3fbc9d669a867a3de07, f-0c26a3b4c3ce03b93be03251, f-0f6266e394856e155a3dbe67, f-0fa765d544a354bfd95fc8ba, f-142a90a8b3bc9fe571d9d165, f-1596e4237761da2f28ed8cee, f-19f2224efcebd9218620053f, f-1c4b85672ed07aedfe3d5d89, f-1cc81a631a46c1a860d4647e, f-1eba9c06f5e4635a0a53b960, f-282b5a5af914fa65aad0751b, f-2b720fe72106359e53ce8d40, f-317ea95ab0766b34153932b9, f-33131382fec82ff0b59a04ce, f-36ae528afb186a99bbfceaf9, f-375773c7944bd31613bdc8e6, f-3b786b4636c6117676682a12, f-41cc87b6f3f7e2098e59a073, f-45f692ee76fd4a1908327397, f-4e7ef654b4eff3ba9c816f95, f-4e99a4ee1f94396e95a21b22, f-510e1f88f38d9fb8d2295923, f-56070ec38a001f358d3dbd66, f-5884736f6b643d85c3658c74, f-58f17ba9083d9259095b1c9b, f-595d8ac6f5ab03393d7bcd11, f-5dc69486d2e5f51b7bc27527, f-5df529a8011b63ee4980b64a, f-60f96af6ba15583099ad0d97, f-631c901cfc3ceb8992dbaac5, f-657b3dfd7fa24beb0847c684, f-6673b8a4ebee503044b90b69, f-66eb905ac4984fbb8e6e6558, f-6713c630e7e9cfe6f6f561c8, f-67319f148c6a98f85eea7de2, f-67af4f66119e2082648a4869, f-6d89688039c579af7d969928, f-7197c58476719cfc5ffb80f2, f-73f909d3e6f2be2914e6ab88, f-761adfbc894e7fb70816897a, f-79747bb364f72c27d69cff18, f-79c596d2bfab018e9dba9b4c, f-7a910bcbfc93dffc10adb231, f-7b4e8973bd6034ad82f6d029, f-7d6527818ee3a3da89ff64ec, f-7e3b5198f9a655d39e35a912, f-8145ded896f8d9bc6abe3a75, f-82c314842c94cb7e18f7d78c, f-93d570a97f8820f2d3ab5881, f-95bf994b6d67eb74ac4cba80, f-9ae60617f9cf54a616b93bf2, f-9c12b384fd494c4257f8949d, f-9f552f79eaabd2714ae07335, f-a63e062a3cefaee1f3b02dc3, f-a750e1a9db8bdcf334804eb2, f-a8c35d0404ea51eecf5b2e8e, f-ad18088c57a1b7142b058537, f-ae7c4c84de173b343232b804, f-b002c415068a7d644ad6a618, f-b0fb9f12136c57ae6b18298e, f-b0fe0372b85b08af36a4edca, f-bac65c1901381086389cbde7, f-bba9bda0fe25ab7690b6c947, f-be65d4bbd0fcc087f85c52ea, f-c150673a0ba696ef8e52f231, f-c2d4381b7b946a84329be700, f-c2f5b9ce5d89cdb6b5a0c711, f-c3b278998dd1c5d69c1bb372, f-cb57c042fa55a38c8c3181d1, f-d15be5951568382d700eabf7, f-d2dd7f29b3bd4dee997d5d74, f-d3c976eb80653207cee7e35d, f-d638d823ce23ca793738a039, f-d6585b5a3969e28deea87c17, f-d8da7ed482bfccb6f16dc2a0, f-dac54ee8898349748b744261, f-dd9058fba148b797e7f303b2, f-df615eaa5e9ebd0661ee88f1, f-e32e5c2f63c1da4aa1243214, f-e3649ea1bbc239848a4d8db1, f-e39f1cf93b3cc07ebdfd244e, f-e636109025a1cc4037406bc7, f-e66afc1f6be5ae978ab34fd1, f-e753ee70708458790cc14c5c, f-eb8b5f000bc18462f5f2b3f2, f-ee5a6126823a37d5b3572cc6, f-eeeb67e74b32fb8bffedbc9d, f-f03704bcd271e6a7072b3e47, f-f0acb7c4f1bd570aaffb8907, f-f0f2912feecea3a34f814f56, f-f259025b49e5450a228b078d, f-f5fa4a4b56d41e99eb3cbc2f, f-f68b52e1896aab08b5962645, f-f6e5d65fdc1b80cdef4c3fa4, f-f94d33e4ff1d924a81de95af, f-fc6665cd417f9923939baf4b, f-fdd7e99ee9654d683018628f

ru · official · sha256:ae1ce12e03603e0165f2e8e76a8c5974a79a04c664e8a2cd57e399d4febd7782RU

§6. Пирамидальная сортировка Задача та же. Вариант — построение кучи за линейное время просеиванием вниз, затем n − 1 обменов вершины с концом и восстановление кучи на укороченном участке. Просеивание вниз из позиции i: если больший из потомков больше элемента в i, они обмениваются, и просеивание продолжается из позиции потомка. Построение кучи выполняется просеиванием из всех позиций от последней внутренней к корню; порядок «от последней к первой» существенен, потому что просеивание требует, чтобы поддеревья уже были кучами. После построения наибольший элемент стоит в корне. Он обменивается с последним элементом рассматриваемого участка, участок укорачивается на единицу, и корень просеивается вниз. Повторение до участка длины один даёт упорядоченную последовательность. Инвариант: хвост последовательности за границей участка упорядочен и содержит наибольшие элементы целиком, а участок есть куча. Мера убывания — длина участка. Оценка: построение кучи стоит порядка n — утверждение неочевидное, и его доказательство суммой по уровням остаётся в источнике; каждое из n − 1 просеиваний стоит порядка log n. Итог — n·log n в ХУДШЕМ случае, и это отличает вариант от быстрой сортировки. Дополнительная память постоянна: вариант работает на месте. Устойчивости нет: обмен вершины с концом переносит элементы через равные.

Referencing norms: f-01639cec58f16461b3225495, f-043241e7e09af84a6393ec9d, f-05e8ce1b9b5a46421b6248e8, f-095244dfdebd451f7b82b29d, f-0afc97e38cf63a3a42c82308, f-0b6738b3f7ffd89338977eba, f-0e8623b8caea79cce95f4d79, f-0fbc102c7f8609b10a3e4a3f, f-10fdf776969a28e496d0780f, f-12bb5f50bb3d70b8f34888e4, f-133a4b84ee3a0cdaa9669006, f-1456e937405607e6a09984f6, f-199a2df9569aba9d3c4a9fd2, f-1ea0a676d874f918880680fa, f-1fe738af930a2549388c5549, f-20e5e27b87fe354d637fb2a5, f-2184b1df0bdeaa685b6dcdf2, f-264e9e3606985b5f45de78ae, f-29567f6a79b3676d813532b7, f-2a55924b8d19e0944946301f, f-2ab0c39d3ad871ada867b8ea, f-2ef3b771e17d8990467a9e2b, f-307b0df460a2404f55550437, f-32501371216e530c932debaa, f-3986eedfd5e3f2d99786f20a, f-3b53620423645c73ac1e926c, f-3c5b0d28f755b23bf7c35a4c, f-403bed40f3ecf798d60b0163, f-4528c293870ae6fe8adfade3, f-4adb12554e01d7de09abbdc1, f-4b6756f8bc55fcdd28d6da6b, f-4ddf7b68bf99f08a1b86fe5d, f-504d178d94a5251b7a830714, f-54411efbcb0dc07a5e8aae4c, f-59f6273f82593d69f900005d, f-5ab3454fc92e0e9ffba3276b, f-5ab447157b8bc3eae06cf694, f-5db7c3990278a5ee8ae17afd, f-5ec24ea1d99372e5d32ba41f, f-60c2c84567533da6edef46d0, f-6119b2f635101f5cca963792, f-613bcd54eb4ba1c6d06c69f8, f-64301c5ed0f8f3704c5418c3, f-6546d7a2648f3e0373b6221d, f-65837664ac8e0c8b5da4fab7, f-7eebe8c792096b2228b80bd3, f-7f79ff4856dab4d968a0d469, f-7f9fd3dc84c802de10f9dc1b, f-81b3e5b58ce0bae3611c043e, f-82568e0a70632bf3742abdd2, f-84759e9679429fb2c4b2d616, f-86c033b297825e22a123152f, f-8b0c860770911ff7cddf1f0e, f-8b5f7037af74e7ecf5d93e2d, f-8be801391c83a6ccb008999b, f-8c488f776ca5a2e78b3c24d4, f-8dc74f697285bf702993f7a4, f-911359dec3311cc7794bbefe, f-95730810d699fdfa678229a4, f-9c005eeaf32f6a874861241b, f-9d101b4b889c5ab87a024196, f-a0197ee769d7963aa01e2804, f-a0f28b99a8447513895260dc, f-a322011e57e6c26e6bdad9fc, f-a7f8aa4fff329f8d5a6d7dbb, f-a8f03831da3daf971f4b2895, f-a94fe6c025a81d5a01934cb4, f-aee95fa670949af0af9bc185, f-b2d68cb56f0591b9cc1bd666, f-b2daa790df20ff9ba0979e2e, f-b540ca008d7abf9a41e09c22, f-b75830573a83f80016520d01, f-bab699040c9b95adbc06f169, f-c43043300484988b03d09443, f-c611e67086a6b8d35d47b083, f-d19849ca07d3ad2bd679d8f2, f-d502497a80ec41fdf3dd219a, f-d62b7da262d978bb31896a9f, f-d62cec56403f7c5c7ed52095, f-d87fbd4ecb38bf2edb172951, f-dbf66beed6c08780b211b133, f-df73cf76277ab614c35f9c88, f-e08dee7b6bea8dc9bdcddd8c, f-e0f476c43095670e409f8282, f-e1ef9c0663f372f6f5b04422, f-e2c71741881545e8f702fc05, f-e2d58255dfef679b6a9f68df, f-fb77e10ca6f1999a62441a8d

ru · official · sha256:c863e83ead98bd252285921fa0b1ccefbbf4357a2adc6fa7da0a06a4555f3cf3RU

§7. Сортировка подсчётом Задача: упорядочить последовательность, ключи которой суть целые из известного диапазона от нуля до k − 1. Вариант — подсчёт вхождений, накопительная сумма, обратный проход по входу. Заводится таблица счётчиков длины k, заполняемая числом вхождений каждого ключа. Затем счётчики заменяются накопительными суммами: значение при ключе становится числом элементов с ключом, не большим данного. Наконец вход проходится СПРАВА НАЛЕВО, и каждый элемент помещается в выход по позиции, на единицу меньшей соответствующей накопительной суммы, после чего сумма уменьшается на единицу. Обратный проход существен: он и даёт устойчивость. Проход слева направо при тех же счётчиках переставляет равные элементы в обратном порядке; это ДРУГОЙ вариант, и он не устойчив. Сортировка подсчётом не основана на сравнениях, поэтому нижняя оценка §1 к ней не относится. Её стоимость есть n + k, и при k порядка n это линейно; при k, много большем n, вариант неприменим — память под таблицу и есть его предел. Крайние случаи: пустой вход — таблица счётчиков заполнена нулями, и выход пуст; ключ вне объявленного диапазона есть нарушение предусловия, а не ошибка вычисления.

Referencing norms: f-007b90bc2dcb2efdffec2ad2, f-06e79c13f89acf841ebf7200, f-08e34ccc5868743a8cfa2514, f-11392345161cd8ab6a58414d, f-12cf65f841c9b956811eba1e, f-13f00c64ab3bb15a73526ece, f-14c368fb8b36b9f150f854a0, f-1575c3c14c1df547c206045b, f-198f6b17be99de64c084b476, f-1d434af1c71f49ebda96fd94, f-1d4f21517398af859dd66129, f-1e6e5497253a1bc43b7d7020, f-20edc0cc5bc2b1cf40334543, f-22faf0f692a2ea45a54013d0, f-26058682b9514cd43bc16b0a, f-2b10fb8c48cfc67d8f629e58, f-32402e257b616997a8e5fc41, f-3271ac22aeac445ee847282f, f-33b942b1ff8bc314b7fee9c2, f-37f2599275320f30c50518f5, f-38758b6e6b1585bd92920c8a, f-38f3ceceb983ed8d08db5521, f-3bd9a25dff0d0332a17f526d, f-3c268b49bc560b9ce6edc49e, f-3fce7da9c3f76f98554b0700, f-43524adac0c6f5d705c14923, f-4685492347d1bfa307d9c4b8, f-487c3b005ec4eccaa35e5a38, f-48fa620ca76ba96860a76ec8, f-49aaf0ba33f2a3f1c8257d90, f-4a6bf49d47e65b3cc72192ee, f-54a2142b293b85566a97dc76, f-603b3ba7d8115fe4393b4ed2, f-61b78413cb31eb0ef3823f5a, f-61cd72603f7debdc0a821576, f-62bbb2bc74d5e21fea4618aa, f-650be54d49be602e17357736, f-66bd998c23d6e798086d433d, f-686d74136a70f6634839e66f, f-6cb8435001fbd07ce1c84bef, f-6fa22daae5932fd1c65ccba8, f-741e7a852560a8a15d6b7cef, f-7ac656da5535586a7aba3700, f-7d7af1c1b54074821279f796, f-7ddfd789793d71683029d1e3, f-83f0ec01f5f69f16d6134bb2, f-845e369017a71afcd992526f, f-86417638badf6e595b1fafa4, f-87c6c7b7135357f86a958963, f-885df0c1269a8f2c16cddde5, f-8a73e666efa94302798e6545, f-8caf6a925d70a46722a11da7, f-9e2bcceae7d4074aa3803c38, f-a3d1b484ca67d9b2f9015543, f-a47647be6656a936937cd56f, f-aadfc9061432c6eafd77348d, f-ab8b69b4c472d5cb66d8cf1c, f-ac5ac03bcfb6ded016399d54, f-ad8dd3a19f75191212722d8d, f-af092b45e2a161de5e38def1, f-af870aabe5b7d963024fd692, f-b2303a043833bc267009212e, f-b473cfb40bbf4fefbf3e5773, f-b4ea7b93ac9ffe598692490e, f-bb7f5d106df0c3d6dd1233ee, f-be600a7bf226285e9eac62d6, f-c0ccb1ad561cd5844c5275dd, f-c2e9652d765c5d8628f50b5c, f-c87e63d6692c0c0360cac505, f-cb1464719a8aa7a9f27fd4d0, f-cb28390a309108dd9a6a3de8, f-cbe453e7e9c52660d425112f, f-cf86b696a54115e769703dc2, f-d0bb35b3b0c299f0b2282340, f-d0d298f334d4761608fe6d68, f-d256db9a76ddaba217e1e83d, f-d43b635e003c852b85684500, f-d66f8569eb1340456e934b57, f-d675c0268f164b99cbde960d, f-da1d676c8e27cac0ad738abe, f-da52a6f567603b2cdca5dd99, f-db486203b5ba1aed7f71fb14, f-dc00e6393f305fce8b95660a, f-e34e6be01f3e0f640d6f9608, f-e45151db077a38da9536681b, f-e5328e066f5f2bd20127e78a, f-e5797d1642c08a4bbca8f1fd, f-e57df8ab2a1b4abcbf50e185, f-edc07a584e89e042af9b0730, f-f528ae4cda69e9043d70e71f, f-f6176cab9d7cda6f93a9729a, f-f9425e59d4cc2c7d337ddd10, f-fc439973370b7e414fd4d32a, f-fcc6153d877aa22111c829dd

ru · official · sha256:56f21de10b601ac95095b2cfe46a6ed518d7be3e2a4bc193fde3309bfe640192RU

§8. Поразрядная сортировка Задача: упорядочить последовательность, ключи которой суть целые фиксированной длины d в системе с основанием b. Вариант — от младшего разряда к старшему, с устойчивой сортировкой подсчётом на каждом разряде. Разряды обрабатываются от младшего к старшему; на каждом разряде вся последовательность сортируется устойчивой сортировкой по значению этого разряда. По исчерпании разрядов последовательность упорядочена по всему ключу. Устойчивость вспомогательной сортировки — не удобство, а УСЛОВИЕ ПРАВИЛЬНОСТИ: без неё порядок, достигнутый на младших разрядах, разрушается при обработке старших. Это главное, что теряют изложения, называющие поразрядную сортировку «сортировкой по цифрам». Инвариант: после обработки разрядов от нулевого до j последовательность упорядочена по числу, составленному из этих младших разрядов. Вариант от старшего разряда к младшему существует, требует разбиения на группы и рекурсии и в настоящее описание не входит; смешивать их нельзя. Оценка: d проходов по n элементам с таблицей длины b, то есть порядка d·(n + b). Выбор основания b есть параметр варианта: больший b уменьшает d и увеличивает память.

Referencing norms: f-032ea6fd67c51428cfa254aa, f-073a9d116b15d5e049cc918a, f-095038c47168b0e4b47697ec, f-0bb4b68c24ef4101f57b6772, f-104fbca713eb444de898e504, f-1381517562939b695bf61f0b, f-1ab620616becbdb03a282d6f, f-1affb4721ec2e155fa68eb1e, f-1e25ccf58e3dd6ec79d8ffee, f-23d181a274de52f5444e8837, f-26abc149e177bfa96bb28d18, f-290ac0cf6dc46e4fa5a076f3, f-2a51cb7ac7cff01e67c7575e, f-2ec72247b1569de185fe1f24, f-35c62aebd1fd4a537f63806a, f-360ae99a06faa28323f931ad, f-391fcb2487a887a2aed63856, f-3cf2fbc5f6eadb139309d166, f-3e314ac08591ff74ca2f6c98, f-3f73c9de525e43f993bb8657, f-41ef49fdc8961f6995cac654, f-42c5639834dde2bce16b35ab, f-4db3700227739d50f8c8dbda, f-52506bc3560683482b80a76d, f-540c8c5f073f90443c9d100f, f-549abe20637e50c1455e04c7, f-55b90dcb10b816051ac445d5, f-5aa2de2124fd49d320537903, f-5b7e6d29079e73e9d9868fde, f-5e93c9f329c65272bd57ec0e, f-5ea4f72dd6f88ad0aafc6411, f-5ec2823ce5491aee27a38bb7, f-5f5139e02e984763c744ced4, f-61652541e3dcad535ec320a9, f-66056d788e3bd6d9487b4847, f-712b9344f01a5221d13b012c, f-721d8a8022937db0cdf147fc, f-78f53e2bb969449a092044e1, f-807a44102462d277b1f02004, f-81b93440da0d3e956c114ce2, f-886af8a47951686a9b58a5a7, f-8a49391626c18d5c884ac6b0, f-8f335510371897aac26a8e97, f-8f8263e9472e8e9dc1b57910, f-9b160a31bfffe81c43c974d4, f-9b849208b41bbdc5ec23308b, f-9fae083c3b2893751b3e5a96, f-a15b97e524fc059312302759, f-a1ee3ea6571b80a0e6926d5a, f-a407e24c1f1deeeb760887e1, f-a7d8ae3073b79f6538265cc3, f-ad59e9151845127d67104393, f-afd997c99903fb2af2c446c8, f-b2dc3ae658dc14a1d67a5a1a, f-b4f1b585911ac9d928c7c4d1, f-b538213bff042c13f8069002, f-b8edadf3f77d254ff87d5deb, f-bdd882fb493cf3568cdd0949, f-bee3737e585fe3017c56416a, f-c662078a3a221bc4eadf933e, f-c67c8d49966b8e6ecb61fb68, f-c835d9333f32126c0bcfbdfd, f-cdddf2b880bf8b1ab081059d, f-cdec619148418c9bd1486e99, f-d0df5b894f6098b65a1ea7a1, f-d17a17d71181f4f6bba9c7e9, f-d498653afb826d456770b1dc, f-d5cf92309ffe3d64f409d0a4, f-dccdc1e8d18006dd258af2af, f-e35d587a9581e341c860d71f, f-e7303f2d3318770336498650, f-ec6283fbbd5336ccf983f83a, f-ece7a3bb94dc3a78dbade3cc, f-f086de5507798c69a2cce5db, f-f29d8e322dad93c79fd4e00f, f-f3e01d2fc9439c3bdbd8309b, f-f4d2a5dccebc1b479f4ad956, f-f7d9995417a01c8b0c6011e4, f-fe8d37a92bfb55367e0ea30a

ru · official · sha256:4ff3ac875d6598b091cee8a0247d6e15c8c6f08c8010e6b791defb44496f13baRU

СОРТИРОВКИ: ВСТАВКАМИ, ВЫБОРОМ, СЛИЯНИЕМ, БЫСТРАЯ, ПИРАМИДАЛЬНАЯ, ПОДСЧЁТОМ И ПОРАЗРЯДНАЯ Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство семи алгоритмов сортировки: трёх простых, двух основанных на разделяй и властвуй, одной пирамидальной и двух не использующих сравнений. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Формулировка шагов, их нумерация и выбор варианта принадлежат настоящему изложению. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна последовательность здесь не переставляется.