Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitafd5617

Browse files
committed
Code style fixes for RadixSort.
1 parent7198533 commitafd5617

File tree

4 files changed

+157
-97
lines changed

4 files changed

+157
-97
lines changed

‎src/algorithms/sorting/SortTester.js

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,6 @@ export const sortedArr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
22
exportconstreverseArr=[20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1];
33
exportconstnotSortedArr=[15,8,5,12,10,1,16,9,11,7,20,3,2,6,17,18,4,13,14,19];
44
exportconstequalArr=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
5-
exportconststringArr=['zzz','bb','a','rr','rrb','rrba'];
6-
exportconstintArr=[3,1,75,32,884,523,4343456,232,123,656,343];
75

86
exportclassSortTester{
97
statictestSort(SortingClass){
Lines changed: 21 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,29 @@
11
#Radix Sort
22

3-
In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. A positional notation is required, but because integers can represent strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
3+
In computer science,**radix sort** is a non-comparative integer sorting
4+
algorithm that sorts data with integer keys by grouping keys by the individual
5+
digits which share the same significant position and value. A positional notation
6+
is required, but because integers can represent strings of characters
7+
(e.g., names or dates) and specially formatted floating point numbers, radix
8+
sort is not limited to integers.
49

510
##Efficiency
611

7-
The topic of the efficiency of radix sort compared to other sorting algorithms is somewhat tricky and subject to quite a lot of misunderstandings. Whether radix sort is equally efficient, less efficient or more efficient than the best comparison-based algorithms depends on the details of the assumptions made. Radix sort complexity is O(wn) for n keys which are integers of word size w. Sometimes w is presented as a constant, which would make radix sort better (for sufficiently large n) than the best comparison-based sorting algorithms, which all perform O(n log n) comparisons to sort n keys. However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n for a random-access machine to be able to store them in memory, which gives at best a time complexity O(n log n).[2] That would seem to make radix sort at most equally efficient as the best comparison-based sorts (and worse if keys are much longer than log n).
8-
9-
The counter argument is that comparison-based algorithms are measured in number of comparisons, not actual time complexity. Under some assumptions the comparisons will be constant time on average, under others they will not. Comparisons of randomly generated keys takes constant time on average, as keys differ on the very first bit in half the cases, and differ on the second bit in half of the remaining half, and so on, resulting in an average of two bits that need to be compared. In a sorting algorithm the first comparisons made satisfies the randomness condition, but as the sort progresses the keys compared are clearly not randomly chosen anymore. For example, consider a bottom-up merge sort. The first pass will compare pairs of random keys, but the last pass will compare keys that are very close in the sorting order. This makes merge sort, on this class of inputs, take O(n (log n)2) time. That assumes all memory accesses cost the same, which is not a physically reasonable assumption as we scale n to infinity, and not, in practice, how real computers work.
12+
The topic of the efficiency of radix sort compared to other sorting algorithms is
13+
somewhat tricky and subject to quite a lot of misunderstandings. Whether radix
14+
sort is equally efficient, less efficient or more efficient than the best
15+
comparison-based algorithms depends on the details of the assumptions made.
16+
Radix sort complexity is`O(wn)` for`n` keys which are integers of word size`w`.
17+
Sometimes`w` is presented as a constant, which would make radix sort better
18+
(for sufficiently large`n`) than the best comparison-based sorting algorithms,
19+
which all perform`O(n log n)` comparisons to sort`n` keys. However, in
20+
general`w` cannot be considered a constant: if all`n` keys are distinct,
21+
then`w` has to be at least`log n` for a random-access machine to be able to
22+
store them in memory, which gives at best a time complexity`O(n log n)`. That
23+
would seem to make radix sort at most equally efficient as the best
24+
comparison-based sorts (and worse if keys are much longer than`log n`).
1025

1126
##References
1227

13-
-[Wikipedia](https://en.wikipedia.org/wiki/Radix_sort)
28+
-[Wikipedia](https://en.wikipedia.org/wiki/Radix_sort)
29+
-[YouTube](https://www.youtube.com/watch?v=XiuSW_mEn7g&index=62&t=0s&list=PLLXdhg_r2hKA7DPDsunoDZ-Z769jWn4R8)
Lines changed: 133 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -1,96 +1,27 @@
11
importSortfrom'../Sort';
22

3+
// Using charCode (a = 97, b = 98, etc), we can map characters to buckets from 0 - 25
4+
constBASE_CHAR_CODE=97;
5+
constNUMBER_OF_DIGITS=10;
6+
constENGLISH_ALPHABET_LENGTH=26;
7+
38
exportdefaultclassRadixSortextendsSort{
9+
/**
10+
*@param {*[]} originalArray
11+
*@return {*[]}
12+
*/
413
sort(originalArray){
5-
constisNumber=(element)=>{
6-
returnNumber.isInteger(element);
7-
};
8-
9-
constcreateBuckets=(numBuckets)=>{
10-
/**
11-
* Mapping buckets to an array instead of filling them with
12-
* an array prevents each bucket from containing a reference to the same array
13-
*/
14-
returnnewArray(numBuckets).fill(null).map(()=>[]);
15-
};
16-
17-
constplaceElementsInNumberBuckets=(array,index)=>{
18-
// See below. These are used to determine which digit to use for bucket allocation
19-
constmodded=10**(index+1);
20-
constdivided=10**index;
21-
constbuckets=createBuckets(10);
22-
23-
array.forEach((element)=>{
24-
this.callbacks.visitingCallback(element);
25-
if(element<divided){
26-
buckets[0].push(element);
27-
}else{
28-
/**
29-
* Say we have element of 1,052 and are currently on index 1 (starting from 0). This means
30-
* we want to use '5' as the bucket. `modded` would be 10 ** (1 + 1), which
31-
* is 100. So we take 1,052 % 100 (52) and divide it by 10 (5.2) and floor it (5).
32-
*/
33-
constcurrentDigit=Math.floor((element%modded)/divided);
34-
buckets[currentDigit].push(element);
35-
}
36-
});
37-
38-
returnbuckets;
39-
};
40-
41-
constplaceElementsInCharacterBuckets=(array,index,numPasses)=>{
42-
constgetCharCodeOfElementAtIndex=(element)=>{
43-
// Place element in last bucket if not ready to organize
44-
if((numPasses-index)>element.length)return25;
45-
// Using charCode (a = 97, b = 98, etc), we can map characters to buckets from 0 - 25
46-
constBASE_CHAR_CODE=97;
47-
/**
48-
* If each character has been organized, use first character to determine bucket,
49-
* otherwise iterate backwards through element
50-
*/
51-
constcharPos=index>element.length-1 ?0 :element.length-index-1;
52-
53-
returnelement.toLowerCase().charCodeAt(charPos)-BASE_CHAR_CODE;
54-
};
55-
56-
constbuckets=createBuckets(26);
57-
58-
array.forEach((element)=>{
59-
this.callbacks.visitingCallback(element);
60-
constcurrentBucket=getCharCodeOfElementAtIndex(element);
61-
buckets[currentBucket].push(element);
62-
});
63-
64-
returnbuckets;
65-
};
66-
6714
// Assumes all elements of array are of the same type
68-
constisArrayOfNumbers=isNumber(originalArray[0]);
69-
70-
/** Number of passes is determined by the length of the longest element in the array.
71-
* For integers, this log10(num), and for strings, this would be the lenght of the string.
72-
*/
73-
constdetermineNumPasses=()=>{
74-
constgetLengthOfLongestElement=()=>{
75-
if(isArrayOfNumbers){
76-
returnMath.floor(Math.log10(Math.max(...originalArray)))+1;
77-
}
78-
79-
returnoriginalArray.reduce((acc,val)=>{
80-
returnval.length>acc ?val.length :acc;
81-
},-Infinity);
82-
};
83-
84-
returngetLengthOfLongestElement(originalArray);
85-
};
15+
constisArrayOfNumbers=this.isArrayOfNumbers(originalArray);
8616

8717
letsortedArray=[...originalArray];
88-
constnumPasses=determineNumPasses();
18+
constnumPasses=this.determineNumPasses(sortedArray);
8919

9020
for(letcurrentIndex=0;currentIndex<numPasses;currentIndex+=1){
9121
constbuckets=isArrayOfNumbers ?
92-
placeElementsInNumberBuckets(sortedArray,currentIndex) :
93-
placeElementsInCharacterBuckets(sortedArray,currentIndex,numPasses);
22+
this.placeElementsInNumberBuckets(sortedArray,currentIndex) :
23+
this.placeElementsInCharacterBuckets(sortedArray,currentIndex,numPasses);
24+
9425
// Flatten buckets into sortedArray, and repeat at next index
9526
sortedArray=buckets.reduce((acc,val)=>{
9627
return[...acc, ...val];
@@ -99,4 +30,123 @@ export default class RadixSort extends Sort {
9930

10031
returnsortedArray;
10132
}
33+
34+
/**
35+
*@param {*[]} array
36+
*@param {number} index
37+
*@return {*[]}
38+
*/
39+
placeElementsInNumberBuckets(array,index){
40+
// See below. These are used to determine which digit to use for bucket allocation
41+
constmodded=10**(index+1);
42+
constdivided=10**index;
43+
constbuckets=this.createBuckets(NUMBER_OF_DIGITS);
44+
45+
array.forEach((element)=>{
46+
this.callbacks.visitingCallback(element);
47+
if(element<divided){
48+
buckets[0].push(element);
49+
}else{
50+
/**
51+
* Say we have element of 1,052 and are currently on index 1 (starting from 0). This means
52+
* we want to use '5' as the bucket. `modded` would be 10 ** (1 + 1), which
53+
* is 100. So we take 1,052 % 100 (52) and divide it by 10 (5.2) and floor it (5).
54+
*/
55+
constcurrentDigit=Math.floor((element%modded)/divided);
56+
buckets[currentDigit].push(element);
57+
}
58+
});
59+
60+
returnbuckets;
61+
}
62+
63+
/**
64+
*@param {*[]} array
65+
*@param {number} index
66+
*@param {number} numPasses
67+
*@return {*[]}
68+
*/
69+
placeElementsInCharacterBuckets(array,index,numPasses){
70+
constbuckets=this.createBuckets(ENGLISH_ALPHABET_LENGTH);
71+
72+
array.forEach((element)=>{
73+
this.callbacks.visitingCallback(element);
74+
constcurrentBucket=this.getCharCodeOfElementAtIndex(element,index,numPasses);
75+
buckets[currentBucket].push(element);
76+
});
77+
78+
returnbuckets;
79+
}
80+
81+
/**
82+
*@param {string} element
83+
*@param {number} index
84+
*@param {number} numPasses
85+
*@return {number}
86+
*/
87+
getCharCodeOfElementAtIndex(element,index,numPasses){
88+
// Place element in last bucket if not ready to organize
89+
if((numPasses-index)>element.length){
90+
returnENGLISH_ALPHABET_LENGTH-1;
91+
}
92+
93+
/**
94+
* If each character has been organized, use first character to determine bucket,
95+
* otherwise iterate backwards through element
96+
*/
97+
constcharPos=index>element.length-1 ?0 :element.length-index-1;
98+
99+
returnelement.toLowerCase().charCodeAt(charPos)-BASE_CHAR_CODE;
100+
}
101+
102+
/**
103+
* Number of passes is determined by the length of the longest element in the array.
104+
* For integers, this log10(num), and for strings, this would be the length of the string.
105+
*/
106+
determineNumPasses(array){
107+
returnthis.getLengthOfLongestElement(array);
108+
}
109+
110+
/**
111+
*@param {*[]} array
112+
*@return {number}
113+
*/
114+
getLengthOfLongestElement(array){
115+
if(this.isArrayOfNumbers(array)){
116+
returnMath.floor(Math.log10(Math.max(...array)))+1;
117+
}
118+
119+
returnarray.reduce((acc,val)=>{
120+
returnval.length>acc ?val.length :acc;
121+
},-Infinity);
122+
}
123+
124+
/**
125+
*@param {*[]} array
126+
*@return {boolean}
127+
*/
128+
isArrayOfNumbers(array){
129+
// Assumes all elements of array are of the same type
130+
returnthis.isNumber(array[0]);
131+
}
132+
133+
/**
134+
*@param {number} numBuckets
135+
*@return {*[]}
136+
*/
137+
createBuckets(numBuckets){
138+
/**
139+
* Mapping buckets to an array instead of filling them with
140+
* an array prevents each bucket from containing a reference to the same array
141+
*/
142+
returnnewArray(numBuckets).fill(null).map(()=>[]);
143+
}
144+
145+
/**
146+
*@param {*} element
147+
*@return {boolean}
148+
*/
149+
isNumber(element){
150+
returnNumber.isInteger(element);
151+
}
102152
}

‎src/algorithms/sorting/radix-sort/__test__/RadixSort.test.js

Lines changed: 3 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,5 @@
11
importRadixSortfrom'../RadixSort';
2-
import{
3-
stringArr,
4-
intArr,
5-
SortTester,
6-
}from'../../SortTester';
2+
import{SortTester}from'../../SortTester';
73

84
// Complexity constants.
95
constARRAY_OF_STRINGS_VISIT_COUNT=24;
@@ -16,15 +12,15 @@ describe('RadixSort', () => {
1612
it('should visit array of strings n (number of strings) x m (length of longest element) times',()=>{
1713
SortTester.testAlgorithmTimeComplexity(
1814
RadixSort,
19-
stringArr,
15+
['zzz','bb','a','rr','rrb','rrba'],
2016
ARRAY_OF_STRINGS_VISIT_COUNT,
2117
);
2218
});
2319

2420
it('should visit array of integers n (number of elements) x m (length of longest integer) times',()=>{
2521
SortTester.testAlgorithmTimeComplexity(
2622
RadixSort,
27-
intArr,
23+
[3,1,75,32,884,523,4343456,232,123,656,343],
2824
ARRAY_OF_INTEGERS_VISIT_COUNT,
2925
);
3026
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp