Միաձուլման տեսակավորման ալգորիթմը

#տեսակավորում-ալգորիթմներ շարքի մասին

#sorting-algorithms series-ը հրապարակումների հավաքածու է JavaScript-ում վերաիրականացված տեսակավորման ալգորիթմների մասին:

Եթե ​​դուք ծանոթ չեք տեսակավորման ալգորիթմներին, արագ ներածությունը և վերաիրականացված տեսակավորման ալգորիթմների ամբողջական ցանկը կարող եք գտնել JavaScript-ում տեսակավորման ալգորիթմների շարքի ներածական գրառման մեջ:

Եթե ​​դուք հարմարավետ եք զգում յուրաքանչյուր տեսակավորման ալգորիթմի հայեցակարգը և ցանկանում եք տեսնել միայն կոդը, դիտեք շարքի ամփոփիչ գրառումը: Այն հեռացնում է բոլոր բացատրությունները և պարունակում է միայն JavaScript կոդը բոլոր տեսակավորման ալգորիթմների համար, որը քննարկվել է շարքում:

Ստացեք կոդը Github-ում

Իհարկե, ամբողջ կոդը կարելի է գտնել նաև Github-ում sorting-algorithms-in-javascript-ի պահեստում:

Նրանց բոլորին համեմատելու լավ միջոց

Ի տարբերություն տվյալների կառուցվածքների, բոլոր տեսակավորման ալգորիթմներն ունեն նույն նպատակը, և նրանք բոլորը կարող են վերցնել նույն մուտքային տվյալները: Այսպիսով, շարքի յուրաքանչյուր տեսակավորման ալգորիթմի համար մենք դասավորում ենք 10 թվերից բաղկացած զանգված 1-ից մինչև 10:

Դրանով մենք կկարողանանք ավելի հեշտությամբ համեմատել տարբեր տեսակավորման ալգորիթմները: Տեսակավորման ալգորիթմները շատ զգայուն են մուտքային տվյալների նկատմամբ, ուստի մենք կփորձենք նաև տարբեր մուտքային տվյալներ՝ տեսնելու, թե ինչպես են դրանք ազդում կատարողականի վրա:

Սահմանում

Միաձուլման տեսակավորումը բաժանիր և տիրիր ալգորիթմ է: Հայեցակարգային առումով, Միաձուլման տեսակավորումն աշխատում է հետևյալ կերպ. 1) չտեսակավորված ցուցակը բաժանել n ենթացանկերի, որոնցից յուրաքանչյուրը պարունակում է 1 տարր (1 տարրի ցանկը համարվում է տեսակավորված), 2) Բազմիցս միաձուլել ենթացանկերը՝ նոր տեսակավորված ենթացանկեր ստեղծելու համար, մինչև լինի միայն 1 ենթացանկ: մնացածը։ Սա կլինի տեսակավորված ցուցակը: Վիքիպեդիայից

Վիզուալիզացիա

Եթե ​​ցանկանում եք ունենալ ալգորիթմի գեղեցիկ պատկերացում, visualgo.net կայքը լավ ռեսուրս է: Դուք կարող եք խաղալ բազմաթիվ պարամետրերով և տեսնել, թե ալգորիթմի որ մասն ինչ է անում:

Բարդություն

Ժամանակի բարդություն

Լավագույն =› O(n log(n)), Միջին =› O(n log(n)), Վատագույն =› O(n log(n))

Merge տեսակավորման ալգորիթմի ժամանակի և տարածության բարդության ամբողջական ակնարկ ստանալու համար դիտեք այս հիանալի Big O cheat sheet-ը:

Կոդը

Յուրաքանչյուր տեսակավորման ալգորիթմի համար մենք պատրաստվում ենք դիտարկել կոդի 2 տարբերակ։ Առաջինը վերջնական/մաքուր տարբերակն է, որը պետք է հիշել։ Երկրորդն իրականացնում է որոշ հաշվիչներ, որպեսզի ցույց տա ժամանակային տարբեր բարդությունները՝ կախված մուտքերից:

Մաքուր տարբերակ

// array to sort
var array = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];

