ماهي خوارزمية Radix Sort ؟
هي خورزميه يرجع عمرها الى 1887 عمل العالم : Herman Hollerith لاتعتمد على مقارنه القيم بل ترتب الارقام بالاعتماد على
مفاتيح للارقام الصحيحه من 0 الى 9 بالاعتماد على القيمه القصوى للرقم Least Significant Digit (LSD) او Most Significant Digit (MSD) وهي تعتبر من اسرع الخوارزمات الموجوده .
مقارنة السرعه بين الخوارزميات :
http://bigocheatsheet.comمعلومات اكثر :
https://en.wikipedia.org/wi...الخوارزميه تم تنفيذها في لغة javascript .
الخوارزمية :
(function(){
// mv - the maximum possible position of number in the array
// ua - unsorted array
function RadixSort(mv,ua){
// part of the algorithm to get the position of the
var n = 1;
// a 0 to 9 linked list queues FIFO
var ll = Array(10);
for(var i = 0; i < ll.length; i++ ){
ll[i] = [];
}
// keep multiplying m and n until we sort the array!
for( var m=10; m < mv; m *= 10, n *= 10 ){
// push the number in array to our queue
for( var i = 0; i < ua.length; i++ ){
ll[ Math.floor( (ua[i] % m) / n) ].push( ua[i] );
}
// replace the arry with new values
var uai=0;
for(var i=0;i<ll.length;i++){
var cl = ll[i];
while(cl.length>0){
var v = cl.shift();
ua[uai] = v;
uai++;
}
}
}
// return the new sorted array
return ua;
}
//create Random Array
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
var ary=[];
var max = 10000;
var len = 700000;
for(var i = 0 ;i<len;i++){
ary.push(getRandomInt(10,max));
}
//Test Radix Sort
var start = new Date().getTime();
RadixSort(max*10,ary);
var end = new Date().getTime();
var time = end - start;
console.log('Radix Sort Time : ');
console.log('Array Length = '+ary.length+',Execution time: ' + time);
//Test Default Javascript Native Sort
var ary2=[];
for(var i = 0 ;i<len;i++){
ary2.push(getRandomInt(10,max));
}
var start = new Date().getTime();
RadixSort(max*10,ary);
var end = new Date().getTime();
var time = end - start;
ary.sort();
console.log('Default Javascript Sort Time: ');
console.log('Array Length = '+ary.length+',Execution time: ' + time);
})();
Github :
يمكنك مشاهده كيفيه عمل الخوارزميه من هنا :
https://www.cs.usfca.edu/~g...
التعليقات