Thilina's Blog

Hope this will work..

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(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…..

About these ads

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

20 Comments »

  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

    Comment by Madhavi | 2012 January 15 | Reply

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

    Comment by Reader.. | 2012 December 17 | Reply

  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 :)

    Comment by pinklemonade | 2014 March 19 | Reply

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 74 other followers

%d bloggers like this: