## 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,

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^{2}) 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…..

Thanks !!!

Comment by Nuwan | 2011 June 2 |

Comment by Thilina S. | 2011 June 2 |

What you have explained as “Selection sort” is actually “Exchange sort”, a cousin of the bubble sort. This is how Selection sort actually works – http://mathbits.com/mathbits/Java/arrays/SelectionSort.htm

Comment by Madhavi | 2012 January 15 |

Thank you very much for the corrections Madhavi

Comment by Thilina S. | 2012 January 15 |

Thanks! This was very helpful.

Comment by Bob Johnson | 2012 April 2 |

really, these algo are so helpful for sorting. thankyou

Comment by reena | 2012 June 27 |

Thanks for this post.. I got nize summary form this..

Comment by Reader.. | 2012 December 17 |

Thanks

Comment by sajmax1992 | 2012 December 30 |

Hi, thanks it is helpful. One correction:

To sort all data values with bubbleSort,m the line 7 should be :

for j = (lenD ):-1:(i+1) .

Dima

Comment by Dima | 2013 February 13 |

Thanks a lot for the comment and correction.

Comment by Thilina S. | 2013 February 13 |

thanx for help

Comment by anum | 2013 April 4 |

It was amazing to understand the algorithm and sample code example. Keep rocking

Comment by Bhupathi | 2013 April 21 |

thnx for simplest overview …

I think in quick sort java algo,

int[] L = new int[lenD];

int[] R = new int[lenD];

****new int[lenD];

since its an array … which leads to unnecessary waste of memory i guess.

it can bet initialised with

new int[lenD/2];

Comment by Lieu | 2013 May 31 |

thank you very much

Comment by chin | 2013 August 26 |

thank you so mach silina whit the best wishes for you

i am farzane from iran

Comment by farzaneh | 2013 November 18 |

Thank you very much..

Comment by Thilina S. | 2013 November 18 |

this was so helpful! thanks so much

Comment by pinklemonade | 2014 March 19 |

thank u

Comment by Varsha Kaverappa | 2014 March 20 |

very nice. for more java examples visit http://java2novice.com site

Comment by java2novice | 2014 April 9 |

Hey, I just want to say thanks. I have been crawling the internet for Java implementation of a shell sort for many hours. Everyone keeps using the native Java comparable method. You want to read a pure algorithm when studying it. Again thanks.

Comment by chasethewhiterabbitt | 2014 July 22 |

Very Useful. For more examples visit http://answersz.com

Comment by Answerz Answerz | 2014 December 15 |

I think the matlab algorithm for megesort has something wrong, the output is half the length of the input

Comment by Ahmed A. Mostafa | 2015 January 28 |

thanks so much

Comment by brkt | 2015 December 27 |

nice merge sort code, for step by step explanation visit http://www.hellgeeks.com/merge-sort/

Comment by Romeo Off Gcu | 2016 January 9 |

I need programming 5 String algorithm in 1 program

please help

Comment by aram | 2016 January 10 |