mirror of https://github.com/TheAlgorithms/C
88 lines
2.0 KiB
C
88 lines
2.0 KiB
C
/**
|
|
* @file
|
|
* @brief implementation of [Bubble sort](https://en.wikipedia.org/wiki/Bubble_sort) algorithm
|
|
* @details
|
|
* worst-case: O(n^2)
|
|
* best-case: O(n)
|
|
* average-complexity: O(n^2)
|
|
|
|
* @author Unknown author
|
|
* @author [Gabriel Fioravante](https://github.com/northernSage)
|
|
*/
|
|
|
|
#include <stdlib.h> /// for rand() calls
|
|
#include <assert.h> /// for assert(<expr>)
|
|
#include <stdbool.h> /// for boolean values: true, false
|
|
|
|
#define MAX 20
|
|
|
|
/**
|
|
* @brief Bubble sort implementation
|
|
* @param array_sort the array to be sorted
|
|
* @returns void
|
|
*/
|
|
void bubble_sort(int* array_sort)
|
|
{
|
|
bool is_sorted = false;
|
|
|
|
/* keep iterating over entire array
|
|
* and swaping elements out of order
|
|
* until it is sorted */
|
|
while (!is_sorted)
|
|
{
|
|
is_sorted = true;
|
|
|
|
/* iterate over all elements */
|
|
for (int i = 0; i < MAX - 1; i++)
|
|
{
|
|
/* check if adjacent elements are out of order */
|
|
if (array_sort[i] > array_sort[i + 1])
|
|
{
|
|
/* swap elements */
|
|
int change_place = array_sort[i];
|
|
array_sort[i] = array_sort[i + 1];
|
|
array_sort[i + 1] = change_place;
|
|
/* elements out of order were found
|
|
* so we reset the flag to keep ordering
|
|
* until no swap operations are executed */
|
|
is_sorted = false;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief Test implementations
|
|
* @returns void
|
|
*/
|
|
static void test() {
|
|
/* simple int array for testing */
|
|
int array_sort[MAX] = {0};
|
|
|
|
/* populate our test array with
|
|
* random integer numbers */
|
|
for (int i = 0; i < MAX; i++)
|
|
{
|
|
array_sort[i] = rand() % 101;
|
|
}
|
|
|
|
/* sort array */
|
|
bubble_sort(array_sort);
|
|
|
|
/* check if array ir correctly ordered */
|
|
for (int i = 0; i < MAX - 1; i++)
|
|
{
|
|
assert(array_sort[i] <= array_sort[i+1]);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* @brief Main function
|
|
* @returns 0 on exit
|
|
*/
|
|
int main()
|
|
{
|
|
test(); // run self-test implementations
|
|
return 0;
|
|
}
|