TOPIC: Bubble Sort

DEFINITION: 
Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted, solving the problem of arranging elements in ascending or descending order. It works by iteratively "bubbling" the largest or smallest element to the end or beginning of the list.

TIME_COMPLEXITY: 
The time complexity of bubble sort is O(n) in the best case, O(n^2) on average, and O(n^2) in the worst case, because in the best case the list is already sorted and only one pass is needed, while in the average and worst cases, the algorithm needs to make multiple passes through the list to sort it.

SPACE_COMPLEXITY: 
The space complexity of bubble sort is O(1), because it only uses a constant amount of additional space to store temporary swaps, and does not require any extra space that scales with the size of the input list.

USE_WHEN: 
Bubble sort can be useful when the list is small or nearly sorted, as it has a simple implementation and can be efficient in these cases. It can also be a good teaching tool for introducing the concept of sorting algorithms.

AVOID_WHEN: 
Bubble sort is a poor choice for large lists or lists that are in reverse order, as its average and worst-case time complexities are high, and other algorithms like quicksort or mergesort are generally more efficient and should be used instead.

EXAMPLE: 
Suppose we have the list [5, 2, 8, 3, 1] and we want to sort it in ascending order using bubble sort. 
  Initial list: [5, 2, 8, 3, 1]
  Compare 5 and 2, swap: [2, 5, 8, 3, 1]
  Compare 5 and 8, no swap: [2, 5, 8, 3, 1]
  Compare 8 and 3, swap: [2, 5, 3, 8, 1]
  Compare 8 and 1, swap: [2, 5, 3, 1, 8]
  Repeat the process until the list is sorted: 
    [2, 5, 3, 1, 8] -> [2, 3, 5, 1, 8] -> [2, 3, 1, 5, 8] -> [2, 1, 3, 5, 8] -> [1, 2, 3, 5, 8]
  Final sorted list: [1, 2, 3, 5, 8] 

REAL_WORLD_ANALOGY: 
Bubble sort is similar to rearranging a set of books on a shelf, where you compare each book to the one next to it and swap them if they are in the wrong order, repeating the process until the books are in the correct order.

SOURCE_NOTE: 
Concepts referenced from general knowledge of sorting algorithms and data structures.