Bubble sort in C
Bubble sort in C
Bubble sort is defined as the algorithm that is used for the sorting mechanism. It follows the technique of replacing the first index with the more minor value present within the array and then keeps it repeating until it is sorted in the correct order.
Bubble sort is the simple way of performing the sorting technique. The value of the array has to be assigned to the array first before starting the sorting.
Data sorting is considered to be an essential concept. During the times when the data needs to be arranged in a particular order or in an organized way, sorting techniques are used. Bubble sort is considered the most straightforward sorting technique among the ones present in the C standard as it is very easy to implement and understand.
It follows the approach of comparing the current element with the preceding one and then swaps it accordingly if required, such as if it is less or more significant. This gives accurate results no matter what. Every time an element is passed into an array, it will be compared with all the elements present within the array, and then it decides a final place to that inserted element and is called a pass.
Bubble sort gets the name as it filters out the elements of the top of the array, similar to the bubbles on the water. Although this algorithm is the slowest, it runs with O’s time complexity (n^2).
A bubble sort might be optimized by using the variable called to flag that exists the loop once, and then the swapping can be initiated. The best complexity of the bubble sort can be O(n).
Bubble sort algorithm:
- Starting from the index zero in an array, compare the element with the preceding one (a[0] and a[1] considering the name of the array as a) compare both the elements and swap if a[1] > a[2]. Repeat this process until the end of the array. After doing so, the most significant element will be placed as the end of the array. The whole thing is considered as a pass. The array elements will be processed in the first pass in the first pass [0, n - 1].
- Repeat the previous step but instead consider the elements from [0, n - 2] as the last one, that is, a[n - 1] is present at its correct position. After this particular step, the largest of the two elements will be compared and will be swapped.
- Repeat the same steps for n - 1 number of times.
E.g.:
#include <stdio.h>
int main()
{
int total_count, counter, counter1, swap_var;
int array[20];
printf("How many numbers do you want to input?\n");
scanf("%d", &total_count);
printf("Please enter %d integers that have to be sorted\n", total_count);
for (counter = 0; counter < total_count; counter++)
scanf("%d", &array[counter]);
for (counter = 0 ; counter < total_count - 1; counter++)
{
for (counter1 = 0 ; counter1 < total_count - counter - 1; counter1++)
{
if (array[counter1] > array[counter1+1]) /* For decreasing order use < */
{
swap_var = array[counter1];
array[counter1] = array[counter1+1];
array[counter1+1] = swap_var;
}
}
}
printf("Below is the list of elements sorted in ascending order:\n");
for (counter = 0; counter < total_count; counter++)
printf("%d\n", array[counter]);
return 0;
}
Output:
How many numbers do you want to input? 4 Please enter 4 integers that have to be sorted 4 2 5 1 Below is the list of elements sorted in ascending order: 1 2 4 5
Once the above program is compiled and run, it will further ask the programmer or the developer for the number of elements that they want to sort.
Once it is provided, the program will ask the user to provide values equivalent to their provided count. The values will be stored in the array and processed further using nested for loop together with decision-making using “if” to sort the array.
The first smallest value found in the array has been moved to the array’s first index, and then the search begins again to find the other smallest number.
Once the following smallest number is found, it replaces the value in the second index, and the process keeps on repeating until the array consists of a sorted list of values.
Complexities:
- Worst case time complexity: O(n^2). If we want to sort, the array is ascending order, and the given array is in descending series.
- Best case time complexity: O(n). if the array is already sorted in the beginning and there is no necessity of sorting.
- Average case time complexity: O(n^2). This occurs when the element of the array occurs in the chaotic order.
Space complexity:
- Space complexity is always O(1) as an extra variable is used for swapping
- In an optimized bubble sort algorithm, an extra two of the variables will be used. Hence the space complexity will be O(2).
Applications:
- Bubble sort can be used if the complexity does not matter
- If the array is short and readable.