Introselect

Introselect (Musser)
ClassSelection algorithm
Data structureArray
Worst-case performanceO(n)
Best-case performanceO(n)
Introselect (Quickselect–Heapselect)
ClassSelection algorithm
Data structureArray
Worst-case performanceO(n log n)
Best-case performanceO(n)

In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance. Introselect is related to the introsort sorting algorithm: these are analogous refinements of the basic quickselect and quicksort algorithms, in that they both start with the quick algorithm, which has good average performance and low overhead, but fall back to an optimal worst-case algorithm (with higher overhead) if the quick algorithm does not progress rapidly enough. Both algorithms were introduced by David Musser in (Musser 1997), with the purpose of providing generic algorithms for the C++ Standard Library that have both fast average performance and optimal worst-case performance, thus allowing the performance requirements to be tightened.[1]

However, in most C++ Standard Library implementations, a different "introselect" algorithm is used, which combines quickselect and heapselect, and has a worst-case running time of O(n log n).[2] The C++ draft standard, as of 2022, does not have requirements on the worst-case performance, therefore allowing such choice.[3]

Algorithms

Introsort achieves practical performance comparable to quicksort while preserving O(n log n) worst-case behavior by creating a hybrid of quicksort and heapsort. Introsort starts with quicksort, so it achieves performance similar to quicksort if quicksort works, and falls back to heapsort (which has optimal worst-case performance) if quicksort does not progress quickly enough. Similarly, introselect combines quickselect with median of medians to achieve worst-case linear selection with performance similar to quickselect.

Introselect works by optimistically starting out with quickselect and only switching to a worst-case linear-time selection algorithm (the Blum-Floyd-Pratt-Rivest-Tarjan median of medians algorithm) if it recurses too many times without making sufficient progress. The switching strategy is the main technical content of the algorithm. Simply limiting the recursion to constant depth is not good enough, since this would make the algorithm switch on all sufficiently large lists. Musser discusses a couple of simple approaches:

  • Keep track of the list of sizes of the subpartitions processed so far. If at any point k recursive calls have been made without halving the list size, for some small positive k, switch to the worst-case linear algorithm.
  • Sum the size of all partitions generated so far. If this exceeds the list size times some small positive constant k, switch to the worst-case linear algorithm. This sum is easy to track in a single scalar variable.

Both approaches limit the recursion depth to k ⌈log n⌉ = O(log n) and the total running time to O(n).

The paper suggested that more research on introselect was forthcoming, but the author retired in 2007 without having published any such further research.

See also

References

  1. ^ "Generic Algorithms", David Musser
  2. ^ "35968 – nth_element fails to meet its complexity requirements".
  3. ^ "27.8.3 Nth element [alg.nth.element]". Working Draft, Standard for Programming Language C++, eel.is.

Read other articles:

Masaaki Ueki

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada April 2017. Masaaki UekiInformasi pribadiNama lengkap Masaaki UekiTanggal lahir 23 Juli 1974 (umur 49)Tempat lahir Prefektur Ibaraki, JepangPosisi bermain PenyerangKarier senior*Tahun Tim Tampil (Gol)1993-1995 Kashima Antlers * Penampilan dan gol di klub senior...

 

Balusu

Balusu Elops hawaiensis Status konservasiKekurangan dataIUCN194307 TaksonomiKerajaanAnimaliaFilumChordataKelasActinopteriOrdoElopiformesFamiliElopidaeGenusElopsSpesiesElops hawaiensis Regan, 1909 lbs Balusu[1] (Elops hawaiensis), juga dikenal sebagai ikan tenpounder atau ikan pisang, adalah spesies ikan bersirip pari dalam keluarga Elopidae. Ikan ini kadang-kadang disebut sebagai herring raksasa, meskipun tidak terkait erat dengan ikan herring sejati dari keluarga Clupeidae. Nama Hawa...

 

Hierarki memori

Hierarki memori adalah urutan prioritas dalam menggunakan sumber memori komputer. Hierarki memori terdiri dari beberapa lapisan, mulai dari memori yang paling cepat dan mahal hingga memori yang lebih lambat dan murah. Lapisan-lapisan ini meliputi: tembolok, memori akses acak, dan memori massal seperti hard disk drive (HDD) atau solid state drive (SSD). Data yang sering digunakan atau diakses disimpan pada lapisan memori yang lebih cepat dan lebih mahal, seperti cache dan RAM, sehingga memasti...

MV Empire City

