Sorting Algorithms sample codes on JAVA, C++ and MATLAB

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. Since I was interested to work with C++ I decided to implement some of those algorithms to be familiar with the language, but later on I thought it may be useful to implement those in JAVA as well as in MATLAB. From this article I am going to share my experiences in implementing those codes in above languages. I used Wikipedia, sorting algorithms website and the book “Introduction to Algorithms 3e” as my references. The algorithms I implemented was,

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

Sample codes will be as below. In MATAB, this can be used to compare any numeric data type such as uint8, uint16, int8, int16, double, etc. But in case of JAVA and C++ I wrote them to work with integers. Since I am new to C++ I some good points in using arrays/pointers with C++, such as how to initialize an array with a length which is an argument of that function, to get the size of an array, etc. These codes may not be the optimised codes for above algorithms but a small attempt to implement those on three platforms.

Selection Sort

Selection sort is a comparison sort with O(n²) timing complexity making in-efficient on large sets. In this algorithm the element on active position (say i^th position) is compared with other positions (say i+1^th to n^th position) and swaps if it’s larger than the compared element.

MATLAB

function dataOut = selectionSort(data)
    lenD = size(data,2);
    for i=1:lenD
        j = i;
        for k = i:lenD
            if(data(j)>data(k))
                j = k;
            end
        end
        tmp = data(i);
        data(i) = data(j);
        data(j) = tmp;
     end
dataOut = data;

JAVA

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

C++

void SortAlgo::selectionSort(int data[], int lenD)
{
  int j = 0;
  int tmp = 0;
  for(int i=0;i<lenD;i++){
    j = i;
    for(int k = i;k<lenD;k++){
      if(data[j]>data[k]){
        j = k;
      }
    }
    tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
  }
}

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.

MATLAB

function dataOut = insertionSort(data)
  len = size(data,2);
  for j = 2:len;
    key = data(j);
    i = j-1;
    while(i>0 && data(i)>key)
      data(i+1) = data(i);
      i = i-1;
      data(i+1)=key;
    end
  end
dataOut = data;

JAVA

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;
}

C++

void SortAlgo::insertionSort(int data[], int lenD)
{
  int key = 0;
  int i = 0;
  for(int j = 1;j<lenD;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;
    }
  }
}

Bubble Sort

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

MATLAB

function dataOut = bubbleSort(data)
lenD = size(data,2);
for i = 1:lenD
  for j = (lenD):-1:(i+1)
    if(data(j)<data(j-1))
      tmp = data(j);
      data(j)=data(j-1);
      data(j-1)=tmp;
    end
  end
end
dataOut = data;

JAVA

