Bitonic sorteringsanlæg

Bitonic mergesort er en parallel algoritme til sortering. Det er også bruges som en konstruktion metode til at opbygge et sortering netværk. Algoritmen blev udtænkt af Ken Batcher. De resulterende sortering netværk består af komparatorer og har en forsinkelse på, hvor antallet af elementer, der skal sorteres.

En sorteret sekvens er en monotont ikke-aftagende sekvens. En bitonic er en sekvens med for nogle eller en cirkulær forskydning af en sådan sekvens.

Hvordan algoritmen fungerer

Det følgende er et bitonic sortering netværk med 16 indgange:

De 16 numre ind på indgangene på den venstre ende, glide langs hver af de 16 vandrette tråde, og exit ved udgangene på det rigtige ende. Netværket er designet til at sortere de elementer, med det største antal i bunden.

Pilene er komparatorer. Når to tal nå de to ender af en pil, er de i forhold til at sikre, at pilen peger mod det større antal. Hvis de er ude af drift, er de byttes. De farvede kasser er blot til illustration og ikke har nogen virkning på algoritmen.

Hver rød boks har den samme struktur: hver indgang i den øverste halvdel er i forhold til den tilsvarende indgang i den nederste halvdel, med alle pilene peger ned eller alle op. Hvis indgangene tilfældigvis danne en bitonic sekvens, så produktionen vil danne to bitonic sekvenser. Den øverste halvdel af output vil være bitonic og den nederste halvdel bliver bitonic, med hvert enkelt element i den øverste halvdel er mindre end eller lig med hvert enkelt element i den nederste halvdel eller vice versa. Denne sætning er ikke indlysende, men kan verificeres ved omhyggeligt at overveje alle de tilfælde af, hvordan de forskellige input kunne sammenligne, ved hjælp af nul-én-princippet.

De røde kasser kombineres for at danne blå og grønne bokse. Enhver sådan boks har den samme struktur: en rød boks påføres hele inputsekvens, derefter til hver halvdel af resultatet, derefter til hver halvdel af hver af disse resultater, og så videre. Alle pilene peger ned eller alle peger op. Denne struktur er kendt som en sommerfugl netværk. Hvis input til denne boks sker for at være bitonic, så produktionen vil være helt sorteret i stigende orden eller faldende orden. Hvis et nummer ind i blå eller grønne boks, så den første røde felt vil sortere det til den korrekte halvdel af listen. Det vil derefter passere gennem en mindre rød boks, der sorterer det i den rigtige fjerdedel af listen inden at halvdelen. Dette fortsætter, indtil det sorteres i nøjagtigt den korrekte position. Derfor vil outputtet fra den grønne eller blå boks være helt sorteres.

De grønne og blå bokse kombineres til dannelse af hele sortering netværket. For en vilkårlig sekvens af indgange, vil det sortere dem korrekt, med den største nederst. Udgangssignalet fra hver grøn eller blå boks vil være en ordnet sekvens, så produktionen af ​​hvert par af hosliggende lister bliver bitonic, fordi den øverste er blå og den nederste er grøn. Hver kolonne i blå og grønne bokse tager N sorteret sekvenser og sammenkæder dem parvis for at danne N / 2 bitonic sekvenser, som derefter Weaver boksene i kolonnen til dannelse af N / 2 sorteret sekvenser. Denne proces begynder med hver indgang anses for at være en ordnet liste over et element, og fortsætter gennem alle kolonner til sidste fletter dem i en enkelt, sorteret liste. Fordi den sidste fase var blå, vil det endelige liste har det største element i bunden.

Hver grønne boks udfører den samme funktion som en blå kasse, men med den slags i den modsatte retning. Så kunne hver grønne boks blive erstattet af en blå kasse efterfulgt af en crossover, hvor alle ledningerne flytte til den modsatte position. Dette vil give alle pilene til at pege i samme retning, men ville forhindre de vandrette linjer fra at være lige. Imidlertid kunne en lignende crossover placeres til højre for den nederste halvdel af udgangene fra enhver røde blok, og den slags vil stadig fungere korrekt, fordi bagsiden af ​​en bitonic sekvens er stadig bitonic. Hvis en rød boks har så en crossover før og efter det, kan det være omarrangeret internt, så de to delefiltre annullere, så ledningerne bliver lige igen. Derfor følgende diagram svarer til den ovenfor, hvor hver grønne boks er blevet et blåt plus en crossover, og hver appelsin boks er en rød boks, der absorberes to sådanne crossovers:

De pilespidser er ikke tegnet, fordi hver komparator sorterer i samme retning. De blå og røde blokke udføre de samme operationer som før. De orange blokke svarer til røde blokke, hvor sekvensen ordre er vendt til den nederste halvdel af sine input og den nederste halvdel af sine udgange. Dette er den mest almindelige repræsentation af en bitonic sortering netværk.

Eksempel kode

Det følgende er en implementering af bitonic mergesort sortering algoritme i Python. Indgangen er en boolesk værdi op, og en liste x længde en effekt på 2. Udgangen er en sorteret liste, der stiger op, hvis op er sandt, og faldende andet.

  0   0
Forrige artikel Alex Kipchirchir
Næste artikel Chien-Ming Wang

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha