Блочная сортировка

Элементы распределяются по корзинам
Затем элементы в каждой корзине сортируются

Блочная сортировка (Карманная сортировка, корзинная сортировка, англ. Bucket sort) — алгоритм сортировки, в котором сортируемые элементы распределяются между конечным числом отдельных блоков (карманов, корзин) так, чтобы все элементы в каждом следующем по порядку блоке были всегда больше (или меньше), чем в предыдущем. Каждый блок затем сортируется отдельно, либо рекурсивно тем же методом, либо другим. Затем элементы помещаются обратно в массив. Этот тип сортировки может обладать линейным временем исполнения.

Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.

Алгоритм

Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).

Идея алгоритма заключается в том, чтобы разбить отрезок [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путём последовательного перечисления элементов каждого кармана.

Псевдокод

function bucket-sort(A, n) is
  buckets ← новый массив из n пустых элементов
  for i = 0 to (length(A)-1) do
    вставить A[i] в конец массива buckets[msbits(A[i], k)]
  for i = 0 to n - 1 do
    next-sort(buckets[i])
  return Конкатенация массивов buckets[0], ..., buckets[n-1]

На вход функции bucket-sort подаются сортируемый массив (список, коллекция и т.п.) A и количество блоков - n.

Массив buckets представляет собой массив массивов (массив списков, массив коллекций и т.п.), подходящих по природе к элементам A.

Функция msbits(x,k) тесно связана с количеством блоков - n (возвращает значение от 0 до n), и, в общем случае, возвращает k наиболее значимых битов из x (floor(x/2^(size(x)-k))). В качестве msbits(x,k) могут быть использованы разнообразные функции, подходящие по природе сортируемым данным и позволяющие разбить массив A на n блоков. Например, для символов A-Z это может быть сопоставление номерам букв 0-25, или возврат кода первой буквы (0-255) для ASCII набора символов; для чисел [0, 1) это может быть функция floor(n*A[i]), а для произвольного набора чисел в интервале [a, b) - функция floor(n*(A[i]-a)/(b-a)).

Функция next-sort также реализует алгоритм сортировки для каждого созданного на первом этапе блока. Рекурсивное использование bucket-sort в качестве next-sort превращает данный алгоритм в поразрядную сортировку. В случае n = 2 соответствует быстрой сортировке (хотя и с потенциально плохим выбором опорного элемента).

Оценка сложности

Оценим сложность алгоритма блочной сортировки для случая, при котором в качестве алгоритма сортировки блоков (next-sort из псевдокода) используется сортировка вставками.

Для оценки сложности алгоритма введём случайную величину ni, обозначающую количество элементов, которые попадут в карман B[i]. Время работы сортировки вставками равно .

Время работы алгоритма карманной сортировки равно

Вычислим математическое ожидание обеих частей равенства:

Найдем величину .

Введем случайную величину , которая равна 1, если A[j] попадает в i-й карман, и 0 в противном случае:

Если k ≠ j, величины Xij и Xik независимы, поэтому:

Таким образом

Итак, ожидаемое время работы алгоритма карманной сортировки равно

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 8. Сортировка за линейное время // Алгоритмы: построение и анализ, 2-е издание = Introduction to Algorithms second edition. — М.: «Вильямс», 2005. — С. 230 - 234. — ISBN 5-8459-0857-4.

См. также

Ссылки

Read other articles:

Men's K-1 1000 metres at the 2022 ICF Canoe SprintWorld ChampionshipsVenueLake BanookLocationDartmouth, CanadaDates3–6 AugustCompetitors30 from 30 nationsWinning time3:38.93Medalists  Bálint Kopasz   Hungary Fernando Pimenta   Portugal Jacob Schopf   Germany← 20212023 → 2022 ICF Canoe SprintWorld ChampionshipsCanadian eventsC-1 200mmenwomenC-1 500mmenwomenC-1 1000mmenwomenC-1 5000mmenwomenC-2 200mwo...

 

L'unione falla forseLogo del filmPaese di produzioneItalia Anno2019 Generedocumentario RegiaFabio Leli SceneggiaturaFabio Leli ProduttoreFabio Leli Casa di produzioneHuman Tree FotografiaFabio Leli, Armando Avolio MontaggioFabio Leli, Armando Avolio MusicheAlfredo Colella, Luce Montrone, Rosa Cavalieri Interpreti e personaggi Italia Aiuola: voce narrante Eleonora Magnifico: annunciatrice Michele Ciavarella: Padre Michele Maria Celeste Rizzo: se stessa Daniela D'Anna: se stessa Vittoria D'Anna...

 

Keresahan makanan di Indonesia 2005 adalah keresahan makanan yang terjadi pada tahun 2005 di Jakarta, Indonesia, ketika pemerintah menemukan bahwa 60% dari toko mie di ibu kota telah menjual mie yang dicampur dengan formaldehida, suatu karsinogen yang cukup dikenal. Mie pada keresahan makanan di Vietnam pada tahun 2007 juga memiliki kontaminan yang sama, dan pengawet kimia yang juga jelas ditemukan pada tahu, mie, dan ikan asin. Thailand[1] memiliki masalah formaldehida yang serupa. R...

The Ancient Magus' BrideGambar sampul manga volume pertama魔法使いの嫁(Mahō Tsukai no Yome)GenreFantasi gelap,[1] misteri,[2] supernatural[3] MangaPengarangKore YamazakiPenerbitMag GardenPenerbit bahasa InggrisNA Seven Seas EntertainmentPenerbit bahasa IndonesiaM&C!MajalahMonthly Comic Blade(November 2013 – 1 Juli 2014)Monthly Comic Garden(September 2014 – sekarang) DemografiShōnenTerbitNovember 2013 – sekarangVolume19 (Daftar volume) Video anima...

 

Изображение было скопировано с wikipedia:en. Оригинальное описание содержало: Summary The cover art for the Santana album Spirits Dancing in the Flesh Licensing Це зображення є обкладинкою музичного альбому або синглу. Найімовірніше, авторськими правами на обкладинку володіє видавець альбому (синглу) або виконав

 

For the New Zealand illustrator, cartoonist and ceramicist, see Anna Crichton. Dame Anna CrightonDNZM QSO JPCrighton in 2020BornAnna Louisa de Launey CrightonChristchurch, New ZealandAcademic backgroundAlma materUniversity of Canterbury (BA, MA)University of Otago (PhD)ThesisThe selection and presentation culture of the Robert McDougall Art Gallery, Christchurch, New Zealand, 1932–2002 (2012) Dame Anna Louisa de Launey Crighton DNZM QSO JP is a New Zealand heritage camp...

This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (February 2010) (Learn how and when to remove this template message) Wilhelm FliessWilhelm FließFliess (right) and Sigmund Freudin the early 1890s.Born24 October 1858Arnswalde, Province of Brandenburg, Kingdom of PrussiaDied13 October 1928 (aged 69)Berlin, Province of Brandenburg, GermanyNationalityPrussianScien...

 

Скоростные виды подводного плавания Категория Дисциплины подводного спорта Инвентарь Маска (подводное плавание) Трубка (дайвинг) Ласты (дайвинг) Акваланг Дисциплины плавание в ластах 50м, 100м, 200м, 400м, 800м, 1500 м ныряние 50м подводное плавание с аквалангом 100м, 400м эстафета 4 × 1...

 

Кленовий сироп Необхідні компоненти Ксилема  Медіафайли у Вікісховищі Пляшка кленового сиропу, виробленого в канадській провінції Квебек Кленовий сироп (англ. maple syrup, фр. Sirop d'érable) — солодкий сироп з соку дерева цукрового клена, червоного клена або чорного клена. Ча...

Large, oval-shaped kettle used for cooking whole fish A fish kettle, circa 1907. A fish kettle is a kind of large, oval-shaped kettle used for cooking whole fish. Owing to their necessarily unwieldy size, fish kettles usually have racks and handles, and notably tight-fitting lids. Larousse Gastronomique describes the fish kettle as a long, deep cooking receptacle with two handles, a grid, and a lid. The fish kettle is used to cook whole fish, such as hake, salmon, pike, in a court-bouillon. T...

 

ManitobaProvince BenderaLambang kebesaranMotto: bahasa Latin: Gloriosus et LiberAgung dan bebasGlorious and Freecode: en is deprecated   (Inggris)Glorieux et librecode: fr is deprecated   (Prancis) BC AB SK MB ON QC NB PE NS NL YT NT NU NegaraKanadabergabung dengan konfederasi15 Juli 1870 (urutan ke-5)Ibu kotaWinnipegKota terbesarWinnipeg Metro terbesarWilayah Ibukota Winnipeg Pemerintahan • Wakil GubernurJanice Filmon • Perdana MenteriHeat...

 

Suburb of Perth, Western AustraliaRivervalePerth, Western AustraliaRivervale from the Aloft HotelCoordinates31°57′40″S 115°55′01″E / 31.961°S 115.917°E / -31.961; 115.917Population10,897 (SAL 2021)[1]Established1843Postcode(s)6103Area3.0 km2 (1.2 sq mi)Location5 km (3 mi) from PerthLGA(s)City of BelmontState electorate(s)BelmontFederal division(s)Swan Suburbs around Rivervale: Burswood Maylands Belmont Lathlain Riverval...

1990 Indian filmManeಮನೆDirected byGirish KasaravalliScreenplay byGirish KasaravalliStory byT. G. RaghavaProduced byGirish Kasaravalli(Kannada version)NFDC(Hindi version)StarringNaseeruddin ShahDeepti NavalRohini HattangadiCinematographyS. RamachandraEdited byM. N. SwamyMusic byL. VaidyanathanDistributed byApoorva ChithraRelease dates 1990 (1990) (Kannada version) 16 August 1991 (1991-08-16) (India) (Hindi version)Running time117 minutes(Kannada version)98 minutes...

 

بلديات المقاطعة هنا قائمة ببلديات منطقة أشتورية (بالإسبانية: Asturias)‏, المصنفة على أنها إحدى مقاطعات إسبانيا. والتي تقع في الشمال الغربي لإسبانيا. الاسم السكان (2002) السكان (2014)[1] ألاندي 2,374 1,891 ألير 14,786 11,906 أمايفا 889 772 أفايلاس 83,511 82,568 بيلمونتي دي ميراندا 2,209 1,711 بايمينس 2,071 1,8...

 

Railway station in Bihar Janakpur Road railway stationIndian Railways stationGeneral informationLocationStation Road, Pupri, Janakpur Road, BiharIndiaElevation61 metres (200 ft)Owned byIndian RailwaysOperated byEast CentralLine(s)Muzaffarpur–Sitamarhi section Muzaffarpur–Gorakhpur line (via Hajipur, Raxaul and Sitamarhi)Platforms2Tracks3ConstructionStructure typeStandard (on ground station)ParkingNoBicycle facilitiesNoOther informationStatusConstruction – single-line electrificatio...

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Welsh Mountain Landscape J. M. W. Turner – news · newspapers · books · scholar · JSTOR (May ...

 

Spanish football club Football clubTomellosoFull nameTomelloso Club de FútbolFounded1979Dissolved2015GroundEstadio Municipal, Tomelloso, Castile-La Mancha, SpainCapacity5,000Chairman Francisco MuñozManager Ignacio GalindoLeague1ª Autonómica Preferente2012–131ª Autonómica Preferente, 7th Home colours Away colours Tomelloso Club de Fútbol was a Spanish football team based in Tomelloso, in the autonomous community of Castile-La Mancha. Founded in 1979 it played its home games at Estadio...

 

American actress Not to be confused with Nicky Cox. Nikki CoxCox during an October 2000 promotional tour for NikkiOther namesNikki Cox Mohr (formerly)OccupationActressYears active1988–2010Spouse Jay Mohr ​ ​(m. 2006; div. 2018)​PartnerBobcat Goldthwait (1997–2005)Children1 Nikki Cox is an American former actress, known mostly for her roles on the television series Unhappily Ever After, Las Vegas, The Norm Show, and Nikki. Career Co...

College of higher education in Kerala, India This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: St. Thomas College, Palai – news · newspapers · books · scholar · JSTOR (August 2018) (Learn how and when to remove this template message) St. Thomas College Palaസെന്റ്. തോമസ്‌ കോളേജ...

 

Difference in wind speed or direction over a short distance For other uses, see Wind shear (disambiguation). Cirrus uncinus ice crystal plumes showing high-level wind shear, with changes in wind speed and direction Wind shear (or windshear), sometimes referred to as wind gradient, is a difference in wind speed and/or direction over a relatively short distance in the atmosphere. Atmospheric wind shear is normally described as either vertical or horizontal wind shear. Vertical wind shear is a c...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!