:
- Will be very quick on an already sorted list.
Cons
Probably the slowest sort ever invented.
Working of bubble sort algorithm:
Say we have an array unsorted A[0],A[1],A[2]................
A[n-1] and A[n] as input. Then the following steps are followed by bubble
sort algorithm to sort the values of an array.
1.Compare A[0] and A[1] .
2.If A[0]>A[1] then Swap A[0] and A[1].
3.Take next A[1] and A[2].
4.Comapre these values.
5.If A[1]>A[2] then swap A[1]
and A[2]
...............................................................
................................................................
at last compare A[n-1] and A[n]. If
A[n-1]>A[n] then swap A[n-1] and A[n]. As we see the highest value is
reached at nth position. At next iteration leave nth value. Then apply the
same steps repeatedly on A[0],A[1],A[2]................ A[n-1] elements repeatedly until the values of array is sorted.
In our example we are taking the following array values
12 9 4 99 120 1 3 10
The basic steps followed by algorithm:-
In the first step compare first two values 12 and 9.
12 9 4 99 120 1 3 10
As 12>9 then we have to swap these values
Then the new sequence will be
9 12 4 99 120 1 3 10
In next step take next two values 12 and 4
9 12 4 99 120 1 3 10
Compare these two values .As 12>4 then we have to swap these values.
Then the
new sequence will be
9 4 12 99 120 1 3 10
We have to follow similar steps up to end of array. e.g.
9 4 12 99 120 1 3 10
9 4 12 99 120 1 3 10
9 4 12 99 1 120 3 10
9 4 12 99 1 120 3 10
9 4 12 99 1 3 120 10
9 4 12 99 1 3 10 120
When we reached at last index .Then restart same steps unlit the
data is not sorted.
The output of this example will be :
1 3 4 9 10 12 99 120
int array[] = {12,9,4,99,120,1,3,10};
bubble_srt(array, array.length);
public static void bubble_srt( int a[], int n ){
int i, j,t=0;
for(i = 0; i < n; i++){
for(j = 1; j < (n-i); j++){
if(a[j-1] > a[j]){
t = a[j-1];
a[j-1]=a[j];
a[j]=t;
}
}
}
}
Notes: Don't
bother learning this sort. There are other sorts which are just as easy
to implement and much faster. Although there are some time saving
modifications that can be made (e.g. keeping track of the last swap in
the previous pass, and only going up to there in the current pass), they
aren't worth it.
Reference: roseindia
There are two types of heap. First one is Max heap and second one is min
heap. Max heap is a special type of binary tree .The roots of the max heap
is greater than its child roots. Other heap is min heap it is also a special
type of heap which has minimum root than his child. We can sort the array values
using heap sorting algorithm. In this algorithm the heap build is used to
rebuild the heap.
In this example we sorting all elements of an array. The complexity of the heap sort is O(n.log(n)). Heap sort is slowest but it is better
option for large data sets.
To sort a heap Build Heap algorithm is used to build a heap out of the
data set. Then remove the root element and replace the last element at the
position of root node. Then rearrange the heap. Place the root node in an array.
Follow these steps until all elements in heap is not replace into array. The
values in array will be in sorted order.
Algorithm: Add
the elements to a heap one at a time. Then remove the elements from the
top of the heap one at a time, and they will be in order. If the heap
is done upside down (i.e. largest element at the root) then the
incomplete sorted list and the heap can share the same array without
requiring extra memory.
Steps of heap sort algorithm:
1. Remove the parent root and replace it with the rightmost leaf.
2.Store parent root in an array.
3. Re-establish the heap.
4. Repeat steps 1 and 3 until values in heap is not zero.
Pros:
- Guaranteed to be O(n.log n)
- One of the few non-recursive O(n.log n) sorts
- Fairly easy to debug, because it is non-recursive and because it consists of two smaller and unrelated parts
Cons
- Not as fast on average as Quick sort
- Quite a lot of code to implement the heap operations.
Working of heap sort algorithm:
Input:1,3,5,4,2
Step1:Buid Heap tree and an array of same size.
Step2: Remove largest root and add largest root in array.
Step3:Replace last value (eg 2) at at root node position.
Step4:Swap 2 and 4
Step5:Swap 2 and 3.
Step6:Remove 4 and replace 2 at position of 4 and add 4 in array
Step7:Swap 2 and 3
Step8:Remove 3 ,add in array and replace 1 at position of 3.
Step9:Swap 2 and 1.
Step10:Remove 2 and it at root position
Step11:Remove 1 and add in array.
Output: Sorted array 1,2,3,4,5
public class heap_Sort{
public static void main(String a[]){
int i;
int arr[] = {1,3,4,5,2};
System.out.println("\n Heap Sort\n---------------\n");
System.out.println("\n Unsorted Array\n\n");
for (i = 0; i < arr.length; i++)
System.out.print(" "+arr[i]);
for(i=arr.length; i>1; i--){
fnSortHeap(arr, i - 1);
}
System.out.println("\n Sorted array\n---------------\n");
for (i = 0; i < arr.length; i++)
System.out.print(" "+arr[i]);
}
public static void fnSortHeap(int array[], int arr_ubound){
int i, o;
int lChild, rChild, mChild, root, temp;
root = (arr_ubound-1)/2;
for(o = root; o >= 0; o--){
for(i=root;i>=0;i--){
lChild = (2*i)+1;
rChild = (2*i)+2;
if((lChild <= arr_ubound) && (rChild <= arr_ubound)){
if(array[rChild] >= array[lChild])
mChild = rChild;
else
mChild = lChild;
}
else{
if(rChild > arr_ubound)
mChild = lChild;
else
mChild = rChild;
}
if(array[i] < array[mChild]){
temp = array[i];
array[i] = array[mChild];
array[mChild] = temp;
}
}
}
temp = array[0];
array[0] = array[arr_ubound];
array[arr_ubound] = temp;
return;
}
}
Notes: This isn't an especially useful sort, but the running time is
guaranteed O(n.log n) and it is very light on memory consumption. Also,
if you have already implemented a heap for some other reason, then this sort comes almost for free. It
is possible to get some extra speed by constructing the heap in one
pass: put everything into the heap ignoring the heap condition, then
work through the heap from bottom to top, bubbling elements down the
heap where necessary. This makes the heap creation take linear time.
Reference: roseindia
