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

Primitive Data Search - algorithms basic 01

Searching is a common way to find the target data in a data group. The data group contains the same data type.


Note that Java SE API provides a simple way of searching.
Arrays.binarySearch( ... ) 
Collections.binarySearch( ... )
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 searching  and to implement with other programming languages.


There are two common approaches:
1 Linear Search - go and compare with each item in a linear way
2 Binary Search - go and  compare with the middle item of each iteration


Example:
searching through a given group of integers with 10 elements:
int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };


we need to find out if this group has 20. if yes, show the index of 20, otherwise the index of 20 set to -1.
(0 is the beginning index of an array, so -1 means it is not in the array)


So how do we perform the search?
We aim to minimize the comparisons to find the target data fast.
Let's compare 2 basic search algorithms.


1 Linear Search
The linear search needs to go through each item, unless we are lucky that the first item is our target.
Here, it is obvious that there is no 20 in the integer array.
So, we need to perform 10 comparisons.
Code:

1. int a[] = { 7, 5, 8, 2, 9, 0, 3, 6, 1, 4 };
2. int target = 20;
3.   //try to change target to any value in the array
4. int found=-1;
5. for(int i=0;i<a.length;i++){
6. if(a[i]==target){
7. found=i;
8. }
9. }
10. System.out.println(found);

2 The Binary Search
The binary search needs roughly 3-4 comparisons to find 20
Well, first we need to sort the given array, whether in ascending or descending order, it is up to you.
int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
Since we know the order is ascending, let us begin the begin the Binary Search.
Steps:

1. find the element in the middle which is 4, 4 is less than 20, now we know anything on the left side of 4 does not have 20, so we move on.
2. find the element in middle of the right hand side of 4 which is 7, 7 is less than 20, we move on.
3. comparing 20 with 8 ...
4. comparing 20 with 9 ...   End of story!!!

Code:

1. int a[] = { 0, 1, 2, 3, 4, 5, 6,7,8,9 };
2. int target = 20;
3.   //try to change target to any value in the array
4. boolean isFound = false;
5. int len = a.length;
6. int begin = 0;
7. int end = len - 1;
8. int mid = (end - begin) / 2;
9. while (!isFound&&begin<=end) {
10. if (a[mid] == target) {
11. isFound = true;
12. break;
13. } else if (a[mid] < target) {
14. begin = mid+1;
15. } else {
16. end = mid-1;
17. }
18. mid = (end + begin) / 2;
19. }
20. System.out.println(isFound+" - "+mid);

Linear Search or Binary Search?
Linear Search does not require pre-sort the elements, and it is easy to code, maintain and debug. The time complexity of Linear Search is O(n). 


Binary Search requires pre-sort the elements, but it saves time in finding the target. The line of code are longer, so it takes time to code, maintain and debug. The time complexity of Binary Search is O(log2n)

Some people may think it doesn't matter which algorithm we perform here. Yes.

But if we are searching an element within a group with 1,000 or even 1,000,000 elements.

Binary Search helps to save heaps of time in such a case.

To Search Other Data Types:

Just like an integer array, you can easily implement the above algorithms with primitive data types char, float, double, short, long, byte.


For String, the String class implements Comparable interface, when we compare 2 Strings we use compareTo method.


For Object, the class must implement the Comparable interface, and we need to override the compareTo method.


Other references: 
Algorithm - Wikipedia
Analysis of algorithms - Wikipedia
Time complexity - Wikipedia
Binary search algorithm - Wikipedia