Sorting Algorithm
Bubble Sort
Introduction
Sorting: Arranging values of an array in Ascending or Descending
order.
• E.g., 65, 34, 12, 7, 5, 2, 1 {Descending order}
• 3, 13, 23, 37, 49, 87 {Ascending order}
Bubble Sort
• Repeatedly stepping through the array to be sorted, comparing each pair
of adjacent items and swapping
• them if they are in the wrong order. The pass through the array is repeated
until no swaps are needed (which indicates that the list is sorted)
Algorithm
1. Start at the beginning of the array.
2. Compare the first two adjacent elements.
3. If the first element is greater than the second, swap them.
4. Move to the next pair of adjacent elements and repeat the
comparison and swap if necessary.
5. Continue this process for the entire array. After the first pass, the
largest element will be at the end of the array.
6. Repeat the process for the remaining elements (excluding the last
sorted elements) until no swaps are needed, indicating that the array
is sorted.
Introduction
Sorting takes an unordered collection and makes it an ordered one.
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
5 12 35 42 77 101
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
77 42 35 12 101 5
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42Swap
77 77
42 35 12 101 5
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42 35Swap35
77 77 12 101 5
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42 35 12Swap12
77 77 101 5
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42 35 12 77 101 5
No need to swap
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42 35 12 77 5 Swap101
101 5
"Bubbling Up" the Largest Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise comparisons and
swapping
1 2 3 4 5 6
42 35 12 77 5 101
Largest value correctly placed
Sorting in Ascending Order
Initialize the Random Array
#include <iostream>
#include <cstdlib> // For rand() and srand()
#include <ctime> // For time()
using namespace std;
const int SIZE = 10; // Size of the array
int numbers[SIZE];
// Seed the random number generator
srand(static_cast<unsigned int>(time(0)));
for (int i = 0; i < SIZE; ++i) {
numbers[i] = rand() % 100; // Assign a random number }
Sorting
for (int i = 0; i <= size - 1; ++i) {
bool swapped = false; //Flag to check if a swap occurred
for (int j = 0; j < size - i - 1; ++j) {
if (number[j] > number[j + 1]) {
temp=number[j]; 78
77 77
78
number[j] = number[j + 1];
temp=78
number[j + 1] = temp;
swapped = true; //Set the flag to true }}
//If no two elements were swapped in the inner loop, the array is sorted
if (!swapped) {
break; }}
Display Sorted Array
cout << "Sorted array: ";
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
Descending Order
• What if you want to Sort in descending Order?
• How will you manipulate the sorting for-loop?
if (arr[j] < arr[j + 1]) {
temp=arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; //Set the
flag to true
}
