정리하지 않은 상태로 구성되었습니다.
시간이 나면 정리할 예정입니다.
일반적으로 많이 사용하는 sort( function (a,b) { return a-b; } ) 와 quick 정렬의 실행속도를
비교해 보았습니다.
아래는 코드 입니다.
function swapArrayPosition(orgArray,stdIdx,targetIdx) {
if ( !orgArray ) {
return;
}
if ( stdIdx == targetIdx ) {
return;
}
var len = orgArray.length;
if ( stdIdx < 0 || stdIdx >= len ) {
return;
}
if ( targetIdx < 0 || targetIdx >= len ) {
return;
}
var tmp = orgArray[stdIdx];
orgArray[stdIdx] = orgArray[targetIdx];
orgArray[targetIdx] = tmp;
}
function getQuickSortStdIndex(orgArray,stIdx,edIdx) {
if ( edIdx - stIdx < 2 ) {
return stIdx;
}
var midIdx = parseInt((edIdx+stIdx)/2);
var fV = orgArray[stIdx];
var mV = orgArray[midIdx];
var lV = orgArray[edIdx];
if ( fV >= mV && fV >= lV ) {
if ( mV >= lV ) {
return edIdx;
} else {
return midIdx;
}
} else if ( lV >= fV && lV >= mV ) {
if ( mV >= fV ) {
return stIdx;
} else {
return midIdx;
}
} else {
if ( fV >= lV ) {
return edIdx;
} else {
return stIdx;
}
}
}
function executeQuickSortPartition(orgArray,stIdx,edIdx,stdIdx) {
var stdValue = orgArray[stdIdx];
var reStartIdx = stIdx;
swapArrayPosition(orgArray,stdIdx,edIdx);
for ( var i = stIdx; i < edIdx; i++ ) {
if ( orgArray[i] <= stdValue ) {
swapArrayPosition(orgArray,i,reStartIdx);
reStartIdx++;
}
}
swapArrayPosition(orgArray,edIdx,reStartIdx);
return reStartIdx;
}
function executeQuickSortRecursive(orgArray,stIdx,edIdx) {
if ( edIdx > stIdx ) {
var stdIdx = getQuickSortStdIndex(orgArray,stIdx,edIdx);
var sortedIdx = executeQuickSortPartition(orgArray,stIdx,edIdx,stdIdx);
executeQuickSortRecursive(orgArray,stIdx,sortedIdx-1);
executeQuickSortRecursive(orgArray,sortedIdx+1,edIdx);
}
}
function executeQuickSort(orgArray) {
if ( !orgArray || !orgArray.length ) {
return;
}
var len = orgArray.length;
executeQuickSortRecursive(orgArray,0,len-1);
}
window.onload = function() {
var orgArray = [];
var orgArrayTest = [];
for ( var i = 0; i < 10000000; i++ ) {
orgArray.push(parseInt(Math.random()*1000000000));
orgArrayTest.push(orgArray[i]);
}
document.writeln("<P>");
document.writeln ( orgArray[0] + " : " + orgArray[orgArray.length-1] );
document.writeln("</P>");
var stTimeMillis = (new Date())-1;
orgArray.sort(function(a,b) { return a - b; });
var edTimeMillis = (new Date())-1;
document.writeln("<P>");
document.writeln ( orgArray[0] + " : " + orgArray[orgArray.length-1] );
document.writeln("<P>");
document.writeln("<P>");
document.writeln ( "Browser spending times : " + (edTimeMillis-stTimeMillis) );
document.writeln("<P>");
stTimeMillis = (new Date())-1;
executeQuickSort(orgArrayTest);
edTimeMillis = (new Date())-1;
document.writeln("<P>");
document.writeln ( orgArrayTest[0] + " : " + orgArrayTest[orgArray.length-1] );
document.writeln("<P>");
document.writeln("<P>");
document.writeln ( "Quicksort spending times : " + (edTimeMillis-stTimeMillis) );
document.writeln("<P>");
}
그 실행결과는 다음과 같습니다.
IE10
555502868 : 166089945
172 : 999999749
Browser spending times : 3272
172 : 999999749
Quicksort spending times : 2551
Chrome 버전 30.0.1599.101 m
532093033 : 69739888
140 : 999999930
Browser spending times : 3103
140 : 999999930
Quicksort spending times : 1328
IE10 과 Chrome 의 내부 sort 연산은 크게 차이가 나지 않았습니다. (물론 반복회수가
많아지면 더 차이가 들어날것 같습니다만....)
사용자가 만든 함수의 성능은 지금의 결과로도 2배가량 차이가 나타나고 있습니다.
172 : 999999749
Browser spending times : 3272
172 : 999999749
Quicksort spending times : 2551
Chrome 버전 30.0.1599.101 m
532093033 : 69739888
140 : 999999930
Browser spending times : 3103
140 : 999999930
Quicksort spending times : 1328
IE10 과 Chrome 의 내부 sort 연산은 크게 차이가 나지 않았습니다. (물론 반복회수가
많아지면 더 차이가 들어날것 같습니다만....)
사용자가 만든 함수의 성능은 지금의 결과로도 2배가량 차이가 나타나고 있습니다.
