Let's be clear on the understanding about the sorting. We define problem in terms of input and output.
Here
Input: A sequence of n numbers (a1,a2,......,aN)
Output: A permutation (reordering) (a1',a2',......,aN') of the input sequence such that a1'<= a2'<=aN'.
Yes, Here we are going to deal with a problem of sorting numbers in the non decreasing order.
For solving this problem, one of the simplest algorithm is bubble sort or sinking sort which is easy to code but inefficient. So i have to give a warning "Don't try this in your app!"
Bubble sort, also known as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.This is a wiki definition.
Let's look at the algorithm. An important node Here i won't be giving any pseudocode. Instead i will be giving the implementation of the algorithm in Java.
public class BubbleSort {
public int[] sort(int []input){
for(int i=0;i<input.length;i++)
for(int j=i+1;j<input.length;j++){
if(input[i]>input[j]){
int temp = input[i];
//swap the elements
input[i] = input[j];
input[j] = temp;
}
}
return input;
}
public static void main(String[] args) {
new BubbleSort().sort(new int[]{10,23,2,5,23,675,1,23});
}
}
Here you need to iterate the array and while iterating for each element you have to find the element in that position. So we have to compare this with every element to check that whether this number is eligible to stay in that position. or for example if the position of the number is 2 in the array. Is this number the second smallest in the array? This is checked by comparing with the remaining elements of the array. This is a straightforward implementation of solving the problem.
Now let's talk of the design of the algorithm. Here this is designed by the fact that for every ith iteration we will find the ith smallest number. so if the algorithm is in the ith iteration then it should have completed all the
i-1 small elements. To find the ith smallest element it just have to compare with the rest of the elements because the i-1 elements have been sorted.
When we analyze the algorithm, we could find that for the given input size 'n', the algorithm will execute the loop n^2 times. since for every element it will check whether it is the smallest in the remaining elements. When we analyze the algorithm we will look for most running section of code.We will find out the no of times each line of code will run and then we take the higher order term. Then that is the worst case running time of the algorithm.So the running time will be O(n^2) in the worst case.
Now the correctness. To prove the correctness of the algorithm, we have to see the properties of the elements which we already processed before the current iteration. These properties are called loop invariant.
I will explain this. Here the loop is the two for loops in the code. Here property is that the elements before the current iteration will be in sorted order. To prove the correctness of the algorithm, we have to prove that this property holds for Initialization, Maintenance and Termination section of the code.
Initialization: It is true prior to the first iteration of the loop.
Maintenance: If it is true before an iteration of the loop, it remains true before the
next iteration.
Termination: When the loop terminates, the invariant gives us a useful property
that helps show that the algorithm is correct.
Here we can find that before the first iteration the no of elements already sorted is 0. This proves the Initialization. If we check the elements before every iteration, we can find that the no of elements sorted will be i-1 before ith iteration. This proves the Maintenance.When the loop terminates we can find that the whole array is sorted and the iteration is i+1 (but this iteration won't happen). At this point of time all the i ((i+1)-1) elements are sorted in the array. Thus the correctness of this algorithm is proved.
Coming up.. Insertion sort.
No comments:
Post a Comment