World War II merchant ship of the United Kingdom History NameEmpire City OwnerMinistry of Transport OperatorA Weir & Co Ltd Port of registry Sunderland BuilderSwan, Hunter & Wigham Richardson Ltd Launched15 July 1943 CompletedNovember 1943 Identification Code Letters BFLB United Kingdom Official Number 180046 General characteristics TypeCargo ship Tonnage 7,295 GRT 4,941 NRT Length428 ft 8 in (130.66 m) Beam56 ft 5 in (17.20 m) Depth35 ft 5...

 

Marisela Escobedo Ortiz

Murdered Mexican social activist Marisela Escobedo OrtizPlaque indicating the place Ortiz was killedBornJune 12, 1958DiedDecember 16, 2010Chihuahua City, MexicoCause of deathMurderNationalityMexicanOccupation(s)Nurse, market store ownerKnown forSocial activismChildren5 Marisela Escobedo Ortiz[1][2] (June 12, 1958 – December 16, 2010) was a Mexican social activist from Juarez, Chihuahua, who was assassinated while protesting the 2008 murder of her daughter.[3 ...

 

Steven Sater

American poet Steven SaterBornEvansville, Indiana, United StatesAlma materWashington University in St. Louis Princeton UniversityOccupation(s)Poet, playwright, lyricist, television writer, screenwriter Steven Sater is a Tony Award, Grammy Award, and Laurence Olivier Award-winning American poet, playwright, lyricist, television writer and screenwriter. He is best known for writing the book and lyrics for the Tony Award-winning 2006 Broadway musical Spring Awakening.[1] Early life ...

Boeing 747SP

Boeing 747SP Un Boeing 747SP de l'Administration de l'aviation civile de Chine, compagnie mère de Air China, photographié en 1985 à l'aéroport de Paris-Charles-de-Gaulle. Rôle Avion de ligne à fuselage large très long courrier Constructeur Boeing Statut • En service limité en tant que charter, VIP ou avion gouvernemental• Un exemplaire converti en SOFIA Premier vol 4 juillet 1975 Mise en service 1976 avec la compagnie Pan Am Premier client • Pan American World Airways Client pr...

 

Libellus de expugnatione Terrae Sanctae per Saladinum

Opening page of the Libellus in the British Library's Cotton MS Cleopatra B. I The Libellus de expugnatione Terrae Sanctae per Saladinum (Little Book about the Conquest of the Holy Land by Saladin), also called the Chronicon terrae sanctae (Chronicle of the Holy Land), is a short anonymous Latin account of the conquests of Saladin (Ṣalāḥ al-Dīn) in the Holy Land between 1186 and 1191.[1][2] The core of the text was written shortly after the events it describes and then s...

 

Santander (Espagne)

Pour les articles homonymes, voir Santander. Santander Héraldique Drapeau Administration Pays Espagne Statut Commune Communauté autonome Cantabrie Province Cantabrie Comarque Santander District judic. Santander Budget 197 284 888 € (2018) Maire Mandat Gema Igual (es) (PP) 2023-2027 Code postal 39001 à 39012 Démographie Gentilé santanderino/a, santanderense (es) / Santanderien (fr) Population 172 726 hab. (2023) Densité 4 935 hab./km2 Géographie Coo...

Jean Foyer

French politician (1921–2008) Jean FoyerFrench Minister of JusticeIn office15 April 1962 – 6 April 1967PresidentCharles de GaullePrime MinisterGeorges PompidouPreceded byBernard ChenotSucceeded byLouis Joxe Personal detailsBorn(1921-04-21)21 April 1921Contigné, FranceDied3 October 2008(2008-10-03) (aged 87)Paris, France Jean Foyer (21 April 1921, Contigné, Maine-et-Loire – 3 October 2008, Paris) was a French politician and minister. He studied law and became a law profes...

 

NGC 2928

NGC 2928   الكوكبة الأسد[1]  رمز الفهرس NGC 2928 (الفهرس العام الجديد)PGC 27380 (فهرس المجرات الرئيسية)IRAS F09343+1712 (IRAS)2MASX J09371010+1658380 (Two Micron All-Sky Survey, Extended source catalogue)IRAS 09343+1712 (IRAS)MCG+03-25-005 (فهرس المجرات الموروفولوجي)Z 92-11 (فهرس المجرات وعناقيد المجرات)UZC J093710.1+165838 (فهرس زفيكي المحدّث)Z 0934.5+17...

 

Gangsa

Gangsa Gangsa merupakan sebuah instrumen yang tergabung dalam sebuah ensambel atau barungan gambelan yang bilahannya terbuat dari perunggu.[1] Menurut Bandem I Made, di dalam Sanjaya dkk, Gangsa merupakan seperangkat gamelan terdapat empat buah gangsa dan biasanya dimainkan untuk membuat elaborasi melodi dengan sistem yang dinamakan ubit-ubitan, kotekan, atau cecandetan, suatu pola permainan yang menggunakan polos (pada ketukan) dan sangsih diluar ketukan.[2] Gangsa terdiri da...

Emperor Go-Tsuchimikado

Emperor of Japan Emperor Go-Tsuchimikado後土御門天皇Emperor of JapanReignAugust 21, 1464 – October 21, 1500CoronationMay 22, 1465PredecessorGo-HanazonoSuccessorGo-KashiwabaraShōgunAshikaga YoshimasaAshikaga YoshihisaAshikaga YoshitaneBornFusahito (成仁)July 3, 1442DiedOctober 21, 1500(1500-10-21) (aged 58)BurialFukakusa no kita no Misasagi (深草北陵) (Kyoto)Issuemore...Emperor Go-KashiwabaraPosthumous nameTsuigō:Emperor Go-Tsuchimikado (後土御門院 or 後土御門天�...

 

2022年2月苏州市2019冠状病毒病聚集性疫情

  关于江苏省的2019冠状病毒病疫情情况，请见「2019冠狀病毒病江蘇省疫情」。 维基百科中的醫學内容仅供参考，並不能視作專業意見。如需獲取醫療幫助或意見，请咨询专业人士。詳見醫學聲明。 在這條目內未有標明年份的日期都代表是2022年。  若非特別註明，本條目所有時間皆為東八區標準時間（UTC+8）。 2022年2月苏州市2019冠状病毒病聚集性疫情位于苏州工�...

 

Addie McPhail

Questa voce sull'argomento attori statunitensi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Addie McPhail nel 1927 Addie Oakley Dukes (White Plains, 15 luglio 1905 – Canoga Park, 14 aprile 2003) è stata un'attrice statunitense, meglio nota con il cognome del primo marito, McPhail. Dal primo marito, il pianista e compositore Lindsay McPhail, ebbe una figlia, Marilyn. Nel 1932 sposò in seconde noz...

Journey from the Fall

Journey from the FallPoster rilis teatrikalSutradaraHam TranProduserLam NguyenHam TranDitulis olehHam TranPemeranKieu ChinhLong NguyenDiem LienCat LyPenata musikChristopher WongSinematograferGuillermo RosasJulie KirkwoodPenyuntingHam TranDistributorImaginAsian PicturesTanggal rilis 22 Februari 2006 (2006-02-22) (Festival Film Internasional Bangkok) 23 Maret 2007 (2007-03-23) (Amerika Serikat) Durasi135 menitNegaraAmerika SerikatBahasaVietnam Inggris Journey from the Fa...

 

2023 en Antarctique

Cet article est une ébauche concernant l’Antarctique. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Chronologies Données clés 2020 2021 2022  2023  2024 2025 2026Décennies :1990 2000 2010  2020  2030 2040 2050Siècles :XIXe XXe  XXIe  XXIIe XXIIIeMillénaires :Ier IIe  IIIe  Chronologies géographiques Afrique Afrique du Sud, Algérie, Angola, Bénin...

 

Musée de la Magie

Museum of magic, Paris, France This article is about the magic museum in Paris. For the magic museum in Blois, see La Maison de la Magie Robert-Houdin. Musée de la Magie The Musée de la Magie, also known as the Musée de la Curiosité et de la Magie and the Académie de la Magie, is a private museum located in the 4th arrondissement at 11, rue saint Paul, Paris, France. It is open several afternoons per week; an admission fee is charged. The museum occupies 16th-century cellars beneath the ...

Aleksandr Evtušenko

Questa voce sull'argomento ciclisti russi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Aleksandr EvtušenkoEvtušenko nel 2017.Nazionalità Russia Altezza185 cm Peso72 kg Ciclismo SpecialitàStrada, pista SquadraVelobayki CarrieraSquadre di club 2013Helicopters2014Russian Helicopters2015 RusVelo2016 Gazprom-RusVelo2017-2018Lokosphinx2019 Gazprom-RusVelo2020Spor Toto2021 Efapel2022-Velobayki Nazionale 2014- Russiapista2017-2...

 

Dormer

Structural element of a building For people named Dormer, see Dormer (surname). Dormer window of the Building of Préfecture de police de Paris (île de la Cité) Gable dormers at Hospices de Beaune in Beaune, France Pair of hip roof dormer windows on the Howard Memorial Hall, Letchworth A dormer is a roofed structure, often containing a window, that projects vertically beyond the plane of a pitched roof.[1] A dormer window (also called dormer) is a form of roof window. Dormers are co...