Сортування порівняннями

В алгоритмах сортування порівняннями для отримання інформації про розташування елементів вхідної послідовності $\langle a_{1},a_{2},\dots ,a_{n}\rangle$ використовуються тільки попарні порівняння елементів. Іншими словами, для визначення взаємного порядку двох елементів $a_{i}$ та $a_{j}$ виконується одна з перевірок $a_{i}<a_{j},a_{i}\leq a_{j},a_{i}=a_{j},a_{i}\geq a_{j}$ або $a_{i}>a_{j}.$ Ми не можемо використовувати значення самих елементів або отримувати інформацію про них іншим способом.

Приклади

Модель дерева прийняття рішень

Ми можемо розглядати сортування порівняннями абстрактно, у термінах дерева прийняття рішень. Дерево прийняття рішень — повне двійкове дерево, яке представляє порівняння між елементами, які виконав певний алгоритм сортування порівняннями на наданих вхідних даних.

Нижня межа для найгіршої швидкодії

Довжина найдовшого простого шляху від кореня до листа представляє кількість порівнянь які необхідно виконати в найгіршому випадку. З цього випливає, що кількість порівнянь в найгіршому випадку для певного алгоритму сортування порівняннями дорівнює висоті дерева прийняття рішень. Нижня межа для всіх дерев прийняття рішень в яких кожна перестановка є досяжним листом і є нижньою межею швидкодії для будь-якого алгоритму сортування порівняннями.

Теорема Будь-який алгоритм сортування порівняннями в найгіршому випадку вимагає $\Omega (n\lg {n})$ порівнянь.

Доведення Зі сказаного вище, достатньо визначити висоту дерева прийняття рішень в якому кожна перестановка з'являється як досяжний лист. Розглянемо дерево висоти $h$ з $l$ досяжними листами, що відповідає сортуванню порівняннями для $n$ елементів. Через те, що кожна $n!$ перестановок вхідних даних з'являється в якомусь листі, ми маємо $n!\leq l.$ оскільки повне двійкове дерево висоти $h$ має не більше ніж $2^{h}$ листів, маємо

n!\leq l\leq 2^{h},

що, якщо прологарифмувати, дає

h\geq \lg {n!}=\Omega (n\lg {n})

(для доведення останнього рівняння зручно використати формулу Стірлінґа в логарифмічній формі).

Джерела

Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
Сортування за лінійний час

п о р Алгоритми сортування
Теорія	Обчислювальна складність \| Нотація великого О \| Відношення порядку \| Список \| Стабільність \| Сортування порівняннями \| Квантове сортування
Сортування обміном	Сортування бульбашкою \| Сортування змішуванням \| Odd-even sort \| Сортування гребінцем \| Сортування гнома \| Швидке сортування
Сортування вибором	Сортування вибором \| Пірамідальне сортування
Сортування включенням	Сортування включенням \| Сортування Шелла \| Сортування бінарним деревом \| Сортування вставкою з проміжками \| Patience sorting^[en]
Сортування злиттям	Сортування злиттям \| Ниткоподібне сортування
Алгоритми без порівнянь	Сортування за розрядами \| Сортування комірками \| Сортування підрахунком \| Цифрове сортування \| Burstsort^[en] \| Bead sort^[en]
Інші	Топологічне сортування \| Sorting network^[en] \| Bitonic sorter^[en]
Непрактичні алгоритми	Випадкове сортування \| Stooge sort

Read other articles:

Vittoriano

Disambiguazione – Se stai cercando il nome proprio di persona, vedi Vittoriano (nome). Monumento nazionalea Vittorio Emanuele IIIl Vittoriano visto da piazza VeneziaLocalizzazioneStato Italia RegioneLazio LocalitàRoma IndirizzoPiazza Venezia 6, 00187 Roma Coordinate41°53′40.56″N 12°28′59.13″E / 41.894599°N 12.483092°E41.894599; 12.483092Coordinate: 41°53′40.56″N 12°28′59.13″E / 41.894599°N 12.483092°E41.894599; 12.483092 Informa...

Orani João Tempesta

