### Bubble Sort in C and Python

This blog is just going to be filled with programming/algorithm examples, which are sometimes thorough, and sometimes not.

Here's an example of bubble sort in Python (probably easier to understand than C).
#! /usr/bin/env python3.4
# -*- coding: utf-8 -*-

""" A quick implementation of Bubble Sort """

from random import randint
from array import array
from typing import Iterable
from types import FunctionType

def checkReturnArray(f: FunctionType) -> bool:
""" Decorator to ensure array has been sorted """
def new_f(*args, **kwds) -> bool:
res = f(*args, **kwds)
for i in range(len(res) - 1):
if (res[i] < res[i + 1]):
return False
else:
return True
return new_f

@checkReturnArray
def bubbleSort(arr: array =array('I', )) -> Iterable[int]:
""" O(N^2) time complexity """
arrLength = len(arr)

for i in range(arrLength):
for j in range(i):
if (arr[i] > arr[j]):
# swap
arr[i] ^= arr[j]
arr[j] ^= arr[i]
arr[i] ^= arr[j]

return arr

def main(LENGTH: int =100, MOD: int =100):
X = array('I', [])
for _ in range(LENGTH):
X.append(randint(0, MOD))

if (bubbleSort(X)):
print("X sorted successfully")
else:
print("X not sorted successfully")

if __name__ == '__main__':
main()


I used the decorator checkOutputWrapper to check the return array to make sure that the algorithm is working correctly. Also, the three lines with an XOR operation swap array values in-place, so there's no need for a temporary variable. I have CPython installed on my machine, so in the shebang line I've written the specific version of Python 3 I want to run it with (simply make it executable, i. e. chmod +111 bubbleSort.py)

Now, the same algorithm in C.
/* A simple bubble sort example in C */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <stdint.h>

#define LENGTH 100
#define MOD    100

void
bubbleSort(uint16_t * arr)
{
uint16_t i, j;

for (i = 0; i < LENGTH; ++i)
{
for (j = 0; j < i; ++j)
{
if (arr[i] > arr[j]) {
arr[i] ^= arr[j] ^= arr[i] ^= arr[j];
}
}
}
}

int
check(uint16_t * arr)
{
uint16_t i;

for (i = 0; i < LENGTH - 1; ++i)
{
if (arr[i] < arr[i + 1])
return 0;
}
return 1;
}

int
main(void)
{
srand(time(NULL));
uint16_t i, * arr;

// create array to store random integers
arr = (uint16_t *)malloc((uint16_t)LENGTH * sizeof(uint16_t));

// populate arr with random integers
for (i = 0; i < LENGTH; ++i)
arr[i] = rand() % MOD;

// sort in-place
bubbleSort(arr);

// check to make sure the array is sorted
if (check(arr)) {
printf("arr sorted correctly\n");
} else {
printf("arr not sorted correctly\n");
}

free(arr);

return 0;
}


It's pretty straightforward I think. The time complexity is $$\mathcal{O}\left(N^2\right)$$.