The basic algorithms which have been traditionally emphasized are search and sort algorithm. There are innumerous algorithms recognized or de-recognized, ultimate or intermediate or preliminary, with different complexity and problem space, but searching and sorting over a set of data are the entry point to this world of algorithms. These basic steps not only provide us a solution but alos give a way to think on how to solve bigger problems. In real life scenarios one rarely gets a problem where one has to sort a set of data/numbers as an isolated question. Even if one gets every language provides already existing tested and efficient libraries that provide such functionality. And I will suggest that one should use them rather than re-inventing the wheel(with possible glitches). Nonetheless learning such algorithm is useful to get an approach towards solving a problem.
So let us talk about Sorting. To sort is to rearrange the data in a monotonically increasing or decreasing order. In simple words arrange given numbers(~data) in increasing or decreasing order. So what is the first requisite for a data set to be sortable? The data set should be of single type. One cannot compare two different kind of data.(unless some correlation is already established).
The second prerequisite is that the two data points or elements should be comparable. Can you compare two persons? No . You can compare their heights, weights or some other mathematical index that represents them. So essentially whenever you are sorting some dataset you first look for the comparable mathematical index(or indices) and the comparision function (say f(i1,i2...,ik))
Now we are ready to sort. I will show you an algorithm which we call bubble sort.
The idea behind bubble sort is let the lightest settle at the top (like a bubble) or the heaviest settle in bottom (as in sedimentation).
Logically it goes like this:
We have to bubble up the smallest element. How does the bubble come up. Suppose the lightest layer(smallest element) is at the bottom. It will compare itself to the next upper layer. If it is lighter than next upper layer, it will go up and the upper layer will go down. This is called 'swap'. It will continue going up till it finds any other layer lighter than itself. In all cases the topmost layer will be lightest. Now skim off the topmost layer and let the setup rearrange again. Again the lightest in the remaining will come to the top. So one by one we go on collecting the smallest layers or bubbles and finally we have a sorted array.
I will not write the algorithm and instead directly give you the working code in java.
An Utility class:
import java.util.Random;
public class Utility {
static int[] array = new int[10];
static Random random = new Random();
public static int[] getArray() {
for(int i = 0; i <10; i++){
array[i]= random.nextInt(100)%100;
}
return array;}
public static int[] getArrayTen() {
for(int i = 0; i <10; i++){
array[i]= random.nextInt(10)%10;
}
return array;}
public static void setArray(int[] array) {
Utility.array = array;
}
public static void swap(int[] array,int i, int j)
{int temp = array[i];array[i]= array[j];
array[j] = temp;
}
public static void display(int[] array2) {
for (int i : array2) {
System.out.print(" " + i);
}
}
}
The Bubble Sort Class:
package kumar.test.sort;
public class BubbleSort {
public static void main(String[] args) {
System.out.println("before sort");
int[] array = Utility.getArray();Utility.display(array);
System.out.println();System.out.println("***********************************");
bubbleSort(array);
System.out.println();System.out.println("***********************************");
System.out.println("after sort");
Utility.display(array);
}
public static void bubbleSort(int[] array)
{for(int i = 0; i <array.length; i++)
{for (int j = array.length-1; j> i; j--)
{if(array[j] > array[j-1]){Utility.swap(array, j, j-1);
}
}
System.out.println( "After cycle "+ (i+1));
Utility.display(array);
System.out.println();}
}
}
Sample Output:
before sort
92 64 4 28 89 41 58 80 37 54
***********************************
After cycle 1
92 89 64 4 28 80 41 58 54 37
After cycle 2
92 89 80 64 4 28 58 41 54 37
After cycle 3
92 89 80 64 58 4 28 54 41 37
After cycle 4
92 89 80 64 58 54 4 28 41 37
After cycle 5
92 89 80 64 58 54 41 4 28 37
After cycle 6
92 89 80 64 58 54 41 37 4 28
After cycle 7
92 89 80 64 58 54 41 37 28 4
After cycle 8
92 89 80 64 58 54 41 37 28 4
After cycle 9
92 89 80 64 58 54 41 37 28 4
After cycle 10
92 89 80 64 58 54 41 37 28 4
***********************************
after sort
92 89 80 64 58 54 41 37 28 4
The Sample provided here is inverse of bubble sort i.e Sedmintation salt where I am allowing the largest value to settle down at bottom in every cycle. You can try writing original bubble sort following this example.
No comments:
Post a Comment