Merge sort and quick sort concise implementation and comparison

preface

Merge sort and quicksort are two kinds of sorting algorithms which have practical application. They have some common characteristics and the overall idea is also relatively similar. This article will start from some simpler sorting algorithms, transition to merge sort and quick sort implementation, and to them do some simple contrast thinking and summary. Before we do that, let’s talk a little bit about sorting algorithms.

Sorting algorithm is to arrange a string of data according to a specific sorting method, they have a lot of research and applications in computer science.

Imagine the following scenario:

Search for a contact from your address book
Looking for a file in a pile of files
When you arrive at the cinema, look for the seat assigned on the ticket

How do you find the specific “data” you want if the “data” — contacts, files, theater seats — is not organized in the order you want? It would be very troublesome! Therefore, for the need to search the data, often should be sorted first!

Warm-up 1: Select sort

The examples in this article are numerical sorting, and the easiest and most intuitive way to solve this problem is to find the smallest, then the second smallest, then the third smallest… So that’s the idea of selection sort.

function selectionSort(array) {
  const len = array.length;

  for (let i = 0; i < len - 1; i++) {
    let min = i;

    for (let j = i + 1; j < len; j++) {
      if (array[min] > array[j]) {
        min = j;
      }
    }

    [ array[min], array[i] ] = [ array[i], array[min] ];
  }

  return array;
}
Copy the code

Implementation resolution:

Through the array
Find the smallest element in the current range and record its subscript with minIndex. The first traversal is the entire array
Swap the value of the element subscript minIndex with the element with the current lowest subscript. The element with the lowest subscript in the first traversal is a[0].
For the second traversal, the range starts at the subscript of the second data element, so the current minimum subscript element is a[1].
Repeat the swap until the traversal ends

With a piece of auxiliary code, do some demonstration examples.

function createUnsortedArray(size) {
  const array = [];

  for (let i = size; i > 0; i--) {
    const num = (i / 10 > 1)? i :10;
    array.push( Math.round(Math.random(i) * num + Math.round(Math.random(i)) * Math.random(i) * num * 10)); }return array;
}

function show(fn, size = 11) {
  console.log('-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --');
  console.log(`Method: ${fn.name}`);
  console.log('-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --');
  const array = createUnsortedArray(size);
  console.log('before:');
  console.log(array.toString());
  console.log('after:');
  console.log(fn(array).toString());
}
Copy the code

Create a randomly generated, unsorted array, and then print the result.

show(selectionSort);

// ------------------------------------------
// Method: selectionSort
// ------------------------------------------
// before:
/ / 9,22,3,27,74,54,8,41,80,74,3
// after:
/ / 3,3,8,9,22,27,41,54,74,74,80
Copy the code

Warm-up two: Bubble sort

Bubble sort is similar to selection sort, except that bubble sort bubbles the maximum to the last position first. Bubbling sequencing was studied as early as 1956.

function bubbleSort(array) {
  for (let first = 0, len = array.length; first < len; first++) {
    let isSorted = true;

    for (let second = 0; second < len - first - 1; second++) {
      if (array[second] > array[second + 1]) {
        let temp = array[second];
        array[second] = array[second + 1]
        array[second + 1] = temp;
        isSorted = false; }}if (isSorted) {
      break; }}return array;
}

show(bubbleSort);

// ------------------------------------------                                      
// Method: bubbleSort                                                              
// ------------------------------------------                                      
// before:
/ / 35,8,2,2,8,1,3,4,2,10,4
// after:
/ / 1,2,2,2,3,4,4,8,8,10,35
Copy the code

Implementation resolution:

Through the array
Do the second layer of traversal, compare the two adjacent terms from front to back, the value of the former term is greater than the latter term, then swap (bubble). Bubble the first time, bubble the largest element value to the end
Because each bubble determines a current maximum value and places it at the end of the current range, each bubble has one less position to check
A variable can be used to record whether the current bubbling has resulted in an element swap. If not, the current sorting is complete and the loop is terminated

Warm-up three: Insert sort

The idea of insertion sort is actually very common in daily life, for example, how to arrange lu Junyi’s seat? Comprehensive background, ability, the status of rivers and lakes, the situation of the people and other indicators, he ranked second in Liangshan Po, status only second to Song Jiang. So that’s the idea of insertion sort. The insertion sort is superior to the other sorting methods mentioned in this article in the case of a small amount of data, or adding a data item to the sorted data, such as “rank Lu Junyi”.

function insertionSort(array) {
  for (let i = 0, len = array.length; i < len; i++) {
    let j = i;
    const temp = array[i]

    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1];
      j--;
    }

    array[j] = temp;
  }

  return array;
}

show(insertionSort);

// ------------------------------------------                                      
// Method: insertionSort                                                              
// ------------------------------------------                                      
// before:
/ / 3,8,68,30,28,56,35,30,2,4,13
// after:
/ / 2,3,4,8,13,28,30,30,35,56,68
Copy the code

