Eyes, JAPAN Blog > Common Sorting Algorithms And Analysis

## Common Sorting Algorithms And Analysis

ZHUOTAO LIAN

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(n2)
• 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(n2) 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(n2)
• 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<orderright?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;
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(n2) . 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.