# Thilina's Blog

## 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(n2) timing complexity making in-efficient on large sets. In this algorithm the element on active position (say ith position) is compared with other positions (say i+1th to nth 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…..

2011 June 1 - Posted by | C++, Java, MATLAB

1. Thanks !!!

Comment by Nuwan | 2011 June 2 | Reply

• :) :)

Comment by Thilina S. | 2011 June 2 | Reply

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

• Thank you very much for the corrections Madhavi :)

Comment by Thilina S. | 2012 January 15 | Reply

3. Thanks! This was very helpful.

Comment by Bob Johnson | 2012 April 2 | Reply

4. really, these algo are so helpful for sorting. thankyou

Comment by reena | 2012 June 27 | Reply

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

6. Thanks

Comment by sajmax1992 | 2012 December 30 | Reply

7. 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 | Reply

• Thanks a lot for the comment and correction.

Comment by Thilina S. | 2013 February 13 | Reply

8. thanx for help :)

Comment by anum | 2013 April 4 | Reply

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

Comment by Bhupathi | 2013 April 21 | Reply

10. 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 | Reply

11. thank you very much

Comment by chin | 2013 August 26 | Reply

12. thank you so mach silina whit the best wishes for you
i am farzane from iran

Comment by farzaneh | 2013 November 18 | Reply

13. this was so helpful! thanks so much :)

14. thank u :)

Comment by Varsha Kaverappa | 2014 March 20 | Reply

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

Comment by java2novice | 2014 April 9 | Reply

16. 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 | Reply

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