A bubble sort is generally considered the simplest type of sorting algorithm and works by swapping adjacent elements in an array (or linked lists) until the largest element is at the end of the array, the largest element is then considered sorted and you start again from the left (beginning or array) and swap elements to the right until you find the second largest item. With enough passes you will eventually have a sorted array at the end of it.

(Insert diagrams here)

Implementation

This is an implementation in C# the most important part of which is the bubble sort algorithm itself, that is comprised of a nested for loops that check the two adjacent elements in the array and swaps them if the first term is larger.

It then repeats this process for all unsorted term (a bubble sort pass) until it reaches the end of the array and another element has been sorted. The outer loop repeats the bubble sort pass until the array is populated with sorted elements.

static void PerformBubbleSort(int[] array)
{
	int n = array.Length;
	
	//Repeat the bubble sort pass
	for (int i = 0; i < (n - 1); i++)
	{
		//One bubble sort pass
		for (int j = 0; j < (n - i - 1); j++)
		{
			//Check adjacent terms
			if (array[j] > array[j + 1])
			{
				// Swap temporary and array[i]
				int temporary = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temporary;
			}
		}
	}
}

Time Complexity

It terms of time complexity, it has an efficient best case scenario of $\mathrm{\Omega }(n)$, but is not suitable for large data sets as its average and worst case time complexity are $\mathrm{\Theta }(n^2)$ and $O(n^2)$ respectively.

Appendix

Full Implementation

using System;

class BubbleSort
{
    static void Main(string[] args)
    {
	    //Our unsorted array
        int[] array = {64, 34, 25, 12, 22, 11, 90};
        Console.WriteLine("Original array: ");
        PrintArray(array);
        
        PerformBubbleSort(array);
        Console.WriteLine("\\nSorted array: ");
        PrintArray(array);
    }
    
	static void PerformBubbleSort(int[] array)
	{
		int n = array.Length;
		
		for (int i = 0; i < (n - 1); i++)
		{
			for (int j = 0; j < (n - i - 1); j++)
			{
				if (array[j] > array[j + 1])
				{
					// Swap temporary and array[i]
					int temporary = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temporary;
				}
			}
		}
	}
	
    static void PrintArray(int[] array)
    {
        foreach (int element in array)
        {
            Console.Write(element + " ");
        }
        Console.WriteLine();
    }
}

Original array: 64 34 25 12 22 11 90

Sorted array: 11 12 22 25 34 64 90