Common Sorting Algorithms And Analysis

開発

2020/12/4

Common Sorting Algorithms And Analysis

ZHUOTAO LIAN

この記事は1年以上前に書かれたもので、内容が古い可能性がありますのでご注意ください。

In this article, I will introduce five common sorting algorithms namely bubble sort, insertion sort, selection sort, merge sort and quick sort discribed by JavaScript, and analyze the performance and differences between them.

1. Bubble Sort

function bubbleSort(arr){

varlength = arr.length;

for (vari = 0; i < length; i++){

for(varj = 0; j < length-1-i; j++){

if(arr[j+1] > arr[j]){

vartemp = arr[j];

arr[j] = arr[j+1];

arr[j+1] = temp;

}

}

}

return arr;

}

Analysis:

Stable: Yes
Worst and Average Case Time Complexity: O(n²)
Auxiliary Space: O(1)

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

2. Selection Sort

function selectionSort(arr) {

varlen = arr.length;

varminIndex,temp;

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

minIndex = i;

for(varj = i+1; j < len;j++){

if(arr[j] < arr[minIndex]){

minIndex = j;

}

}

temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

return arr;

}

Analysis:

Stable: The default implementation is not stable
Worst and Average Case Time Complexity: O(n²) as there are two nested loops
Auxiliary Space: O(1). It never makes more than O(n) swaps and can be useful when memory write is a costly operation.

3. Insertion Sort

function insertionSort(arr) {

if (Object.prototype.toString.call(arr).slice(8,-1)===’Array’){

for(vari =1;i<arr.length;i++){

varkey = arr[i];

varj = i-1;

while(j>=0 && arr[j]>key){

arr[j+1]=arr[j];

j–;

}

arr[j+1]=key;

}

return arr;

}else{

return ‘arr is not an array!’

}

}

}

Analysis:

Stable: Yes
Worst and Average Case Time Complexity: O(n²)
Auxiliary Space: O(1)

4. Merge Sort

Array.prototype.mergeSort = function () {

constrec = (arr) => {

if(arr.length===1)returnarr;

constmid = Math.floor(arr.length/2);

constleft = arr.slice(0,mid);

constright = arr.slice(mid, arr.length);

constorderleft = rec(left);

constorderright = rec(right);

constres = [];

while(orderleft.length||orderright.length){

if(orderleft.length&&orderright.length){

res.push(orderleft[0]<orderright[0]?orderleft.shift():orderright.shift())

}else if(orderleft.length){

res.push(orderleft.shift())

}else if(orderright.length){

res.push(orderright.shift())

}

}

return res;

}

const res = rec(this);

res.forEach((n,i)=>{

this[i]=n;

})

}

Analysis:

Stable: Yes
Worst and Average Case Time Complexity: O(nlogn)
Auxiliary Space: O(n)

5. Quick Sort

Array.prototype.quickSort = function () {

constrec = (arr) => {

if(arr.length <= 1){

returnarr;

}

constleft = [];

constright = [];

constmid = arr[0];

for(leti = 1; i<arr.length; i++){

if(arr[i]<mid){

left.push(arr[i]);

}else{

right.push(arr[i])

}

}

return […rec(left),mid,…rec(right)];

};

constres = rec(this);

res.forEach((n,i)=>{this[i]=n})

}

Analysis:

Stable: Not Stable
Worst Case Time Complexity: O(n²) . The worst case occurs when the partition process always picks greatest or smallest element as pivot.
Best Case Time Complexity: O(nlogn) . The best case occurs when the partition process always picks the middle element as pivot.
Auxiliary Space: O(n)

More sorting algorithms, as well as animation demonstrations and details can be found here.