Bubble Sort

One of the simplest sorting algorithms is the Bubble Sort. It works by repeatedly swapping adjacent elements if they are in the wrong order. The algorithm continues to iterate through the array until no more swaps are needed, indicating that the array is sorted.

Here's an example of implementing Bubble Sort in C++:

1#include <iostream>
2#include <algorithm>
3using namespace std;
4
5void printArray(int arr[], int size) {
6  for (int i = 0; i < size; i++) {
7    cout << arr[i] << " ";
8  }
9  cout << endl;
10}
11
12void bubbleSort(int arr[], int size) {
13  for (int i = 0; i < size - 1; i++) {
14    for (int j = 0; j < size - i - 1; j++) {
15      if (arr[j] > arr[j + 1]) {
16        swap(arr[j], arr[j + 1]);
17      }
18    }
19  }
20}
21
22int main() {
23  int arr[] = {5, 2, 8, 12, 1};
24  int size = sizeof(arr) / sizeof(arr[0]);
25
26  cout << "Original array: " << endl;
27  printArray(arr, size);
28
29  bubbleSort(arr, size);
30
31  cout << "Sorted array: " << endl;
32  printArray(arr, size);
33
34  return 0;
35}

In the code snippet above, we have an array arr filled with integer values. We then define a function printArray to print the elements of an array, and another function bubbleSort to implement Bubble Sort.

The bubbleSort function consists of two nested loops that iterate through the array. On each iteration, adjacent elements are compared, and if they are in the wrong order, they are swapped. This process continues until the entire array is sorted.

Let's take a closer look at the steps the Bubble Sort algorithm takes to sort the array {5, 2, 8, 12, 1}:

• Step 1: Compare 5 and 2. Since 5 is greater than 2, swap the two elements: {2, 5, 8, 12, 1}.
• Step 2: Compare 5 and 8. Since 5 is not greater than 8, no swap is needed.
• Step 3: Compare 8 and 12. Since 8 is not greater than 12, no swap is needed.
• Step 4: Compare 12 and 1. Since 12 is greater than 1, swap the two elements: {2, 5, 8, 1, 12}.

After the first iteration, the largest element 12 is in its correct position at the end of the array. The process then repeats for the remaining elements until the entire array is sorted.

Bubble Sort has a worst-case and average time complexity of O(n^2), where n is the number of elements in the array. Although simple to implement, Bubble Sort is not suitable for large arrays or performance-critical applications as its time complexity makes it inefficient.

There are more efficient sorting algorithms available, such as Quick Sort, Merge Sort, and Heap Sort, which we will explore in upcoming screens.

xxxxxxxxxx

}

#include <iostream>

#include <algorithm>

using namespace std;

​

void printArray(int arr[], int size) {

  for (int i = 0; i < size; i++) {

    cout << arr[i] << " ";

  }

  cout << endl;

}

​

void bubbleSort(int arr[], int size) {

  for (int i = 0; i < size - 1; i++) {

    for (int j = 0; j < size - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {

        swap(arr[j], arr[j + 1]);

      }

    }

  }

}

​

int main() {

  int arr[] = {5, 2, 8, 12, 1};

  int size = sizeof(arr) / sizeof(arr[0]);

​

  cout << "Original array: " << endl;

  printArray(arr, size);

​

  bubbleSort(arr, size);