Sortowanie biblioteczne

Sortowanie biblioteczne
Rodzaj	Sortowanie
Struktura danych	Tablica
Złożoność
Czasowa	Średnie: $O(n\cdot \log(n))$ Pesymistyczne: $O(n^{2})$
Pamięciowa	$O(n)$

Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów.

Nazwa wywodzi się z następującej analogii:

Wyobraźmy sobie bibliotekarza, który układa książki alfabetycznie na półkach. Zaczynając od książek na literę A ustawia jedną przy drugiej, aż dojdzie do litery Z. Jeśli bibliotekarz postanowi dodać nową książkę na półkę, której nazwa zaczyna się na literę B, to będzie musiał przesunąć wszystkie książki od miejsca, gdzie pasuje nowa książka aż do ostatniej książki. Ponieważ litera B występuje blisko początku alfabetu, więc praktycznie całą półkę książek należy przesunąć. Tak działa sortowanie przez wstawianie. Gdyby jednak bibliotekarz pozostawiał wolne miejsce po każdej literze, to musiałby przesunąć tylko niewielką liczbę książek (dopóki miejsce za literą B by się nie wyczerpało). Na tym polega algorytm Sortowania bibliotecznego^[1].

Algorytm zaproponowali: Michael A. Bender, Martín Farach-Colton oraz Miguel Mosteiro w 2004 roku^[2]. Podobnie jak sortowanie przez wstawianie, na którym bazuje, sortowanie biblioteczne jest algorytmem stabilnym. Wykazano, że jego złożoność czasowa wynosi najczęściej $O(n\cdot \log(n))$ (podobnie jak algorytmu quicksort), rzadziej $O(n^{2})$ (jak przy sortowaniu przez wstawianie). Mankamentem algorytmu jest zwiększone zapotrzebowanie na pamięć.

Przypisy

↑ Timothy A.: An Active Learning approach to Data Structures using C. [dostęp 2017-07-30]. [zarchiwizowane z tego adresu (2011-07-20)]. (ang.).
↑ M.A. Bender, M. Farach-Colton, M. Mosteiro: Insertion Sort is O(n log n). [dostęp 2017-07-30]. (ang.).

Algorytmy sortowania

Algorytmy stabilne	Sortowanie bąbelkowe Sortowanie przez wstawianie Sortowanie przez scalanie Sortowanie przez zliczanie Sortowanie kubełkowe Sortowanie pozycyjne Sortowanie biblioteczne
Algorytmy niestabilne	Sortowanie przez wybieranie Sortowanie Shella Sortowanie grzebieniowe Sortowanie szybkie Sortowanie introspektywne Sortowanie przez kopcowanie Bogosort

Read other articles:

Albert Gallatin

American politician, diplomat, and scholar (1761–1849) For the artist, see Albert Eugene Gallatin. For the governor of Mississippi, see Albert Gallatin Brown. Albert GallatinGallatin by Gilbert Stuart, c. 1803United States Minister to the United KingdomIn officeSeptember 1, 1826 – October 4, 1827PresidentJohn Quincy AdamsPreceded byRufus KingSucceeded byWilliam Beach Lawrence (acting)United States Minister to FranceIn officeJuly 16, 1816 – May 16, 1823PresidentJa...

Work design

Area of research and practice within industrial and organizational psychology Part of a series onPsychology Outline History Subfields Basic psychology Abnormal Affective neuroscience Affective science Behavioral genetics Behavioral neuroscience Behaviorism Cognitive/Cognitivism Cognitive neuroscience Social Comparative Cross-cultural Cultural Developmental Differential Ecological Evolutionary Experimental Gestalt Intelligence Mathematical Moral Neuropsychology Perception Personality Positive...

Qubic experiment

For the game, see Qubic. Q&U Bolometric Interferometer for CosmologyAlternative namesQubic experiment Location(s)Puna de AtacamaCoordinates24°11′32″S 66°28′29″W / 24.1921°S 66.4747°W / -24.1921; -66.4747 Altitude4,820 m (15,810 ft) Wavelength150, 220 GHz (2.0, 1.4 mm)First light2022 Telescope stylebolometerradio interferometer Angular resolution23.5 arcminute Websitewww.qubic.org.ar Location of...

Syed Razak Syed Zain Barakbah

Malaysian politician In this Malay name, there is no surname or family name. The name Syed Zain Barakhbah is a patronymic, and the person should be referred to by their given name, Syed Razak. The word bin or binti/binte means 'son of' or 'daughter of', respectively. Yang Berbahagia Dato' Seri Utama HajiSyed Razak Syed Zain BarakhbahDMK SSDK DSDK KMN AMN JPسيد رزاق سيد زين بارکبه8th Menteri Besar of KedahIn office11 December 1999 – 22 December 2005MonarchAbdul Ha...

العلاقات الصينية الموزمبيقية

العلاقات الصينية الموزمبيقية الصين موزمبيق الصين موزمبيق تعديل مصدري - تعديل العلاقات الصينية الموزمبيقية هي العلاقات الثنائية التي تجمع بين الصين وموزمبيق.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارنة...

Первородный грех

Об экономическом термине см. Первородный грех (экономика). ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Ран�...

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

NXT TakeOver: In Your House (2020)

WWE Network event NXT TakeOver: In Your HousePromotional poster featuring Adam Cole and Velveteen DreamPromotionWWEBrand(s)NXTDateJune 7, 2020CityWinter Park, FloridaVenueFull Sail UniversityAttendance0 (behind closed doors)[Note 1]WWE Network event chronology ← PreviousMoney in the Bank Next →Backlash NXT TakeOver chronology ← PreviousTampa Bay (cancelled) Next →XXX In Your House chronology ← PreviousSt. Valentine's Day Massacre Next →NXT Tak...

