U računarstvu , celobrojno sortiranje je algoritam koji sortira i prikuplja podatke numeričkih vrednosti, od kojih je svaka ceo broj. Algoritam dizajniran za celobrojo sortiranje, može se upotrebiti i za sortiranje podataka koji su tipa float ili tipa string. Mogućnost da izvršava aritmetiku nad celobrojnim vrednostima, omogućava celobrojnom sortiranju da bude brže od sortiranja poređenjem u mnogim slučajevima, u zavisnosti od toga koje su operacije dozvoljene u modelu računarstva i koliko su velike celobrojne vrednosti koje treba sortirati.
Klasični algoritam celobrojnog segmentnog sortiranja, counting sortiranja i radix sortiranja su najčešće korišćeni i najpraktičniji.; Mnogo kasnije istraživanja o algoritmu celobrojnog sortiranja usmerena su više na praktičnost nego na teorijska poboljšanja u najgorem slučaju , i algoritmi koji dolaze iz ove pretrage nisu praktični na 64-bitnoj arhitekturi računara, takođe eksperimenti su pokazali da neke od ovih metoda mogu biti poboljšanja na radix sortiranju za podatke koji sadrže 128 ili više bita po ključu. Pored toga, za velike podatke,modeli približno slucajanog pristups memoriji mnogih algoritma celobrojnog sortiranja mogu ih sputati za razliku od sortiranja poređenjem koje je dizajnirano sa hijararhijom memorije na umu. Celobrojno sortiranje pruža jednu od šest testova u DARPA High Productivity Computing System Discrete Mathematics benchmark suiteDARPA HPCS Discrete Mathematics Benchmarks , Duncan A. Buell, University of South Carolina, retrieved 2011-04-20. . I jedan od 11 testova u NAS Parallel Benchmarks.
Model računanja Vreme izračunavanja celobrojnog sortiranja zavisi od tri parametra: da broj n bude sortiran, da veličina K najvećeg ključa bude sortiran, a broj bitova w može biti predstavljen na mašinskom jeziku računara na algoritmu koji se koristi. Tipično, pretpostavlja se da je ; to jest, da je mašinski jezik dovoljno veliki da predstavi indeks u nizu ulaznih podataka i da je dovoljno veliki da predstavi samostalan ključ. Algoritam celobrojnog sortiranja je obično dizajniran da radi bilo u modelima računanja bilo pokazivačkim ili automatima slučajnog pristupa, glavnna razlika između ova dva modela je u tome što sa slučajnim pristupom mašina omogućava da svaka vrednost koja se čuva u registrima koji će se koristiti kao adresa memorije, čita i piše operacije, sa cenom po jedinici rada, što omogućava određene kompleksne operacije nad podacima koji se brzo nalaze korišćenjem lookup tabela. Nasuprot tome, pokazivački model omogućava pristup memoriji samo preko pokazivača na memoriju koja se ne može koristiti koristeći aritmetičke operacije. U oba modela, dodatak, boolean operacije i binarne operacije pomeranja obično se mogu ostvariti u jednici vremena po operaciji. Različiti algoritmi sortiranja imaju različite pretpostavke, kako god bilo, celobrojno množenje se takođe obavlja u jedinici vremena po operaciji.The question of whether integer multiplication or table lookup operations should be permitted goes back to ; see also Drugi specijalizovani modeli računanja kao paralelan pristup memoriji će takođe biti razmatrani.;comment in ; ; ;
su pokazali da u nekim slučajevima kod množenja ili lookup tabele je potrebno da neki algoritmi celobrojnog sortiranja mogu biti zamenjeni pojedinim operacijama koje bi bile mnogo lakše da bi se lakše realizovale u hardveru, ali obično nisu dostupni na računarima opste namene. , dokazao je kako se mogu zameniti ove operacije bitovskim poljima manipulišući instrukcijama koje su dostupne na Pentium procesorima.
Sortiranje u odnosu na primarni red Moguće je da osnova algoritma sortiranja selekcijom bilo kog niza struktuiranih podataka, koja omogućava jedan od glavnih skupova od n elemenata sa ključem u intervalu od to , u zavisnosti od operacije, da pronađe i ukloni stavku sa minimalnim ključem. Jednostavno se kreira prioritetni niz koji sadrži sve elemente, zatim se više puta primenjuje minimalno brisanje dok se niz ne isprazni. Deo niza čiji je element izbrisan, sada je sortiran deo niza. Vreme za stvaranje ovog algoritma je vreme za kreiranje niza, plus vreme za n minimalnih operacija brisanja. Na primer, kod algoritma sortiranja poređenjem, heap sortiranje ima ovu formu. Kako god bilo, takođe postoje algoritmi ovog tipa koji su brži za celobrojne ključeve, na osnovu prioritetnih redova struktuiranih podataka koji su specijalizovani za cele brojeve.
Konkretno, van Emde Boas stablo može da se koristi kao priopitetni red da sortira niz od n kljuceva, gde je svaki u opsegu od to , u vremenskoj složenosti . To je teoretsko poboljšanje u odnosu na radix sortiranje kada je K dovoljno veliko. Međutim, da bi se koristilo van Emde Boas-ovo stablo, jedan ili treba direktno adresibilnu memoriju K reči, ili mora da se simulira pomoću Heš tabela, smanjujući tako linearni prostor, praveći algoritam slučajnim. Drugi prioritetni red sa sličnim performansama (uključujući potrebu randomizacije putem Heš tabela) je Y –brzo stablo koje je osmislio . je pokazao kako jednakost između prioritetnih redova ide u drugom smeru: ako je moguće izvšiti celobrojno sortiranje u vremenu po ključu, onda je isto vreme potrebno za ubacivanje ili brisanje operacije u primarnom redu. Throup - ova redukcija je komplikovana i podrazumeva dostupnost bilo brzih operacija množenja ili lookup tabele, ali takođe pruža alternativni prioritetni red koristeći samo sabiranje i logičke operacije sa vremenom po operaciji, nајviše množenjem vremenа od strаne iterativnog algoritma.
Algoritam za male ključeve Odavno je poznato da segmentno sortiranje ili counting sortiranje mogu da sortiraju niz od n ključeva, svaki u opsegu od do , u vremenu . U segmentnom sortiranju, pokazivači na podatke distribuirani su u tabelu "bucket" (predstavljena kao vrsta povezanih listi) koristeći ključeve kao pokazivače u tabeli. Onda, su svi podaci spojeni tako da formiraju izlaznu listu.. Note that, although also describe a version of bucket sort, the version they describe is adapted to inputs where the keys are real numbers with a known distribution, rather than integer sorting. U counting sortiranju, bucket je zamenjen brojačem koji određuje broj podataka koji imaju istu vrednost, a zatim prefix suma se koristi da se odredi podniz, u izlaznom nizu, gde bi trebalo da se nalaze podaci sa istom vrednošću., 8.2 Counting Sort. стр. 168–169. Radix sortiranje je algoritamska tehnika u kojoj se neki drugi algoritam koji je odgovarajuć samo za male ključeve ponavlja, praveći algoritam koji se može upotrebiti na veće ključeve. Ključ koji je upotrebljen za i –ti korak drugog algoritma za sortiranje, je i –ta cifra pozicije celog ključa, prema radix sortiranju, počev od cifre najmanje težine i napreduje u najznačajnije. Da bi ovaj algoritam radio, osnova algoritma mora biti stabilna, podaci sa istim ključem ne bi trebali da menjaju pozicije među sobom. Koristeći radix sortiranje, radixom da se izabere proporcionalno n, sa segmentnim sortiranjem i counting sortiranjem u osnovi , moguće je sortirati niz od n ključeva, svaki u opsegu od to , u vremenu . Koristeći 2n radix omogućava da ključ osnovnog algoritma bude napravjen koristeći samo binarno pomeranje i maskiranje.; , 8.3 Radix Sort. стр. 170–173. Sofisticiranije tehnike sa sličnim ukusom i boljim performansama teorijski je razvio . Oni su primetili da svaki prolazak kroz radix sortiranje može da se tumači kao „smanjenje opsega“ tehnike koja, u linearnom vremenu, smanjuje maksimalne veličine ključeva za faktor n, umesto toga, njihova tehnika smanjuje veličinu ključa u kvadratnom korenu na kvadratni koren svoje ranije vrednosti (prepolovi broj bitova potrebnih za predstavljanje ključa), takođe u linearnom vremenu. Kao i u radix sortiranju, oni predstavljaju ključeve kao dvocifrene brojeve u osnovi b, gde je osnova b približno koren iz . Onda se stavke grupišu i sortiraju se bucket sortiranjem u skladu sa svojim ciframa najveće težine, u linearnom vremenu, koristeći veliku ali neinicijalizovanu direktnu adresnu memoriju ili heš tabele. Svako segmentno sortiranje ima svog predstavnika: stavka sa najvećim ključem, oni zatim sortiraju listu podataka koristeći kao ključ cifre najveće težine kao predstavnike i cifre najmanje težine kao ne predstavnike.
Grupisanjem stavki sa liste segmentnim sortiranjem, svaki deo segmentnog sortiranja se može postaviti u sortiranom redosledu, a izdvajanjem predstavnika iz sortirane liste segmenti se mogu spojiti u sortiranom redosledu. Tako, u linearnom vremenu, problem sortiranja se svodi na drugi problem rekurzivnog sortiranja u kom su ključevi mnogo manji, kvadratni koren svoje prethodne veličine. Ovaj postupak se ponavlja sve dok ključ ne postane dovoljno mali da segmentno sortiranje dovodi do vremena izvršavanja .
Komplikovani slučajno algoritam omogućavada ova ograničenja budu umanjena još više, od .
Algoritmi za nekoliko stavki Algoritam celobrojnog sortiranja je neumeren ako se zahteva reč koja je veličine w koja je znatno veća .; Kao ekstremni primer, ako je , i svi ključevi su različiti, onda ključevi mogu biti sortirani predstavljajući ih kao bitovski niz, sa jednim bitom na poziciji i gde je i jedan od ulaznih ključeva, a zatim se više puta ukljanja bit najmanje težine. Neumereno packed sortiranje koje je osmislio koristi podprogram, koji je baziran na Ken Batcher - ovom paralelnom sortiranju mreže, za spajanje dve sortirane sekvence ključa gde je svaki od njih dovoljno kratak da se pakuje u jednoj mašinskoj reči. Ulaz u složeni sortirajući algoritam, niz predmeta složenih jedan po jedan reči, transformiše se u sabijenu formu, svaki niz reči drži više predmeta u složenom redu, koristeći ovaj potprogram udvostručvava broj jedinica pakovanih u svakoj reči. Kada je niz u zapakovanoj formi, Albers and Hagerup koriste formu sortiranja spajanjem da ih sortira, kada se dve sekvence spoje u jednu dužu sekvencu, istim paralelnim sortiranjem potprogram može da se koristi više puta za izdvajanje pakovanih reči sastavljenih od najmenjih preostalih elemenata od dve sekvence. Ovaj algoritam dobija dovoljnu brzinu od svoje reprezentacije da sortira ulaz u linearnom vremenu kad god je to moguće za jednu reč koja sadrži ključeva; tj, gde je za neku konstantu . Algoritam za velike reči segmentno sortiranje, counting sortiranje, radix sortiranje ivan Emde Boas - ovo stablo najbolje radi za ključeve male veličine, jer sa dovoljno velikim ključevima, oni postaju sporiji od algoritma za sortiranje poređenjem. Međutim, kada je veličina ključa ili veličina reči veoma velika u odnosu na broj jedinica (ili ekvivalentna kada je broj jedinica mali), moguće je sortirati algoritmom quick sortiranja, koristeći različite algoritme koji koriste prednosti urođenog paralelizma sa mogućnošću da obavljaju aritmetičke operacije na velikim rečima.
Rani rezultat u tom pravcu dali su ) koristeći jedinicu uzorka modela izračunavanja(veštački model u kome se složenost algoritma meri samo po broju pristupa memoriji koje obavi). Oslanjajući se na svoj rad, opisali su dve strukture, Q-heap i automatski heap, koje su primenljive na automate sa slucajnim pristupom. Q-heap je paralelna verzija binarnog stabla, i omogućava operacije prioritetnih nizova kao i da odabiranje naslednika i pretka bude obavljeno neprekidno za setove predmeta, gde je veličina tabele pre izračunavanja potrebna za implementiranje strukture podataka. Atomski heap je B-stablo u kome je svaki čvor drveta predstavljen kao Q-heap; dozvoljava operacije prioritetnih redova u konstantnom vremenu za stavki.