public int[] bubbleSort(int[] data){
  int lenD = data.length;
  int tmp = 0;
  for(int i = 0;i<lenD;i++){
    for(int j = (lenD-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;
}

C++

void SortAlgo::bubbleSort(int data[], int lenD)
{
  int tmp = 0;
  for(int i = 0;i<lenD;i++){
    for(int j = (lenD-1);j>=(i+1);j--){
      if(data[j]<data[j-1]){
        tmp = data[j];
        data[j]=data[j-1];
        data[j-1]=tmp;
      }
    }
  }
}

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.

MATLAB

function dataOut = quickSort(data)
lenD = size(data,2);
ind = cast(floor(lenD/2),'uint8');
j = 1;
k = 1;
L = [];
R = [];
if(lenD<2)
  dataOut = data;
else
  pivot = data(ind);
  for i=1:lenD
    if(i~=ind)
      if(data(i)<pivot)
        L(j) = data(i);
        j = j+1;
      else
        R(k) = data(i);
        k = k+1;
      end
    end
  end
  L = quickSort(L);
  R = quickSort(R);
  dataOut = [L pivot R];
end

JAVA

public int[] quickSort(int[] data){
int lenD = data.length;
int pivot = 0;
int ind = lenD/2;
int i,j = 0,k = 0;
if(lenD<2){
  return data;
}
else{
  int[] L = new int[lenD];
  int[] R = new int[lenD];
  int[] sorted = new int[lenD];
  pivot = data[ind];
  for(i=0;i<lenD;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;
  }
}

C++

void SortAlgo::quickSort(int* data, int const len)
{
  int const lenD = len;
  int pivot = 0;
  int ind = lenD/2;
  int i,j = 0,k = 0;
  if(lenD>1){
    int* L = new int[lenD];
    int* R = new int[lenD];
    pivot = data[ind];
    for(i=0;i<lenD;i++){
      if(i!=ind){
        if(data[i]<pivot){
          L[j] = data[i];
          j++;
        }
        else{
          R[k] = data[i];
          k++;
        }
      }
    }
    quickSort(L,j);
    quickSort(R,k);
    for(int cnt=0;cnt<lenD;cnt++){
      if(cnt<j){
        data[cnt] = L[cnt];;
      }
      else if(cnt==j){
        data[cnt] = pivot;
      }
      else{
        data[cnt] = R[cnt-(j+1)];
      }
    }
  }
}

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.

MATLAB

function dataOut = mergeSort(data)
lenD = size(data,2);
if(lenD<2)
  dataOut = data;
else
  middle = cast(floor(lenD/2),'uint16');
  L = data(1:middle);
  R = data(middle+1:end);
  L = mergeSort(L);
  R = mergeSort(R);
  dataOut = merge(L, R);
end
function dataOut = merge(L,R)
lenL = size(L,2);
lenR = size(R,2);
i = 0;
j = 0;
merged = [];
while(i<lenL||j<lenR)
  if (i<lenL && j<lenR)
    if(L(i+1)<=R(j+1))
      merged(i+j+1) = L(i+1);
      i = i+1;
    else
      merged(i+j+1) = R(j+1);
      j = j+1;
    end
  elseif(i<lenL)
    merged(i+j+1) = L(i+1);
    i = i+1;
  elseif(j<lenR)
    merged(i+j+1) = R(j+1);
    j = j+1;
  end
end
dataOut = merged;

JAVA

public int[] mergeSort(int[] data){
  int lenD = data.length;
  if(lenD<=1){
    return data;
  }
  else{
    int[] sorted = new int[lenD];
    int middle = lenD/2;
    int rem = lenD-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;
}

C++

void SortAlgo::mergeSort(int data[], int lenD)
{
  if(lenD>1){
    int middle = lenD/2;
    int rem = lenD-middle;
    int* L = new int[middle];
    int* R = new int[rem];
    for(int i=0;i<lenD;i++){
      if(i<middle){
        L[i] = data[i];
      }
      else{
        R[i-middle] = data[i];
      }
    }
    mergeSort(L,middle);
    mergeSort(R,rem);
    merge(data, lenD, L, middle, R, rem);
  }
}

void SortAlgo::merge(int merged[], int lenD, int L[], int lenL, int R[], int 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++;
    }
  }
}

Shell Sort

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

MATLAB

function dataOut = shellSort(data)
lenD = size(data,2);
inc = cast(lenD/2,'int16');
while(inc>0)
  for i=inc:lenD
    tmp = data(i);
    j = i;
    while(j>inc && data(j-inc)>tmp)
      data(j) = data(j-inc);
      j = j-inc;
    end
    data(j) = tmp;
  end
  inc = cast(floor(double(inc) /2),'int16');
end
dataOut = data;

JAVA

public int[] shellSort(int[] data){
  int lenD = data.length;
  int inc = lenD/2;
  while(inc>0){
    for(int i=inc;i<lenD;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;
}

C++

void SortAlgo::shellSort(int data[], int lenD)
{
  int inc = lenD/2;
  while(inc>0){
    for(int i=inc;i<lenD;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);
  }
}

Thank you very much for reading…..