Overview :- We will start with sorting techniques. To start fast we will pick the easiest sorting technique like Bubble sort
Java program :-
public class BubbleSort {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
//plain logic for bubble sort
int a [] = {4,30,-3,7,1,20,12,50,-9,-1,89,14,13};
int count =0;
for(int i=0;i<a.length;i++){
count=count+1;
for(int j=i+1;j<a.length;j++){
count=count+1;
if(a[i]>a[j]){
int temp;
temp =a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
System.out.println(" count via bubble sort first approach :- "+count);
for(int i=0;i<a.length;i++){
System.out.println(" elements :- "+a[i]);
}
int b [] = {4,30,-3,7,1,20,12,50,-9,-1,89,14,13};
fasterBubbleSort(b);
int c [] = {4,30,-3,7,1,20,12,50,-9,-1,89,14,13};
bubbleSorting(c);
}
//alternate logic for bubble sort
public static void bubbleSorting(int[] a){
int count =0;
for(int i=0;i<a.length;i++){
count=count+1;
for(int j=0;j<(a.length-i-1);j++){
count=count+1;
if(a[j]>a[j+1]){
int temp;
temp =a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
System.out.println("count via alternate bubble sort :-"+count);
}
//smarter logic for bubble sort
public static void fasterBubbleSort(int[] testArray) {
System.out.println("length :-"+testArray.length);
boolean isSwapped = true;
int i = 0;
int count =0;
while (isSwapped ) {
isSwapped = false;
i++;
for (int j = 0; j < testArray.length - i; j++) {
count=count+1;
if (testArray[j] > testArray[j + 1]) {
int temp = testArray[j];
testArray[j] = testArray[j + 1];
testArray[j + 1] = temp;
isSwapped = true;
}
}
}
System.out.println("count via faster bubble sort :-"+count);
}
}
Simple explanation :- Take first element and go to all other elements and check > or < based on condition{ascending/descending} swap it. Like that do it for every element that's it. Don't confuse your selves with time complexity . Its nothing but how much time it is taking to execute your code. And how it will work when inputs are big. To know the time complexity just count how many loops the program is executing.
Now time complexity :- Now about the time complexity for the bubble sort by leaving smart approach. n+n-1 + n-2... = n(n-1)/2 its our old school formula. The same thing happens here because we will be taking each value in array and compare with all other elements that exactly follows the sequence i have mentioned above.so n^2 /2 - n/2. When n^2 is very big we can remove n/2. So now we have to complexity of n^2/2.