Xiongnu

XiongnuAbad ke-3 SM–460-an MWilayah Xiongnu (hijau), Sekitar 250 SMStatusKonfederasi NomadIbu kotaLongcheng (龙城/蘢城), dekat Khoshoo Tsaidam (Mongolia modern), dijadikan tempat pertemuan tahunan, dan ibukota de factoAgama Kemungkinan Tengriisme[1][2]Chanyu • 240–209 SM Touman• 94–118 M Feng-hou (Utara)• 195 M Huchuquan (Selatan) Sejarah • Didirikan Abad ke-3 SM• Dibubarkan 460-an M Digantikan oleh dnsDinasti Han Xianbei ...

Warsaw Ghetto

Nazi ghetto in occupied Poland For the book, see The Warsaw Ghetto: A Guide to the Perished City. Warsaw GhettoBrick wall of the Warsaw Ghetto dividing the Iron-Gate Square, with view of bombed out Lubomirski Palace (left) on the Aryan side of the city, May 24, 1941.Also known asGerman: Ghetto WarschauLocationWarsaw, German-occupied Poland Muranów Powązki Nowolipki Śródmieście Północne Mirów DateOctober 1940 to May 1943Incident typeImprisonment, mass shootings, forced labor, starvatio...

Partai Nasional Demokrat (1998)

Artikel ini bukan mengenai Partai NasDem. Untuk kegunaan lain, lihat Partai Nasional Demokrat. Partai Nasional Demokrat Ketua umumEdwin Henawan SoekowatiSekretaris JenderalEddy SjafuanDibentuk12 Juni 1998Dipisah dariPDIKantor pusatJl Tebet Utara III No 9 Jakarta Selatan 12820IdeologiPancasilaKursi di DPR0Politik IndonesiaPartai politikPemilihan umum Partai Nasional Demokrat (PND) adalah sebuah partai politik di Indonesia yang didirikan pada tanggal 12 Juni 1998 oleh anggota Pemuda Demokr...

世界政區索引

此條目可能包含不适用或被曲解的引用资料，部分内容的准确性无法被证實。 (2023年1月5日)请协助校核其中的错误以改善这篇条目。详情请参见条目的讨论页。各国相关主題列表索引国内生产总值石油储量国防预算武装部队（军事）官方语言人口統計人口密度生育率出生率死亡率自杀率谋杀率失业率储蓄率识字率出口额进口额煤产量发电量监禁率死刑国债 ...

Сказання про населені місцевості Київської губернії

«Сказання про населені місцевості Київської губернії» обкладинка виданняАвтор Лаврентій ПохилевичНазва мовою оригіналу Сказанія о населенныхъ мѣстностяхъ Кіевской губерніиКраїна Російська імперіяМова російська (дореформенна)Тема краєзнавствоЖанр історіяВидано 186...

هات (زاكارباتسكا)

هات تاريخ التأسيس 1374 تقسيم إداري البلد أوكرانيا الإمبراطورية النمساوية الإمبراطورية النمساوية المجرية خصائص جغرافية إحداثيات 48°19′13″N 22°38′22″E / 48.320277777778°N 22.639444444444°E / 48.320277777778; 22.639444444444 المساحة 4.15 كيلومتر مربع السكان التعداد السكاني 3122 (2001)&...

National Postal Mail Handlers Union

American labor union This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (May 2020) National Postal Mail Handlers UnionHeadquartersWashington, D.C.LocationUnited StatesMembers 50,000Key peoplePaul V. Hogrogian, President. Kevin P. Tabarus, Secretary/Treasurer. Katie Maddocks, Legislative & Political Director.Parent organizationLIUNAAffiliationsAFL–CIOWebsitenpmhu.org The National Postal Mail Handlers Un...

Anti-corruption campaign under Xi Jinping

2012–present anti-corruption campaign in China You can help expand this article with text translated from the corresponding article in Chinese. (March 2023) Click [show] for important translation instructions. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Do n...

Théâtre occidental de la guerre d'indépendance des États-Unis

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. La traduction de cet article ou de cette section doit être revue (mai 2016). Le contenu est difficilement compréhensible vu les erreurs de traduction, qui sont peut-être dues à l'utilisation d'un logiciel de traduction automatique. Discutez des points à améliorer en page de discussion ou modifiez l'article. Front de l'Ouest de la guerre d'indépendance des États-Unis La reddition du Fort Sackville, tableau...

1984 في جنوب إفريقيا

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) 1984 في جنوب إفريقيامعلومات عامةالسنة 1984 1983 في جنوب إفريقيا 1985 في جنوب إفريقيا تعديل - تعديل مصدري - تعديل و�...

Виньяк

Эта страница требует существенной переработки. Возможно, её необходимо правильно оформить, дополнить или переписать.Пояснение причин и обсуждение — на странице Википедия:К улучшению/6 июня 2024. В статье не хватает ссылок на источники (см. рекомендации по поиску). Информац...

S. H. Raza

Indian painter Sayed Haider RazaLHBorn(1922-02-22)22 February 1922Kakkaiya, Mandla, Central Provinces and Berar (now in Madhya Pradesh, India)Died23 July 2016(2016-07-23) (aged 94)Delhi, IndiaNationalityIndianEducation• Chitrakala Mahavidyalaya, Nagpur • Sir J. J. School of Arts, MumbaiMovementBombay Progressive Artists' GroupAwardsPadma Vibhushan (2013) Padma Bhushan (2007) Fellow of Lalit Kala Academy (1984)Padma Shri (1981)Commandeur de la Legion d'honneur (2015)Websitetherazafoun...