solutions/The Last Algorithms Course You'll Need/6. Bubble Sort.c

#include <stdio.h>

#define SIZE 10 

// complexity is O(n^2)
// how is that calculated?
// well we run two loops, even if the first one is N
// the second one is first N, then N - 1, then N - 2, ...
// all the way down to N - N + 1
// what's the sum of them? 
// imagine sum of all form 1 to 100
// okay, 1 + 100 = 101
// okay, 2 + 99 = 101
// etc all the way down to 50 and 51,
// so we have 50 times 101 to calculate sum of 1 to 100
// which means:
// 101 * 50    or
// (N+1) * N/2   or
// N^2 + N    which makes
// O(N^2 + N)   then we drop the non-significant + N
// O(N^2)

void bubble_sort(int array[], int size)
{
	for (int i = 0; i < size; ++i)
	{
		for (int j = 1; j < size - i; ++j)
		{
			if (array[j] < array[j-1])
			{
				int temp = array[j];
				array[j] = array[j-1];
				array[j-1] = temp;
			}
		}
	}
}

int main()
{
	int array[SIZE] = { 5, 7, 3, 2, 11, 16, 1, 4, 3, 2 };
	bubble_sort(array, SIZE);
	for (int i = 0; i < SIZE; ++i)
		printf("%d ", array[i]);
	printf("\n");
}