Implementation resolution:

Start with the first element, which can be considered sorted
Takes the next element and scans back to front in the sorted element sequence
If the element (sorted) is larger than the new element, move the element to the next position
Repeat step 3 until you find a place where the sorted element is less than or equal to the new element
After inserting the new element into the location
Repeat steps 2 to 5

Merge sort (recursive implementation)

The time complexity of selection sort and bubble sort is O(n^2), which are seldom used in practical engineering. The time complexity of merge sort is O(nlog(n)), which is an optional sorting scheme in practical engineering.

function mergeSort(unsorted) {
  function merge(leftArr, rightArr) {
    const lenL = leftArr.length;
    const lenR = rightArr.length;
    let indexL = 0;
    let indexR = 0;
    const result = [];

    while (indexL < lenL && indexR < lenR) {
      if (leftArr[indexL] < rightArr[indexR]) {
        result.push(leftArr[indexL++]);
      } else{ result.push(rightArr[indexR++]); }}while (indexL < lenL) {
      result.push(leftArr[indexL++]);
    }

    while (indexR < lenR) {
      result.push(rightArr[indexR++]);
    }

    return result;
  }

  function split(array) {
    const len = array.length;

    if (len <= 1) {
      return array;
    }

    const mid = Math.floor(len / 2);

    const leftArr = array.slice(0, mid);
    const rightArr = array.slice(mid, len);

    return merge( split(leftArr), split(rightArr) );
  }

  return split(unsorted);
}

show(mergeSort);

// ------------------------------------------
// Method: mergeSort
// ------------------------------------------
// before:
/ / 86,55,0,31,104,6,5,49,89,19,6
// after:
/ / 0,5,6,6,19,31,49,55,86,89,104
Copy the code

Implementation analysis:

Splits an array into two arrays
Once the shard is minimized, the merge operation, which merges two sorted arrays, begins
Recursive merge, since it is a small to large merge, so the two arrays to be merged are always sorted, always do the same merge operation

Quicksort (recursive implementation)

Quicksort is a sorting algorithm that has a lot of practical applications, and it is usually faster than other O(nlog(n)) time complexity algorithms.

function quickSort(unsorted) {
  function partition(array, left, right) {
    const pivot = array[ Math.floor((left + right) / 2)];while (left <= right) {
      while (array[left] < pivot) {
        left++;
      }

      while (array[right] > pivot) {
        right--;
      }

      if(left <= right) { [array[left], array[right]] = [array[right], array[left]]; left++; right--; }}return left;
  }

  function quick(array, left, right) {
    if (array.length <= 1) {
      return array;
    }

    const index = partition(array, left, right);

    if (left < index - 1) {
      quick(array, left, index - 1);
    }

    if (right > index) {
      quick(array, index, right);
    }

    return array;
  }

  return quick(unsorted, 0, unsorted.length - 1);
}

show(quickSort);

// ------------------------------------------
// Method: quickSort
// ------------------------------------------
// before:
/ / 41,9,22,4,1,32,10,28,4,94,3
// after:
/ / 1,3,4,4,9,10,22,28,32,41,94
Copy the code

Implementation analysis:

Partition the current array
To partition, select a reference value and create two Pointers, one on the left pointing to the first item and one on the right pointing to the last item. Move the left pointer until it finds an element larger than the reference value, then move the right pointer until it finds an element smaller than the reference value, then swap them, and repeat the process until the left pointer exceeds the right. The operation of partition and swap such that all elements smaller than the reference value are in front of the reference value and all elements larger than the reference value are behind the reference value.
Repeat partition and swap operations for the two regions after the last partition until the partition reaches the minimum.

Compare merge sort with quicksort

They all use the idea of divide and conquer. Compared with select sort and bubble sort, merge sort and quicksort use shard rather than direct traversal, which effectively reduces the number of swaps.
Merge sort is shard first, then sort, the process can be described as: shard, shard, shard… Sort, sort, sort…
Quicksort is an alternating process of partition and sort. The process can be described as: Partition, sort, partition, sort…
The “sort” mentioned in the previous two items is not the same operation in merge sort and quicksort, where the operation is to merge two arrays into one (merge operation), while the operation in quicksort is to swap.

The resources

Learning JavaScript Data Structures and Algorithms (Version 2)
Sorting algorithm

Merge sort and quick sort concise implementation and comparison

preface

Warm-up 1: Select sort

Warm-up two: Bubble sort

Warm-up three: Insert sort

Merge sort (recursive implementation)

Quicksort (recursive implementation)

Compare merge sort with quicksort

The resources

Related Posts

Create front-end data model, vUE development must

Angular 2.x :(5) implement a custom pipe

WebGL Lesson 32: Simple 2D lighting