{"id":207784,"date":"2013-12-29T23:25:03","date_gmt":"2013-12-29T19:25:03","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=207784"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=207784","title":{"rendered":"Merge sort \u0438 AS3. \u041e\u0431\u0433\u043e\u043d\u044f\u0435\u043c \u0440\u043e\u0434\u043d\u043e\u0439 Vector.sort(Array.NUMERIC)<\/span>"},"content":{"rendered":"
\t\t\t
\u0421\u043b\u0435\u0432\u0430 \u2014 mergeSort, \u0441\u043f\u0440\u0430\u0432\u0430 \u2014 \u0440\u043e\u0434\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430. PepperFlash \u0438 75 \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<\/a><\/p>\n

\u0427\u0442\u043e \u0431\u044b \u043f\u043e\u043d\u044f\u0442\u044c \u044d\u0442\u0443 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443, \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u043d\u044f\u0442\u044c \u0442\u0440\u0438 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0430:<\/p>\n

    \n
  • \u0421\u043b\u0438\u0432\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u044b.<\/li>\n
  • \u041c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u043c.<\/li>\n
  • \u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u2014 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/li>\n<\/ul>\n

    \u041f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0432\u044b\u0440\u0435\u0437\u0430\u0435\u0442 \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0438\u0439 \u0438\u0437 \u043f\u0435\u0440\u0432\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0434\u0432\u0443\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u0438 \u0432\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0432 \u043a\u043e\u043d\u0435\u0446 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043f\u043e\u043a\u0430 \u043e\u0434\u0438\u043d \u0438\u0437 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043d\u0435 \u0441\u0442\u0430\u043d\u0435\u0442 \u043f\u0443\u0441\u0442\u044b\u043c. \u041f\u043e\u0441\u043b\u0435 \u044d\u0442\u043e\u0433\u043e \u043e\u0441\u0442\u0430\u0442\u043a\u0438 \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u043e\u043f\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0432 \u043a\u043e\u043d\u0435\u0446 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0438\u0440\u0443\u044e\u0449\u0435\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430.

    \u0427\u0442\u043e \u0431\u044b \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0445\u043e\u0440\u043e\u0448\u043e \u043f\u043e\u043d\u044f\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u2014 \u043d\u0430\u0434\u043e \u0435\u0433\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c.
    \u0423 \u043c\u0435\u043d\u044f \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u043e\u0441\u044c \u0442\u0430\u043a: <\/p>\n

    function mergeSort(array:Array):Array { \tvar chunkSize:int = array.length \/ 2; \tif(chunkSize >= 1){ \t\tvar left:Array = mergeSort(array.slice(0, chunkSize)); \t\tvar right:Array = mergeSort(array.slice(chunkSize)); \t\t \t\tvar result:Array = []; \t\twhile(left.length && right.length){ \t\t\tif(left[0] < right[0]){ \t\t\t\tresult.push(left.shift()); \t\t\t} else{ \t\t\t\tresult.push(right.shift()); \t\t\t} \t\t} \t\treturn result.concat(left, right); \t} \treturn array; }<\/code><\/pre>\n
    \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0434\u0430\u0436\u0435 \u0442\u0430\u043a\u0430\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445, \u043d\u0430\u0439\u0434\u0435\u043d\u043d\u044b\u0445 \u043c\u043d\u043e\u044e \u0432\u043e \u0432\u0441\u044f\u043a\u0438\u0445 \u0431\u043b\u043e\u0433\u0430\u0445.<\/p>\n
      \u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e, \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442\u0441\u044f \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u043f\u0435\u0440\u0432\u044b\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b. \u0422\u043e \u0435\u0441\u0442\u044c 0 \u0438 1, \u043f\u043e\u0442\u043e\u043c 2 \u0438 3, \u043f\u043e\u0442\u043e\u043c 0..1 \u0438 2..3 \u0441\u043b\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u0432 \u043e\u0434\u0438\u043d \u043c\u0430\u0441\u0441\u0438\u0432 0..3, \u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0441\u043b\u0435 4 \u0438 5.
      (\u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u0434 \u043e\u0442\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0435\u0439 \u0441\u043a\u043e\u0431\u043a\u043e\u0439 \u2014 \u043f\u0440\u0438\u043e\u0440\u0438\u0442\u0435\u0442)  <\/p>\n
    6{     _3_[         1(1, 2),         2(3, 4)     ],     5[         _4_(5, 6)     ] }<\/pre>\n
    \u041d\u043e \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u0438 \u043f\u043e\u0442\u043e\u043c \u0438\u0445 \u0441\u043b\u0438\u0432\u0430\u0442\u044c \u0432 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u044b \u0438\u0437 4 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.  <\/p>\n
    6{     _4_[         1(1, 2),         2(3, 4)     ],     5[         _3_(5, 6)     ] }<\/pre>\n
      \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u0437\u0431\u0430\u0432\u0438\u0442\u0441\u044f \u043e\u0442 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0438.<\/p>\n
      \u041f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u0441 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c. \u041d\u0435\u0442 \u043d\u0443\u0436\u0434\u044b \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u0435\u0439 \u043c\u0430\u0441\u0441\u0438\u0432\u044b, \u043a\u043e\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0438 \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u0441\u043b\u0438\u0432\u0430\u0435\u043c\u044b\u0445 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432. \u041d\u043e \u043e\u043d\u0430 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0441\u0440\u0430\u0437\u0443 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432(\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043c\u0435\u043d\u044c\u0448\u0435 \u0432\u0441\u0435\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043f\u0435\u0440\u0432\u043e\u0433\u043e, \u0442\u043e \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u043f\u043e\u043f\u043e\u0440\u0442\u0438\u0442 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432), \u0435\u0439 \u043d\u0443\u0436\u0435\u043d \u0442.\u043d. \u0431\u0443\u0444\u0435\u0440, \u0447\u0442\u043e \u0431\u044b \u0437\u0430\u043f\u043e\u043c\u043d\u0438\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f, \u043d\u0435 \u0438\u0441\u043f\u043e\u0440\u0442\u0438\u0432 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0432\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u041f\u043e \u043e\u043a\u043e\u043d\u0447\u0430\u043d\u0438\u044e \u0441\u0432\u043e\u0435\u0439 \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0430 \u043a\u043e\u043f\u0438\u0440\u0443\u0435\u0442 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0438\u0437 \u0431\u0443\u0444\u0435\u0440\u0430 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n
      \u0422.\u043a. \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0440\u0430\u0432\u0435\u043d \u0441\u0443\u043c\u043c\u0435 \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u0432 \u0434\u0432\u0443\u0445 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432, \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0431\u0443\u0444\u0435\u0440, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u043e\u0434\u0438\u043d \u0431\u0443\u0444\u0435\u0440, \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0441 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432, \u0438 \u043d\u0435 \u043a\u043e\u043f\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u0430\u0436\u0434\u044b\u0439 \u0440\u0430\u0437 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0441\u043b\u0438\u044f\u043d\u0438\u044f \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432.<\/p>\n
      \u041a\u043e\u0440\u043e\u0447\u0435, \u0440\u0438\u0441\u0443\u0435\u043c \u0441\u043e\u0432\u0443:  <\/p>\n
    \u041a\u043e\u0434<\/b><\/p>\n
    \n
    function mergeSort(array:Vector.<int>):Vector.<int> { \tvar length:uint = array.length; \tvar buffer:Vector.<int> = new Vector.<int>(length, true); \tfor (var leftChunkSize:uint = 1; leftChunkSize < length; leftChunkSize *= 2) { \/\/ low \t\tvar bufferPointer:uint = 0; \t\tvar leftChunkStart:uint = 0; \t\tfor (; leftChunkStart < length; leftChunkStart += leftChunkSize * 2) { \/\/ mid \t\t\tvar rightChunkStart:uint = Math.min(leftChunkStart + leftChunkSize, length); \t\t\tvar rightChunkEnd:uint = Math.min(rightChunkStart + leftChunkSize, length); \t\t\t \t\t\tvar leftChunkEnd:uint = rightChunkStart; \t\t\t \t\t\tvar leftPointer:uint = leftChunkStart; \t\t\tvar rightPointer:uint = rightChunkStart; \t\t\t \t\t\twhile (leftPointer < leftChunkEnd && rightPointer < rightChunkEnd) { \/\/ hard \t\t\t\tif (array[leftPointer] < array[rightPointer]) { \t\t\t\t\tbuffer[bufferPointer++] = array[leftPointer++]; \t\t\t\t}else { \t\t\t\t\tbuffer[bufferPointer++] = array[rightPointer++]; \t\t\t\t} \t\t\t} \t\t\twhile (leftPointer < leftChunkEnd) { \/\/ hard \t\t\t\tbuffer[bufferPointer++] = array[leftPointer++]; \t\t\t} \t\t\twhile (rightPointer < rightChunkEnd) { \/\/ hard \t\t\t\tbuffer[bufferPointer++] = array[rightPointer++]; \t\t\t} \t\t} \t\t \t\tvar temp:Vector.<int> = array; \t\tarray = buffer; \t\tbuffer = temp; \t} \t \tif (result !== array) { \t\tfor (var i:uint = 0; i < length; i++ ) { \t\t\tresult[i] = array[i]; \t\t} \t} \treturn result; }<\/code><\/pre>\n
    \u0412 \u043a\u043e\u043c\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u044f\u0445 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u044b \u0443\u0437\u043a\u0438\u0435 \u043c\u0435\u0441\u0442\u0430.<\/p><\/div>\n<\/div>\n
      \u041a\u043e\u043d\u0444\u0438\u0433\u0443\u0440\u0430\u0446\u0438\u044f \u041f\u041a: DDR3-1066 2GB, P6200 (2×2.13GHz).
      (\u00abFP\u00bb \u0447\u0438\u0442\u0430\u0442\u044c \u043a\u0430\u043a \u00abFlashPlayerDebugger 11.9.900.170\u00bb, release)  <\/p>\n
    \u0421\u043a\u043e\u0440\u043e\u0441\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u044b<\/b><\/p>\n
    \n\n\n\n\n\n\n\n\n\n\n\n
    <\/td>\nFP<\/td>\nPepperFlash<\/td>\n<\/tr>\n
    200 000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/b><\/td>\n<\/tr>\n
    mergeSort<\/td>\n160\u043c\u0441<\/td>\n81\u043c\u0441<\/td>\n<\/tr>\n
    \u0420\u043e\u0434\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/td>\n81\u043c\u0441<\/td>\n90\u043c\u0441<\/td>\n<\/tr>\n
    2 000 000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/b><\/td>\n<\/tr>\n
    mergeSort<\/td>\n1800\u043c\u0441<\/td>\n921\u043c\u0441<\/td>\n<\/tr>\n
    \u0420\u043e\u0434\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/td>\n1378\u043c\u0441<\/td>\n1425\u043c\u0441<\/td>\n<\/tr>\n
    20 000 000 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432<\/b><\/td>\n<\/tr>\n
    mergeSort<\/td>\n21374\u043c\u0441<\/td>\n10267\u043c\u0441<\/td>\n<\/tr>\n
    \u0420\u043e\u0434\u043d\u0430\u044f \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430<\/td>\n20404\u043c\u0441<\/td>\n21175\u043c\u0441<\/td>\n<\/tr>\n<\/table>\n
      <\/div>\n<\/div>\n
      \u0422\u0435\u043f\u0435\u0440\u044c \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0443\u0437\u043a\u0438\u0435 \u043c\u0435\u0441\u0442\u0430:  <\/p>\n