Orani João TempestaO.Cist.Kardinal, Uskup Agung São Sebastião do Rio de JaneiroGerejaGereja Katolik RomaTakhtaSão Sebastião do Rio de JaneiroPenunjukan27 Februari 2009Awal masa jabatan19 April 2009PendahuluEusébio Oscar Scheid, S.C.J.Jabatan lainKardinal-Imam Santa Maria Madre della Providenza a Monte Verde (2014–sekarang) Uskup Agung Belém do Pará (2004–2009) Administrator Apostolik Kawasan Biara Claraval (1999–2002) Uskup Rio Preto (1997–2004) Abbas Biara São Bernardo (1996...

Magister equitum

Organi costituzionali romani Assemblee romane Senato (Senatus) princeps senatus senatus consultum Comizi curiati (comitia curiata) Comizi centuriati (comitia centuriata) Comizi tributi (comitia populi tributa) Comizi calati (comitia calata) Concili della plebe (Concilium plebis) Magistrati ordinari Cursus honorum: censore (censor) console (consul) pretore (praetor) edile (aedilis) questore (quaestor) tribuno della plebe (tribunus plebis) duumviri (duumviri) triumviri (triumviri) seviri (sevi...

Человек прямоходящий

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

Etruria

Gaya bahasa tidak ensiklopedis ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan Gaya bahasa tidak ensiklopedis ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Area yang ditutupi adalah bagian dari peradaban Etruria Etruria (merujuk pada teks bahasa Yunani dan...

Ottawa

Capital city of Canada This article is about the capital of Canada. For other uses, see Ottawa (disambiguation). Federal capital city in Ontario, CanadaOttawaFederal capital cityCity of Ottawa Ville d'Ottawa (French)From top, left to right: Centre Block on Parliament Hill, the Government House, Downtown Ottawa, the Château Laurier, the National Gallery of Canada and the Rideau Canal FlagCoat of armsLogoNicknames: Bytown[1][2]O-town[3]Motto(s): Advance-O...

Wilson Chinn

American enslaved man Wilson ChinnChinn, the famous branded slave photoKnown forSubject of photos demonstrating instruments of torture, widely circulated during the American Civil War Wilson Chinn (fl. 1863) was an escaped American slave from Louisiana who became known as the subject of photographs documenting the extensive use of torture received in slavery. The branded slave photograph of Chinn with VBM (the initials of his owner, Volsey B. Marmillion) branded on his forehead, wearing ...

Kutabawa, Karangreja, Purbalingga

KutabawaDesaPeta lokasi Desa KutabawaNegara IndonesiaProvinsiJawa TengahKabupatenPurbalinggaKecamatanKarangrejaKode Kemendagri33.03.10.2002 Luas... km²Jumlah penduduk... jiwaKepadatan... jiwa/km² Kutabawa adalah desa di kecamatan Karangreja, Purbalingga, Jawa Tengah, Indonesia. Di Kutabawa berlokasi pos awal pendakian ke Gunung Slamet (Pos Bambangan) dari sisi timur. Tempat ini populer di kalangan pendaki. Kutabawa dapat ditempuh dari terminal Purbalingga dengan menggunakan angkutan de...

Long Branch, New Jersey

City in Monmouth County, New Jersey, US City in New Jersey, United StatesLong Branch, New JerseyCityChurch of the Presidents SealNicknames: The First Seaside Resort, Friendly CityMotto: Tide InLocation of Long Branch in Monmouth County highlighted in red (left). Inset map: Location of Monmouth County in New Jersey highlighted in orange (right).Census Bureau map of Long Branch, New Jersey Interactive map of Long Branch, New JerseyLong BranchLocation in Monmouth CountyShow map of Monm...

伊帕廷加

伊帕廷加伊帕廷加（Ipatinga）是巴西的城市，位於該國東南部，距離貝洛奧里藏特217公里，由米納斯吉拉斯州負責管轄，面積165.5平方公里，海拔高度220米，2009年人口244,508。外部連結 Official website （页面存档备份，存于互联网档案馆） Ipatinga.org 这是一篇與巴西相關的地理小作品。您可以通过编辑或修订扩充其内容。查论编查论编米納斯吉拉斯州市鎮首府及最大城市：贝�...

Jules Dupuit

French economist and civil engineer (1804–1866) This article includes a list of references, related reading, or external links, but its sources remain unclear because it lacks inline citations. Please help improve this article by introducing more precise citations. (October 2021) (Learn how and when to remove this message) Jules DupuitJules DupuitBorn(1804-05-18)18 May 1804Fossano, Cisalpine RepublicDied5 September 1866(1866-09-05) (aged 62)Paris, FranceNationalityFrenchAlma mater...

Nobelpriset i fysiologi eller medicin

Nobelpriset i fysiologi eller medicin Medaljen för nobelpriset i kemi. Medaljen för fysiologi eller medicin är identisk med denna medalj.BeskrivningVetenskapsprisUtdelareNobelförsamlingen vid Karolinska institutetPlatsStockholmLand SverigeFörsta utdelning1901ÅterkommandeÅrligenTidpunkt10 december Nobelpriset i fysiologi eller medicin är ett av de fem Nobelprisen, inrättade genom Alfred Nobels testamente. Alfred Nobel specificerade att ett av prisen skulle gå till den som under ...

Siege of Carlisle (1644)

Siege of Carlisle during the First English Civil War 54°53′50″N 2°56′31″W / 54.89726°N 2.941936°W / 54.89726; -2.941936 Siege of CarlislePart of the First English Civil WarCarlisle CastleDateOctober 1644 – 25 June 1645LocationCarlisle, Cumbria, North West England, EnglandResult Covenanter/Parliamentarian VictoryBelligerents Covenanters Parliamentarians RoyalistsCommanders and leaders Earl of Leven Sir Thomas GlennamSir Henry ShadlingStrength 4,000[1&#...

Carlos Morais

Questa voce sull'argomento cestisti angolani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Carlos MoraisNazionalità Angola Altezza193 cm Peso91 kg Pallacanestro RuoloGuardia / ala Squadra Petro Atlético CarrieraSquadre di club 2001-2013 Petro Atlético2013-2015 Libolo2016-2018 Benfica67 (825)2018-2019 Mens Sana Siena21 (323)2019- Petro Atlético Nazionale 2003 Ang...

Peephole

Small, round opening through a door For the System of a Down song, see System of a Down (album). For the computer compiler techniques, see peephole optimization. This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these 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...

كارولين لوكاس

تحتاج هذه المقالة إلى الاستشهاد بمصادر إضافية لتحسين وثوقيتها. فضلاً ساهم في تطوير هذه المقالة بإضافة استشهادات من مصادر موثوق بها. من الممكن التشكيك بالمعلومات غير المنسوبة إلى مصدر وإزالتها. (يناير 2019) كارولين لوكاس (بالإنجليزية: Caroline Lucas)‏ معلومات شخصية اسم الولا...

Medical record

Medical term This article is about the documentation of a patient's medical history. For digital records, see electronic health record. For the New York journal published by the Washington Institute of Medicine, see Medical Record (journal). For the BBC Radio 4 medical programme, see Case Notes (radio show). The terms medical record, health record and medical chart are used somewhat interchangeably to describe the systematic documentation of a single patient's medical history and care across ...

Thomas Pennant

Welsh naturalist (1726–1798) Thomas PennantThomas Pennant by Thomas Gainsborough (1776)Born27 June [O.S. 14 June] 1726Downing Hall, Whitford, Flintshire, WalesDied16 December 1798(1798-12-16) (aged 72)Downing Hall, Whitford, Flintshire, WalesOccupationsNaturalistantiquarianKnown forWritings on natural history, geology, and geographical expeditions Thomas Pennant (27 June [O.S. 14 June] 1726 – 16 December 1798)[1] was a Wel...

Operação Lava Jato

Operação Lava Jato Edifício sede da Petrobrás — Brasão da Polícia Federal — Juiz Sergio Moro — Deltan Dallagnol, do Ministério Público Federal, e Rodrigo Janot, ex-Procurador geral da República — Polícia Federal realizando uma operação — Logotipo da Organização Odebrecht (atual Novonor) Local do crime Brasil Data 17 de março de 2014 – 1 de fevereiro de 2021 (7 anos)[1] Tipo de crime Corrupção ativa, corrupção passiva, formação de quadrilha, gestão fraudulent...

Mogilno County

County in Kuyavian-Pomeranian Voivodeship, PolandMogilno County Powiat mogileńskiCounty FlagCoat of armsLocation within the voivodeshipCoordinates (Mogilno): 52°39′N 17°57′E / 52.650°N 17.950°E / 52.650; 17.950Country PolandVoivodeshipKuyavian-PomeranianSeatMogilnoGminas Total 4 Gmina DąbrowaGmina Jeziora WielkieGmina MogilnoGmina Strzelno Area • Total675.86 km2 (260.95 sq mi)Population (2006) • Total45,756...

/profillengkap.com/index.php/article/Federal Power Commission

/profillengkap.com/index.php/article/Chambeali

/profillengkap.com/index.php/article/191st Rifle Division

Unione Sportiva Rivarolese

Nick.com

Budaya Prancis

Telagah, Sei Bingai, Langkat

Marina Barrage

Pemilihan umum Bupati Situbondo 2024

Monica Sandve

Madderty

Papa Ormisda