Bubble sort implementation
Table of Content:
This sorting algorithm is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large datasets as its average and worst case complexity is of ?(n2) where n is the number of items.
Bubble sort is a simple sorting algorithm. Bubble Sort Algorithm is used to arrange N elements in ascending order, and for that you have to begin with 0th element and compare it with the first element. If the 0th element is found greater than the 1st element then the swapping operation will be performed i.e. the two values will get interchanged. In this way all the elements of the array gets compared.
Logic to sort array in ascending order
There are numerous logic to sort given set of numbers. Here I am using general algorithm which we apply in real life for simplicity. To sort array we select an element and place it to its correct position by comparing with subsequent elements.
Step by step descriptive logic to sort array in ascending order.
- Input size of array and elements in array. Store it in some variable say
sizeandarr. - To select each element from array, run an outer loop from 0 to
size - 1. The loop structure must look likefor(i=0; i < size; i++). - Run another inner loop from
i + 1tosize - 1to place currently selected element at its correct position. The loop structure should look likefor(j = i + 1; j < size; j++). - Inside inner loop to compare currently selected element with subsequent element and swap two array elements if not placed at its correct position.
Which is
if(arr[i] > arr[j])then swaparr[i]witharr[j].
Algorithm for Bubble Sort
- algorithm Bubble_Sort(list)
- Pre: list != fi
- Post: list is sorted in ascending order for all values
- for i <- 0 to list:Count – 1
- for j <- 0 to list:Count – 1
- if list[i] < list[j]
- Swap(list[i]; list[j])
- end if
- end for
- end for
- return list
- end Bubble_Sort
Program to sort array in ascending order
/** * C program to sort elements of array in ascending order */ #include <stdio.h> #define MAX_SIZE 100 // Maximum array size int main() { int arr[MAX_SIZE]; int size; int i, j, temp; /* Input size of array */ printf("Enter size of array: "); scanf("%d", &size); /* Input elements in array */ printf("Enter elements in array: "); for(i=0; i<size; i++) { scanf("%d", &arr[i]); } for(i=0; i<size; i++) { /* * Place currently selected element array[i] * to its correct place. */ for(j=i+1; j<size; j++) { /* * Swap if currently selected array element * is not at its correct position. */ if(arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } /* Print the sorted array */ printf("\nElements of array in ascending order: "); for(i=0; i<size; i++) { printf("%d\t", arr[i]); } return 0; }
Output:
Enter size of array: 9 Enter elements in array: 9 8 7 6 5 4 3 2 1 Elements of array in ascending order: 1 2 3 4 5 6 7 8 9
Important note: With a small change in the program you can change the logic for descending order.
Which means replace condition if(arr[i] > arr[j]) with if(arr[i] < arr[j])
to transform the logic for descending order.
Different Approach to see the iteration
Pseudocode
We observe in the algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in an ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.
To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.
Pseudocode of BubbleSort algorithm can be written as follows ?
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list
Program:
#include <stdio.h> #include <stdbool.h> #define MAX 10 int list[MAX] = {9,8,7,6,5,4,3,2,1,0}; void display() { int i; printf("["); // navigate through all items for(i = 0; i < MAX; i++) { printf("%d ",list[i]); } printf("]\n"); } void bubbleSort() { int temp; int i,j; bool swapped = false; // loop through all numbers for(i = 0; i < MAX-1; i++) { swapped = false; // loop through numbers falling ahead for(j = 0; j < MAX-1-i; j++) { printf(" Items compared: [ %d, %d ] ", list[j],list[j+1]); // check if next number is lesser than current no // swap the numbers. // (Bubble up the highest number) if(list[j] > list[j+1]) { temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; swapped = true; printf(" => swapped [%d, %d]\n",list[j],list[j+1]); }else { printf(" => not swapped\n"); } } // if no number was swapped that means // array is sorted now, break the loop. if(!swapped) { break; } printf("Iteration %d#: ",(i+1)); display(); } } main() { printf("Input Array: "); display(); printf("\n"); bubbleSort(); printf("\nOutput Array: "); display(); }
Output:
Input Array: [9 8 7 6 5 4 3 2 1 0 ]
Items compared: [ 9, 8 ] => swapped [8, 9]
Items compared: [ 9, 7 ] => swapped [7, 9]
Items compared: [ 9, 6 ] => swapped [6, 9]
Items compared: [ 9, 5 ] => swapped [5, 9]
Items compared: [ 9, 4 ] => swapped [4, 9]
Items compared: [ 9, 3 ] => swapped [3, 9]
Items compared: [ 9, 2 ] => swapped [2, 9]
Items compared: [ 9, 1 ] => swapped [1, 9]
Items compared: [ 9, 0 ] => swapped [0, 9]
Iteration 1#: [8 7 6 5 4 3 2 1 0 9 ]
Items compared: [ 8, 7 ] => swapped [7, 8]
Items compared: [ 8, 6 ] => swapped [6, 8]
Items compared: [ 8, 5 ] => swapped [5, 8]
Items compared: [ 8, 4 ] => swapped [4, 8]
Items compared: [ 8, 3 ] => swapped [3, 8]
Items compared: [ 8, 2 ] => swapped [2, 8]
Items compared: [ 8, 1 ] => swapped [1, 8]
Items compared: [ 8, 0 ] => swapped [0, 8]
Iteration 2#: [7 6 5 4 3 2 1 0 8 9 ]
Items compared: [ 7, 6 ] => swapped [6, 7]
Items compared: [ 7, 5 ] => swapped [5, 7]
Items compared: [ 7, 4 ] => swapped [4, 7]
Items compared: [ 7, 3 ] => swapped [3, 7]
Items compared: [ 7, 2 ] => swapped [2, 7]
Items compared: [ 7, 1 ] => swapped [1, 7]
Items compared: [ 7, 0 ] => swapped [0, 7]
Iteration 3#: [6 5 4 3 2 1 0 7 8 9 ]
Items compared: [ 6, 5 ] => swapped [5, 6]
Items compared: [ 6, 4 ] => swapped [4, 6]
Items compared: [ 6, 3 ] => swapped [3, 6]
Items compared: [ 6, 2 ] => swapped [2, 6]
Items compared: [ 6, 1 ] => swapped [1, 6]
Items compared: [ 6, 0 ] => swapped [0, 6]
Iteration 4#: [5 4 3 2 1 0 6 7 8 9 ]
Items compared: [ 5, 4 ] => swapped [4, 5]
Items compared: [ 5, 3 ] => swapped [3, 5]
Items compared: [ 5, 2 ] => swapped [2, 5]
Items compared: [ 5, 1 ] => swapped [1, 5]
Items compared: [ 5, 0 ] => swapped [0, 5]
Iteration 5#: [4 3 2 1 0 5 6 7 8 9 ]
Items compared: [ 4, 3 ] => swapped [3, 4]
Items compared: [ 4, 2 ] => swapped [2, 4]
Items compared: [ 4, 1 ] => swapped [1, 4]
Items compared: [ 4, 0 ] => swapped [0, 4]
Iteration 6#: [3 2 1 0 4 5 6 7 8 9 ]
Items compared: [ 3, 2 ] => swapped [2, 3]
Items compared: [ 3, 1 ] => swapped [1, 3]
Items compared: [ 3, 0 ] => swapped [0, 3]
Iteration 7#: [2 1 0 3 4 5 6 7 8 9 ]
Items compared: [ 2, 1 ] => swapped [1, 2]
Items compared: [ 2, 0 ] => swapped [0, 2]
Iteration 8#: [1 0 2 3 4 5 6 7 8 9 ]
Items compared: [ 1, 0 ] => swapped [0, 1]
Iteration 9#: [0 1 2 3 4 5 6 7 8 9 ]
Output Array: [0 1 2 3 4 5 6 7 8 9 ]
Press any key to continue . . .
C program to sort an array using pointers
Write a C program to input elements in an array and sort array using pointers. How to sort an array in ascending or descending order using function pointers in C programming. Logic to sort an array using pointers in program.
Logic to sort an array using pointers
Below is the step by step descriptive logic to sort an array using pointer.
- Input size and elements in array. Store them in some variable say
sizeandarr. - Declare two function with prototype
int sortAscending(int * num1, int * num2)andint sortDescending(int * num1, int * num2).Both the functions are used to compare two elements and arrange it in either ascending or descending order.
sortAscending()returns negative value ifnum1is less thannum2, positive value ifnum1is greater thannum2and zero if both are equal.Similarly,
sortDescending()returns negative value ifnum1is greater thannum2, positive value ifnum2is greater thannum1and zero if both are equal. - Declare another function to sort array with prototype
void sort(int * arr, int size, int (* compare)(int *, int *)).It takes three parameter, where first parameter is the array to sort, second is size of array and third is a function pointer.
Note: The function pointer passed here will decide relationship between two elements to be sorted. If you want to sort elements in ascending order then pass reference of
sortAscending()function, otherwisesortDescending()function.To sort an array I have used basic sorting algorithm. The algorithm is not efficient when compared to other modern sorting algorithms but its easy to understand and use.
Program:
/** * C program to sort an array using pointers. */ #include <stdio.h> #define MAX_SIZE 100 /* Function declaration */ void inputArray(int * arr, int size); void printArray(int * arr, int size); /* Sort function declaration */ int sortAscending(int * num1, int * num2); int sortDescending(int * num1, int * num2); void sort(int * arr, int size, int (* compare)(int *, int *)); int main() { int arr[MAX_SIZE]; int size; /* * Input array size and elements. */ printf("Enter array size: "); scanf("%d", &size); printf("Enter elements in array: "); inputArray(arr, size); printf("\n\nElements before sorting: "); printArray(arr, size); // Sort and print sorted array in ascending order. printf("\n\nArray in ascending order: "); sort(arr, size, sortAscending); printArray(arr, size); // Sort and print sorted array in descending order. printf("\nArray in descending order: "); sort(arr, size, sortDescending); printArray(arr, size); return 0; } /** * Function to take input in array elements. * * @arr Array to store input. * @size Size of the array. */ void inputArray(int * arr, int size) { // Pointer to last element of array int * arrEnd = (arr + size - 1); // (arr++) Input in current array element and move to next element. // Till last array element (arr <= arrEnd) while(arr <= arrEnd) scanf("%d", arr++); } /** * Function to print all array elements. * * @arr Array to print. * @size Size of the array. */ void printArray(int * arr, int size) { // Pointer to last element of array int * arrEnd = (arr + size - 1); // *(arr++) Print current array element and move to next element. // Till last array element (arr <= arrEnd) while(arr <= arrEnd) printf("%d, ", *(arr++)); } /** * Function to compare two succesive elements. * The function returns difference of first and second integer. * * @num1 First integer to compare. * @num2 Second integer to compare. * * @return Difference of num1 and num2. */ int sortAscending(int * num1, int * num2) { return (*num1) - (*num2); } /** * Function to compare two successive elements. * The function returns difference of second and first parameter. * * @num1 First integer to compare. * @num2 Second integer to compare. * * @return Difference of num2 and num1. */ int sortDescending(int * num1, int * num2) { return (*num2) - (*num1); } /** * Function to sort an array in ascending or descending order. * This function is used to sort array in both order ascending or * descending. * * @arr Array to sort. * @size Size of the array. * @compare Function pointer returning integer and takes two int * * parameter. The function is called to get arrangement of * two successive array elements. */ void sort(int * arr, int size, int (* compare)(int *, int *)) { // Pointer to last array element int * arrEnd = (arr + size - 1); // Pointer to current array element int * curElem = arr; int * elemToSort; // Iterate over each array element while(curElem <= arrEnd) { elemToSort = curElem; // Compare each successive elements with current element // for proper order. while(elemToSort <= arrEnd) { /* * Compare if elements are arranged in order * or not. If elements are not arranged in order * then swap them. */ if(compare(curElem, elemToSort) > 0) { *curElem ^= *elemToSort; *elemToSort ^= *curElem; *curElem ^= *elemToSort; } elemToSort++; } // Move current element to next element in array. curElem++; } }
In the above program instead of swapping elements normally, I have used bitwise XOR operator to swap two array elements.
Output:
Enter array size: 9 Enter elements in array: 9 8 7 6 5 4 3 2 1 Elements before sorting: 9, 8, 7, 6, 5, 4, 3, 2, 1, Array in ascending order: 1, 2, 3, 4, 5, 6, 7, 8, 9, Array in descending order: 9, 8, 7, 6, 5, 4, 3, 2, 1,
Bubble sort in C language using function
C programming code for bubble sort to sort numbers or arrange them in ascending order. You can modify it to print numbers in descending order.
Program:
#include <stdio.h> void bubble_sort(long [], long); int main() { long array[100], n, c, d, swap; printf("Enter number of elements\n"); scanf("%ld", &n); printf("Enter %ld integers\n", n); for (c = 0; c < n; c++) scanf("%ld", &array[c]); bubble_sort(array, n); printf("Sorted list in ascending order:\n"); for ( c = 0 ; c < n ; c++ ) printf("%ld\n", array[c]); return 0; } void bubble_sort(long list[], long n) { long c, d, t; for (c = 0 ; c < ( n - 1 ); c++) { for (d = 0 ; d < n - c - 1; d++) { if (list[d] > list[d+1]) { /* Swapping */ t = list[d]; list[d] = list[d+1]; list[d+1] = t; } } } }
Output:
Enter number of elements 9 Enter 9 integers 9 8 7 6 5 4 3 2 1 Sorted list in ascending order: 1 2 3 4 5 6 7 8 9 Press any key to continue . . .
You can also sort strings using Bubble sort, it is less efficient as its average and worst case complexity is high, there are many other fast sorting algorithms like quicksort, heapsort, etc. Sorting simplifies problem-solving in computer programming.
Bubble sort algorithm implementation in descending order using C Programming Language
Program:
#include <stdio.h> void bubble_sort(long [], long); int main() { long array[100], n, c, d, swap; printf("Enter number of elements\n"); scanf("%ld", &n); printf("Enter %ld integers\n", n); for (c = 0; c < n; c++) scanf("%ld", &array[c]); bubble_sort(array, n); printf("Sorted list in ascending order:\n"); for ( c = 0 ; c < n ; c++ ) printf("%ld\n", array[c]); return 0; } void bubble_sort(long list[], long n) { long c, d, t; for (c = 0 ; c < ( n - 1 ); c++) { for (d = 0 ; d < n - c - 1; d++) { if (list[d] < list[d+1]) { /* Swapping */ t = list[d]; list[d] = list[d+1]; list[d+1] = t; } } } }
Program:
Enter number of elements 9 Enter 9 integers 1 2 3 4 5 6 7 8 9 Sorted list in ascending order: 9 8 7 6 5 4 3 2 1 Press any key to continue . . .