Sequential Sort - algorithms basic 02

Sorting is a common way to make a group of data with the same data type in an ordered manner (ascending or descending).

Note that Java SE API provides a simple way of sorting.

Arrays.sort( ... )

Collections.sort( ... )

check: Java SE API - Oracle Java Platform SE 6.0

     - java.util.Collections

     - java.util.Arrays

But thinking deeper of what is inside the method helps us to understand more about sorting  and to implement with other programming languages.

There are two types of sorting which are Sequential Sort and Recursive Sort.

In general, Sequential Sort is simple but slower, Recursive Sort is much faster but requires more algorithmic understanding. 

Sequential Sort

1 Selection Sort - continuously finding the smallest or the greatest element in each iterated subset and swapping with the beginning element of the subset

2 Insertion Sort - continuously inserting the element into an iterated subset in a given order

3 Bubble Sort - continuously comparing the nearing 2 elements and swapping the element in a given order

Example:

sorting a given group of integers with 10 elements in the ascending order:
int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };

1 Selection Sort

Steps:

1. find the smallest value from a[0] to a[a.length-1] which is 0, now swap 7 and 0
2. find the smallest value from a[1] to a[a.length-1] which is 1, now swap 5 and 1 
3. ...
4. repeat the finding and swapping throughout each iteration, until reach the end of this array
5. the array is sorted

Code:

1.  int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };
2.  int k;
3.  int minValue;
4.  for (int i = 0; i < a.length-1; i++) {
5.    k = i;
6.    for (int j = k + 1; j < a.length; j++) {
7.      if (a[k] > a[j]) { //change to a[k]<a[j] to sort in the descending order
8. k = j; // record index of the smallest value
9.      }
10.    }
11.    if (k != i) { // to avoid swapping with self
12.       minValue = a[k];
13.       a[k] = a[i];
14.       a[i] = minValue;
15.    }
16.  }

2 Insertion Sort

Steps:

1. insert a[1] correctly into the first subset contains {a[0], a[1]} ,  the first subset is sorted, move to the next element
2. insert a[2] anywhere correctly into the first sorted subset, move to the next element
3. insert a[3] correctly into the second sorted subset ...
4. ...
5. until the iteration finish, now the array is sorted

Code:

1.  int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };
2.  int j;
3.  int min;
4.  for(int i=1;i<a.length;i++){
5.    j = i;
6.    min=a[i];//min moves toward right after each outer loop
7.    while(j>0&&a[j-1]>min){ //a[j-1]<min  in a descending order
8.      a[j]=a[j-1];
9.      j--;
10.    }
11.    a[j]=min;
12.  }

3 Bubble Sort

Steps:

1. comparing a[0] and a[1], swap if needed, than comparing a[1] and a[2] ... until the greatest value moves to the end of the array
2. now comparing a[0] and a[1] ... just like the first round, until the second greatest value next to the greatest value
3. ...
4. after moving all the comparatively greater values towards the end of the array, this array is sorted

Code:

1.  int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };
2.  int temp;
3.  for(int i=a.length-1;i>=1;i--){
4.     for(int j=0;j<=i-1;j++){
5.       if(a[j]>a[j+1]){ //a[j]<a[j+1] in a descending order
6.           temp=a[j];
7.          a[j]=a[j+1];
8.          a[j+1]=temp;
9.       }
10.   }
11. }

The problem of Sequential Sort:

When dealing with a large amount of data, sometimes it seems to be antique. That is why there are many other sorting algorithms called Recursive Sort in general which performs in a recursive way, such as Merge Sort, Quick Sort, Heap Sort, Shell Sort ... etc 

But there are still methods to optimize the Sequential Sort, such as mix a Binary Search algorithm with Insertion Sort.

Why there are so many sorting algorithms?

Well, I have no idea why people invented all these sorting methods, but all these people are masters of programmers. There must be some reasons.

In different cases, where different algorithms are needed to solve particular problems.

It always aims to minimize the time complexity, and to give better performance.

Other references:

Sorting algorithm - Wikipedia
Selection sort - Wikipedia
Insertion sort - Wikipedia
Bubble sort - Wikipedia