Heltalssortering

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 januari 2021; kontroller kräver 2 redigeringar .

Heltalssortering  är uppgiften att sortera någon uppsättning värden med heltalsnycklar . Heltalssorteringsalgoritmer kan också användas för problem där nycklarna är flyttal eller textsträngar [1] . Möjligheten att utföra heltalsaritmetiska operationer på nycklar gör att heltalssorteringsalgoritmer i många fall kan vara snabbare än liknande sorteringsalgoritmer som använder jämförelser, beroende på de operationer som tillåts i beräkningsmodellen och storleken på nyckeltalen.

De vanliga heltalssorteringsalgoritmerna: basket sort , radix sort , counting sort används ofta och är effektiva [2] [3] . Ytterligare forskning om heltalssorteringsalgoritmer har fokuserat på värsta tänkbara teoretiska förbättringar, och de algoritmer som har erhållits anses inte vara effektiva på moderna 64-bitars datorer, även om experiment har visat att vissa av dessa metoder kan vara bättre än bitvis sortering av data med 128 eller fler bitar på tangenten [4] . För stora datamängder är den nästan slumpmässiga minnesåtkomstnaturen för heltalssorteringsalgoritmer en begränsning, särskilt jämfört med andra sorteringsalgoritmer som har utformats med en hierarkisk minnesstruktur i åtanke .

Heltalssortering används i ett av de sex riktmärkena i DARPA High Productivity Computing Systems Discrete Mathematics-svit och i ett av de elva kriterierna i NAS Parallel Benchmarks-sviten [5] .

Beräkningsmodeller

Tidsbegränsningarna för heltalssorteringsalgoritmer beror vanligtvis på tre parametrar:  - antalet datavärden som ska sorteras,  - storleksordningen på största möjliga nyckel, och  - antalet bitar i datorns maskinord på vilken algoritmen kommer att exekveras. Det antas generellt att , det vill säga maskinorden är tillräckligt stora för att representera både indexet i inmatningssekvensen och tangenten [6] .

Heltalssorteringsalgoritmer är i allmänhet utformade för att fungera antingen för pekmaskineneller för en maskin med slumpmässig tillgång till minnet . Huvudskillnaden mellan dessa modeller är att direktåtkomstmaskiner låter dig använda ett godtyckligt värde i ett register som en minnesadress i läs- och skrivoperationer med ett tidsenhetsvärde, och organisera komplexa datamanipulationer med hjälp av en uppslagstabell . Pekarmaskinsmodellen tillåter endast åtkomst till minnet genom pekare, som inte kan manipuleras med aritmetiska operationer. I båda modellerna kan bitvisa operationer utföras, som regel, i en tidsslice . Olika heltalssorteringsalgoritmer gör olika antaganden om huruvida heltalsmultiplikation kan utföras i en tidsdel [6] [7] . Mer specialiserade beräkningsmodeller, såsom parallella maskiner med slumpmässig åtkomst [8] [9] [10] [11] [12] , kan också övervägas .

Det visades 1999 att i vissa fall kan multiplikationen eller tabellsökningen som krävs för vissa heltalssorteringsalgoritmer ersättas av specialiserade operationer som enkelt kan implementeras i hårdvara men som normalt inte är tillgängliga på datorer för allmänna ändamål [7] .

Anteckningar

  1. ↑ Han, Thorup, 2002 .
  2. ↑ McIlroy, Bostic, McIlroy, 1993 .
  3. ↑ Andersson, Nilsson, 1998 .
  4. ↑ Rahman, Raman, 1998 .
  5. ↑ DARPA HPCS Discrete Mathematics Benchmarks Arkiverad 10 mars 2016 på Wayback Machine , Duncan A. Buell, University of South Carolina, hämtad 2011-04-20.
  6. ↑ 1 2 Fredman, Willard, 1993 .
  7. ↑ 1 2 Andersson, Miltersen, Thorup, 1999 .
  8. ↑ Reif, 1985 .
  9. ↑ Cole, Vishkin, 1986 , Kommentar.
  10. ↑ Hagerup, 1987 .
  11. ↑ Bhatt et al., 1991 .
  12. ↑ Albers, Hagerup, 1997 .

Litteratur