Een sorteeralgoritme is een algoritme om elementen van een lijst in een bepaalde volgorde zet. De meest gebruikte orders zijn numerieke volgorde en lexicografische volgorde. Efficiënt sorteren is belangrijk voor het optimaliseren van het gebruik van andere algoritmen (zoals zoeken en samenvoegen algoritmen) waarvoor gesorteerde lijsten te werken correct; het is ook vaak nuttig voor de canonicalizing van gegevens en voor het produceren van leesbare output. Meer formeel, de uitvoer moet voldoen aan twee voorwaarden:
1. de uitvoer is in niet aflopende volgorde (elk element is niet kleiner zijn dan het vorige element de gewenste totale volgorde);
2. de output is een permutatie (herschikking) van de ingang.
-Sorteren is een van de belangrijkste functies
vereist voor vele toepassingen zoals decoders voor digitale communicatie, digitale signaalverwerking, VLSI CAD enz. Dientengevolge, is er enorme belangstelling voor het versnellen van het sorteren in zowel software als hardware.
-De tijd die nodig is in de sortering is afhankelijk van aantal woorden in het geval van softwarealgoritmen de verbetering die we proberen te maken in dit project is om de tijd afhankelijk van het aantal bits per woord k en niet het aantal woorden
Probleemstelling:
Traditionele sorteren algoritmen zoals bubble sorteren, insertion sort, samenvoegen sorteren en nog veel meer hebben een basisscenario waarvoor het verwisselen van twee gegevenselementen tegelijk. Zelfs tijdens het gebruik van een combinatie van twee sorteer-algoritmen zoals het gebruik van snelle sorteren en samenvoegen sorteren samen sorteren van een matrix van getallen, impliceert het basisscenario nog slechts twee gegevenselementen wisselen op een bepaald moment. Vandaar de motivatie om te verkennen sorteren algoritmen geïmplementeerd via hardware vloeit voort uit het feit dat door de hardware een kunnen beter profiteren van parallellisme, waardoor veel nummers tegelijk sorteren.
Parallellisme niet alleen zorgt concurrency, maar ook is gericht op het verminderen van de tijd complexiteit van algoritmen. Vandaar is het probleem bij de hand te ontwikkelen van een nieuwe sorteer-algoritme en deze in hardware omzetten zodat het parallellisme extracten.
