Wednesday, November 27, 2013

Bubble Sort

Sort Average Best Worst Space Stability Remarks
Bubble sort O(n^2) O(n^2) O(n^2) Constant Stable Always use a modified bubble sort
Modified Bubble sort O(n^2) O(n) O(n^2) Constant Stable Stops after reaching a sorted array
Selection Sort O(n^2) O(n^2) O(n^2) Constant Stable Even a perfectly sorted input requires scanning the entire array
Insertion Sort O(n^2) O(n) O(n^2) Constant Stable In the best case (already sorted), every insert requires constant time
Heap Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Constant Instable By using input array as storage for the heap, it is possible to achieve constant space
Merge Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Depends Stable On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space
Quicksort O(n*log(n)) O(n*log(n)) O(n^2) Constant Stable Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst case scenarios such as a perfectly sorted array.


this is bubble sort example



lets make it c language


#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
 int arr[] = {5, 1, 12, -5, 16, 2, 12, 14};

 int count;
 int i=0, j=0, k=0, temp;
 count = sizeof(arr)/sizeof(arr[0]);
 for(j; j<count -1; j++){
  for(i=0; i<count-1-j; i++){
   if(arr[i]> arr[i+1]){
    temp = arr[i];
    arr[i]= arr[i+1];
    arr[i+1]= temp;
   }
  }
 
  k=0;
  for(k=0; k<count; k++){
   printf("%d ", arr[k]);
  }
  printf("\n");
 }
 return 0;
}


result :

1 5 -5 12 2 12 14 16
1 -5 5 2 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16
-5 1 2 5 12 12 14 16

No comments:

Post a Comment