OPTIMIZED IMPLEMENTATION OF BUBBLE SORT IN C

http://www.codingeek.com/algorithms/bubble-sort-algorithm-and-implementation-multiple-programming-languages/

OPTIMIZED IMPLEMENTATION OF BUBBLE SORT IN C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

// Optimized implementation of Bubble sort #include <stdio.h> #include<stdbool.h> // To use bool variable in our code void swap(int *xp, int *yp) {     int temp = *xp;     *xp = *yp;     *yp = temp; }   // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {    int i, j;    bool isSorted;    for (i = 0; i < n-1; i++)    {      isSorted = true;      for (j = 0; j < n-i-1; j++)      {         if (arr[j] > arr[j+1])         {            swap(&arr[j], &arr[j+1]);            isSorted = false;         }      }        // IF no two elements were swapped by inner loop, then break      if (isSorted)         break;    } }   /* Function to print an array */ void printArray(int arr[], int size) {     int i;     for (i=0; i < size; i++)         printf("%d ", arr[i]);     printf("\n"); }   // Driver program to test above functions int main() {     int arr[] = {64, 34, 25, 12, 22, 11, 90};     int n = sizeof(arr)/sizeof(arr[0]);     bubbleSort(arr, n);     printf("Sorted array: \n");     printArray(arr, n);     return 0; } Algorithms Bubble Sort Quincy Larson edited this page on Aug 19, 2016 · 1 revision  Pages 833 ⚠️ Deprecation Notice ⚠️ This wiki has moved to our forum. It has its own section there. As a result, it's even easier to edit wiki articles and contribute new ones. Head on over: https://forum.freecodecamp.com/c/wiki This GitHub-based wiki that you're looking is out-of-date. We will soon delete it completely. Clone this wiki locally  Clone in Desktop Algorithm Bubble Sort Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison based algorithm in which each pair of adjacent elements is compared and elements are swapped if they are not in order. This algorithm does sorting in-place i.e. it does not creates a new array while carrying out the sorting process. Example Animation of BubbleSort array = [5, 1, 4, 2, 8] First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) C++ Implementation // Function to implement bubble sort void bubble_sort(int array[], int n) { // Here n is the number of elements in array int temp; for(int i = 0; i < n-1; i++) { // Last i elements are already in place for(int j = 0; j < n-i-1; j++) { if (array[j] > array[j+1]) { // swap elements at index j and j+1 temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }  Run Code Python Implementation def bubble_sort(arr): exchanges = True # A check to see if the array is already sorted so that no further steps gets executed i = len(arr)-1 while i > 0 and exchanges: exchanges = False for j in range(i): if arr[j]>arr[j+1]: exchanges = True arr[j], arr[j+1] = arr[j+1], arr[j] i -= 1 arr = [5,3,23,1,43,2,54] bubble_sort(arr) print(arr) # Prints [1, 2, 3, 5, 23, 43, 54]  Run Code Complexity of Algorithm https://github.com/freeCodeCamp/freeCodeCamp/wiki/Algorithms-Bubble-Sort Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted i.e. the elements are in decreasing order Best Case Time Complexity: O(n). Best case occurs when array is already sorted.