Abstract-I detta dokument föreslår vi en ny sorteringsalgoritm som sorterar inmatningsdata heltal element on-the-fly utan någon jämförelse mellan data-jämförande-fri sortering. Vi presenterar en komplett maskinvarustruktur, tillhörande tidsdiagram, och ett formellt matematiskt bevis, som visar en total sorteringstid, i termer av klockcykler, som är linjärt proportionell mot antalet ingångar, vilket ger en hastighet komplexitet i ordningen O(N). Vår hårdvarubaserade sorteringsalgoritm utesluter behovet av SRAM-baserat minne eller komplexa kretsar, såsom rörläggningsstrukturer, men använder istället enkla register för att hålla de binära elementen och elementens tillhörande antal förekomster i inmatningsmängden, och använder matrismappning för att utföra sorteringsprocessen. Således är den totala transistorn komplexiteten i ordningen O(N). Vi utvärderar en applikation specificerad integrerad kretsdesign av vår sorteringsalgoritm för en provsortering av N = 1024 element av storlek K = 10-bitars med 90-nm Taiwan Semiconductor Manufacturing Company (TSMC) teknik med en 1 V strömförsörjning. Resultaten bekräftar att vår sortering kräver ungefär 4-6 μs för att sortera 1024 element med en klockcykeltid på 0,5 GHz, förbrukar 1,6 mW effekt och har ett totalt transistorantal på mindre än 750 000. Index Terms-90-nm TSMC, jämförelsefri, Gigahertz klockcykel, en het vikt representation, sorteringsalgoritmer, SRAM, hastighetskomplex O(N).
Abdel-Hafeez m.fl. Ref föreslog en ny matematisk sorteringsalgoritm utan jämförelse som sorterar indata heltal element i farten utan några jämförelseoperationer.
An Efficient O( $N$ ) Comparison-Free Sorting Algorithm
{'venue': 'IEEE Transactions on Very Large Scale Integration (VLSI) Systems', 'journal': 'IEEE Transactions on Very Large Scale Integration (VLSI) Systems', 'mag_field_of_study': ['Computer Science']}