Bubble Sort

On bubble sort, we start the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuous making sweeps of the array until it is sorted.
In doing so, the smallest items slowly bubble up to the begin list.

C implementation

void swap (int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void BubbleSwap(int* array, size_t size) {
	while (size > 1) {
		size --;
		for (int i = 0; i < size; i++) {
			int *a = &array[i];
			int *b = &array[i+1];
			if (*a < *b) {
				swap(a, b);
			}
		}
	}
}

A C++ implementation

void swap(int & a, int & b) {
	int temp = a;
	a = b;
	b = a;
}

void BubbleSwap(vector<int> &arr) {
	int size = arr.size();
	while (size > 1) {
		size--;
		for (int i = 0; i < size; i++) {
			if (arr[i] > arr[i+1]) {
				swap(arr[i], arr[i+1]);
			}
		}
	}
}

Summary

• Time Complexity: $O(N^2)$
• Space Complexity: $O(1)$