General Sorting Algorithms

Sorting is the process which puts the elements in a list to an order. Sorting algorithms are used to optimize the performance and resources usage in computer science.
Here is I'm going to show common sort algorithms.

1. Selection Sort
2. Insertion Sort
3. Bubble Sort
4. Quick Sort
5. Merge Sort
6. Shell Sort

Selection Sort

Selection sort is a comparison sort with O(n²) timing complexity making in-efficient on large lists. The algorithm divides the input list into two parts: the sublist of items already sorted and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

public int[] selectionSort(int[] data){
  int len = data.length;
  int j = 0;
  int tmp = 0;
  for(int i=0;i < len; i++){
    j = i;
    for(int k = i;k < len; k++){
      if(data[j]>data[k]){
        j = k;
      }
    }
    tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
  }
  return data;
}

Insertion Sort

Insertion sort is a comparison sort algorithm which works similar to the way we arrange the cards in a hand. We take one element at a time, starts compare from one end and them place them in between the card lesser and greater than it.

public int[] InsertionSort(int[] data){
  int len = data.length;
  int key = 0;
  int i = 0;
  for(int j = 1;j < len; j++){
    key = data[j];
    i = j-1;
    while(i>=0 && data[i]>key){
      data[i+1] = data[i];
      i = i-1;
      data[i+1]=key;
    }
  }
  return data;
}

Bubble Sort

Bubble sort is a simple algorithm which compares neighbouring elements and swaps them if they are not in the order.

public int[] bubbleSort(int[] data){
  int len = data.length;
  int tmp = 0;
  for(int i = 0;i < len;i++){
    for(int j = (len-1);j>=(i+1);j--){
      if(data[j] < data[j-1]){
        tmp = data[j];
        data[j]=data[j-1];
        data[j-1]=tmp;
      }
    }
  }
  return data;
}

Quick Sort

Quick sort is an algorithm with O(n.log(n)) average timing complexity. This algorithm is a recursive algorithm. In here it select an element (randomly or middle element of the array) and put elements to left to it if its lesser that it or to right side otherwise till all elements are sorted.

public int[] quickSort(int[] data){
int len = data.length;
int pivot = 0;
int ind = len/2;
int i,j = 0,k = 0;
if(len < 2){
  return data;
}
else{
  int[] L = new int[len];
  int[] R = new int[len];
  int[] sorted = new int[len];
  pivot = data[ind];
  for(i=0;i < len; i++){
    if(i!=ind){
      if(data[i] < pivot){
        L[j] = data[i];
        j++;
      }
      else{
        R[k] = data[i];
        k++;
      }
    }
  }
  int[] sortedL = new int[j];
  int[] sortedR = new int[k];
  System.arraycopy(L, 0, sortedL, 0, j);
  System.arraycopy(R, 0, sortedR, 0, k);
  sortedL = quickSort(sortedL);
  sortedR = quickSort(sortedR);
  System.arraycopy(sortedL, 0, sorted, 0, j);
  sorted[j] = pivot;
  System.arraycopy(sortedR, 0, sorted, j+1, k);
  return sorted;
  }
}

Merge Sort

Merge sort is an algorithm with O(n.log(n)) timing complexity for all cases. This algorithm is a divide and conquer algorithm. Merge sort has two parts which comparison and merging part.

public int[] mergeSort(int[] data){
  int len = data.length;
  if(len<=1){
    return data;
  }
  else{
    int[] sorted = new int[len];
    int middle = len/2;
    int rem = len-middle;
    int[] L = new int[middle];
    int[] R = new int[rem];
    System.arraycopy(data, 0, L, 0, middle);
    System.arraycopy(data, middle, R, 0, rem);
    L = this.mergeSort(L);
    R = this.mergeSort(R);
    sorted = merge(L, R);
    return sorted;
  }
}
 
public int[] merge(int[] L, int[] R){
  int lenL = L.length;
  int lenR = R.length;
  int[] merged = new int[lenL+lenR];
  int i = 0;
  int j = 0;
  while(i < lenL||j < lenR){
    if(i < lenL & j < lenR){
      if(L[i]<=R[j]){
        merged[i+j] = L[i];
        i++;
      }
      else{
        merged[i+j] = R[j];
        j++;
      }
    }
    else if(i < lenL){
      merged[i+j] = L[i];
      i++;
    }
    else if(j < lenR){
      merged[i+j] = R[j];
      j++;
     }
   }
   return merged;
}

Shell Sort

Shell sort is a generalised form of insertion sort algorithm which improved the performance of insertion sort.

public int[] shellSort(int[] data){
  int lenD = data.length;
  int inc = len/2;
  while(inc>0){
    for(int i=inc;i < len; i++){
      int tmp = data[i];
      int j = i;
      while(j>=inc && data[j-inc]>tmp){
        data[j] = data[j-inc];
        j = j-inc;
      }
      data[j] = tmp;
    }
    inc = (inc /2);
  }
  return data;
}

All Java sources are here: Source codes.