// top-down implementation
function mergeSortTopDown(array) {
  if(array.length < 2) {
    return array;
  }

  var middle = Math.floor(array.length / 2);
  var left = array.slice(0, middle);
  var right = array.slice(middle);

  return mergeTopDown(mergeSortTopDown(left), mergeSortTopDown(right));
}
function mergeTopDown(left, right) {
  var array = [];

  while(left.length && right.length) {
    if(left[0] < right[0]) {
      array.push(left.shift());
    } else {
      array.push(right.shift());
    }
  }
  return array.concat(left.slice()).concat(right.slice());
}

console.log(mergeSortTopDown(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

// bottom-up implementation
function mergeSortBottomUp(array) {
  var step = 1;
  while (step < array.length) {
    var left = 0;
    while (left + step < array.length) {
      mergeBottomUp(array, left, step);
      left += step * 2;
    }
    step *= 2;
  }
  return array;
}
function mergeBottomUp(array, left, step) {
  var right = left + step;
  var end = Math.min(left + step * 2 - 1, array.length - 1);
  var leftMoving = left;
  var rightMoving = right;
  var temp = [];

  for (var i = left; i <= end; i++) {
    if ((array[leftMoving] <= array[rightMoving] || rightMoving > end) &&
        leftMoving < right) {
      temp[i] = array[leftMoving];
      leftMoving++;
    } else {
      temp[i] = array[rightMoving];
      rightMoving++;
    }
  }

  for (var j = left; j <= end; j++) {
    array[j] = temp[j];
  }
}

console.log(mergeSortBottomUp(array.slice())); // => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Տարբերակ հաշվիչներով

// sample of arrays to sort
var arrayRandom = [9, 2, 5, 6, 4, 3, 7, 10, 1, 8];
var arrayOrdered = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var arrayReversed = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];

var countOuter = 0;
var countInner = 0;
var countSwap = 0;

function resetCounters() {
  countOuter = 0;
  countInner = 0;
  countSwap = 0;
}

// top-down implementation
function mergeSortTopDown(array) {
  countOuter++;
  if(array.length < 2) {
    return array;
  }

  var middle = Math.floor(array.length / 2);
  var left = array.slice(0, middle);
  var right = array.slice(middle);

  return mergeTopDown(mergeSortTopDown(left), mergeSortTopDown(right));
}

function mergeTopDown(left, right) {
  var array = [];

  while(left.length && right.length) {
    countInner++;
    if(left[0] < right[0]) {
      array.push(left.shift());
    } else {
      array.push(right.shift());
    }
  }
  return array.concat(left.slice()).concat(right.slice());
}

mergeSortTopDown(arrayRandom.slice()); // => outer: 19 inner: 24 swap: 0
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

mergeSortTopDown(arrayOrdered.slice()); // => outer: 19 inner: 15 swap: 0
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

mergeSortTopDown(arrayReversed.slice()); // => outer: 19 inner: 19 swap: 0
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

// bottom-up implementation
function mergeSortBottomUp(array) {
  var step = 1;
  while (step < array.length) {
    countOuter++;
    var left = 0;
    while (left + step < array.length) {
      countInner++;
      mergeBottomUp(array, left, step);
      left += step * 2;
    }
    step *= 2;
  }
  return array;
}
function mergeBottomUp(array, left, step) {
  var right = left + step;
  var end = Math.min(left + step * 2 - 1, array.length - 1);
  var leftMoving = left;
  var rightMoving = right;
  var temp = [];

  for (var i = left; i <= end; i++) {
    if ((array[leftMoving] <= array[rightMoving] || rightMoving > end) &&
        leftMoving < right) {
      temp[i] = array[leftMoving];
      leftMoving++;
    } else {
      temp[i] = array[rightMoving];
      rightMoving++;
    }
  }

  for (var j = left; j <= end; j++) {
    countSwap++;
    array[j] = temp[j];
  }
}

mergeSortBottomUp(arrayRandom.slice()); // => outer: 4 inner: 9 swap: 36
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

mergeSortBottomUp(arrayOrdered.slice()); // => outer: 4 inner: 9 swap: 36
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

mergeSortBottomUp(arrayReversed.slice()); // => outer: 4 inner: 9 swap: 36
console.log('outer:', countOuter, 'inner:', countInner, 'swap:', countSwap);
resetCounters();

Սկզբնապես հրապարակվել է blog.benoitvallon.com-ում: