Алгоритъмът за сортиране тази седмица ще бъде малко по-различен в сравнение с другите алгоритми за сортиране. С Radix Sort ние не сравняваме две стойности въз основа на: „едната по-голяма ли е от другата?“, вместо това сортираме данните по: двоични числа, а не чрез сравняване на елементи.
Radix сортирането работи върху списъци с числа или двоични данни, НЕ чрез сравняване на елементи. Колкото повече цифри, толкова по-голямо е числото. И начинът, по който сортираме с радикс, е като сортираме числата през 10 различни групи. Тези кофи се използват повторно, докато не преминем през сортирането на цифрите и всяка кофа представлява число от 0 до 9 или основа 10.
Ние организираме числата по ред, въз основа на стойността на числото първо в позиция 1s и след това отново преглеждаме числата в 10s, 100s и така нататък, и така нататък.
Така че, ако трябва да сортираме следния списък с числа:
3, 92, 11, 214, 3160, 26, 817, 2000, 33
ние първо сортираме по числата в едноцифрената позиция първо. Значи числата:
3, 92, 11, 214, 3160, 26817200033ще бъдат сортирани в :
3160, 2000, 11, 92, 3, 33, 214, 26, 817
Разглеждаме само едноцифрената стойност, а не останалите цифри в числата. В следващото изпълнение на нашия сорт ще разгледаме стойностите на мястото на десетките. И нашият следващ сортиран списък ще бъде:
2000, 3, 11, 214, 817, 26, 33, 3160, 92
Ще повторим този процес за стотици и хиляди, докато стигнем до нашия сортиран списък. Ако забележите на изображението по-горе, 3 се сортира в кофата на 0. Тъй като цифрите за това число ни свършиха (3 няма цифра на мястото на десетките), всичко отляво на числото ще получи въображаема стойност 0. Това позволява на номера да задържи мястото си в сортирания списък. Броят пъти, през които преминаваме през този процес на сортиране, зависи от броя на цифрите в най-голямото число. В този случай най-голямото число има 4 цифри, така че преминаваме през този процес 4 пъти.
Стотици:
2000, 3, 11, 26, 33, 92, 3160, 2 14, 817
хиляди:
3, 11, 26, 33, 92, 214, 817, 2000, 3160
И така, как да внедрим това в код?
Помощни методи (от Stack Overflow)
getDigit(число, място)
— връща цифрата вътре в числото на дадената стойност на място. Така че, ако нашето число е 365 и мястото е 0, цифрата е 5, ако мястото е 1, цифрата е 6, а ако мястото е 2, цифрата е 3.
function getDigit(number, place) {
return Math.floor(Math.abs(number) / Math.pow(10, place)) % 10;
}Например да приемем, че нашето число е 365, а мястото е 2. Math.abs(number) гарантира, че дори ако имаме работа с отрицателни стойности, числото няма да бъде върнато като отрицателно, така че ние просто боравят с абсолютни числа. Math.pow(10, place) връща 10 на степен на място или в този случай 10 на 2-ра степен. И получаваме 100. След това Math.floor(365/100), което е 3. И накрая намираме 3 % 10, което връща 3.
Изглежда като:
getDigit(365, 2)
Math.abs(365) =› 365
Math.pow(10, 2) =› 100
Math.floor (365/100) =› 3
3%10 =› 3
digitCount(число)
— това ще върне колко цифри има в числото. Така че, ако числото е 365, digitCount връща 3. Трябва да включим крайния случай под if (num === 0) return 1, защото ако изпълним Math.log10(Math.abs(0)) изходът ще бъде-Infinity.
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}Например, ако нашето число отново е 365, Math.log10(365) е 2.5622928644564746 и ако Math.floor(2.5622928644564746) стойността е 2. Накрая добавяме едно ,2+1 и получаваме дължината на нашето число, 3.
mostDigits(numbers)
—вземайки списък с числа, този метод ни казва какъв е размерът на най-голямото число в списъка. Ако това бяха нашите числа, [1000, 1786300, 365], повечето цифри биха върнали 7.
function mostDigits(nums) {
let maxDigits = 0;
for (let num of nums) {
maxDigits = Math.max(maxDigits, digitCount(num));
}
return maxDigits;
}Например, да кажем, че mostDigits приема този списък с числа: [1000, 1786300, 365]. Първо декларираме променлива maxDigits, равна на 0. Преминаваме през всеки номер от списъка с числа или num of nums, за да сравним дължината на цифрата и да присвоим максималната стойност на променливата maxDigits. Зад капака това изглежда така:
1. maxDigits = Math.max(0, digitCount(1000))
кое е по-голямо, 0 или 4? =› maxDigit = 4
2. maxDigits = Math.max(4, digitCount(1786300))
кое е по-голямо, 4 или 7? =› maxDigit = 7
3. maxDigits = Math.max(7, digitCount(365))
кое е по-голямо, 7 или 3? =› maxDigit = 7
Върнете 7
Внедряване на Radix Sort…
- Нашата функция ще приеме списък с числа
- Намерете максималния брой цифри на най-голямото число в списъка с числа
- Създайте цикъл с променлива k, започваща от 0 и достигаща до стойността на максималния брой цифри от най-голямото число.
• където във всеки цикъл създаваме кофи за всяка цифра (0–9)
• И поставете всяко число в правилната кофа въз основа на индекса на k за това число (т.е. 0 е единиците, 1 е 10-те, 2 е 100-те и т.н.). - Заменете нашия съществуващ масив със стойности от кофите от 0 до 9
- И накрая, върнете сортирания списък с числа.
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}Нека разбием това (пълният кодов фрагмент по-долу):
Първо:Взимаме списък с числа и декларираме променлива maxDigitCount, която е дължината на най-голямото число в списъка.
Примерни числа: [90, 881, 16, 320722, 531, 5, 91, 4760]
maxDigitCount = 6, тъй като 320722 е най-голямото число и в него има 6 цифри.
Второ:След това вътре в цикъл декларираме променлива kкоято представлява мястото на числото (1s, 10s, 100s, 1000s)
Вътре в k цикъл декларираме променлива, наречена digitBuckets, и вътре в тази променлива създаваме хеш от 10 празни масива ([]).
Трето:Създаваме вложен цикъл с променлива iкоято представлява текущото число в списъка, през който преминаваме, в този случай започваме от 0 от 8 числа. Докато i е по-малко от дължината на списъка с числа (8), ние ще увеличим i.
Четвърто:Във вложения iцикъл, ние декларираме променлива digit = getDigit(nums[i], k)и след това въз основа на цифрата, вкарваме числото в digitBucket с digitBuckets[digit].push(nums[i]).
Пример: Първа итерация на i:
цифра = getDigit(nums[0], k=0)
nums[0] = 90
цифра = 0< br /> digitBuckets[0].push(90)
Пример: Второ повторение на i:
цифра = getDigit(nums[1], k=0)
nums[1] = 881
цифра = 1< br /> digitBuckets[1].push(881)
Пример: Трета итерация на i:
цифра = getDigit(nums[2], k=0)
nums[2] = 16
цифра = 6< br /> digitBuckets[6].push(16)
Пето: След като завършим вложения цикъл, присвояваме отново стойността на nums в нов масив, свързвайки числата по ред от digitBuckets.
Пример: Първа итерация на k:
nums = [90, 881, 16, 320722, 531, 5, 91, 4760]
digitBuckets = {
0: [90, 4760],
1: [881,531, 91],
2: [320722],
3: [],
4: [],
5: [5],
6: [16],
7: [],
8: [],
9: []
}
nums = [].concat(…digitBuckets)
=› [90, 4760, 881, 531, 91, 320722, 5, 16]
Последна стъпка: повтаряме всички предишни стъпки, докато k вече не е по-малко от maxDigitCount, и накрая връщаме сортирания списък с числа.
function getDigit(number, place) {
return Math.floor(Math.abs(number) / Math.pow(10, place)) % 10;
}
function digitCount(num) {
if (num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
let maxDigits = 0;
for (let num of nums) {
maxDigits = Math.max(maxDigits, digitCount(num));
}
return maxDigits;
}
function radixSort(nums){
let maxDigitCount = mostDigits(nums);
for(let k = 0; k < maxDigitCount; k++){
let digitBuckets = Array.from({length: 10}, () => []);
for(let i = 0; i < nums.length; i++){
let digit = getDigit(nums[i],k);
digitBuckets[digit].push(nums[i]);
}
nums = [].concat(...digitBuckets);
}
return nums;
}