Bubble Sort

With this algorithm, you go through the array checking if each value is bigger than the one after it and you propagate/"bubble" the bigger item up the array (towards the end) by swapping it with the item next to it. Going through the array/list once constitutes as one pass. You will make as many passes as needed until the array is sorted(no swapping has taken place on the last pass).
Best Case: O(n), everything already sorted. You take one pass to figure that out.
Worst case running time: O(n^2).
In place: Yes.

Code:

swap = false;

do {
swap = false;
for (i = 0; i < size -1; i ++) { //you want to stop at the one before last since you're comparing the next item

if (arr[i] > arr[i+1]) {
swap (arr[i], arr[i+1]);
swap = true;
}

} while(swap)


What you will realize is that with the first pass, you're placing the biggest element at the end of the array (fixed in its correct place). 2nd pass: 2nd biggest element, etc. So you don't really need to iterate through the whole array every time, but arr.size - the pass you are on (since the items will be fixed in place).

swap = false;
int index = arr.size;

do {
swap = false;
for (i = 0; i < index -1; i ++) { //you want to stop at the one before last since you're comparing the next item

if (arr[i] > arr[i+1]) {
swap (arr[i], arr[i+1]);
swap = true;
}

index--;

} while(swap)



You will realize that for every element that is not in its place(off by 1), you will need 1 full pass to fix it it + final pass to go through the array and make sure everything is good.
1 swap to get arr ordered = 2 passes
2 swaps to get arr ordered = 3 passes
n = n+1 passes

To keep it easy, we will define 1 pass to mean you've visited all the elements (n). In reality its more like n-i, with i being pass count because as you put items in place you don't need to traverse to that point in the array. So if you know an array is almost sorted, say 4 elements are out of place/4 swaps are needed for the array to be sorted, then Big O is O(5n). Might be better than some other algorithms.

So worst case, the element is very off (at the other end of the array), you will need n+1 passes to fix it, and each pass you're examining n items. Thus, O(n^2).