[go: up one dir, main page]
Scribd
Upload
21 views4 pages

Bubble Sort

Uploaded by

ahmedthomas909
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
21 views4 pages

Bubble Sort

Uploaded by

ahmedthomas909
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

2024

Bubble Sort
SUPERVISOR: Eng/ Noor El-Deen Magdy

BY: Ahmed Mamdouh

Faculty of Engineering,
𝟐𝒏𝒅 Year Computer and Systems Department
Research on the Bubble Sort Algorithm:
Bubble sort works on the repeatedly swapping of adjacent
elements until they are not in the intended order. It is called
bubble sort because the movement of array elements is just
like the movement of air bubbles in the water. Bubbles in
water rise up to the surface; similarly, the array elements in
bubble sort move to the end in each iteration.
How Bubble Sort Works:
The algorithm works by repeatedly "bubbling" the largest unsorted element to
the correct position in each pass. Here’s a step-by-step breakdown:

1. Start from the first element of the list and compare it with the
next element.
2. If the current element is greater than the next, swap them.
3. Move to the next pair of elements and repeat the comparison
and swap process.
4. After each full pass through the list, the largest unsorted element
is placed at its correct position (the end of the list).
5. Repeat the process for the remaining unsorted elements,
ignoring the already sorted portion at the end of the list.
6. The algorithm stops when no more swaps are needed, indicating
the list is fully sorted.
Example:

Given the list: [5, 3, 8, 4, 2]


Pass 1:

 Compare 5 and 3: Swap → [3, 5, 8, 4, 2]


 Compare 5 and 8: No swap → [3, 5, 8, 4, 2]
 Compare 8 and 4: Swap → [3, 5, 4, 8, 2]
 Compare 8 and 2: Swap → [3, 5, 4, 2, 8]

After the first pass, 8 is in the correct position. Continue with the rest
of the list until fully sorted.
#include <iostream>
using namespace std;

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


for (int i = 0; i < n - 1; i++) {
// Last i elements are already sorted
for (int j = 0; j < n - i - 1; j++) {
// Compare adjacent elements
if (arr[j] > arr[j + 1]) {
// Swap if the element is greater than the next
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//////
#include <iostream>
using namespace std;

void optimizedBubbleSort(int arr[], int n) {


bool swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false; // Initialize swapped flag to false

// Perform the comparison and swapping as usual


for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap if the current element is greater than the next
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true; // Set swapped flag to true
}
}

// If no swaps occurred in this pass, the array is already sorted


if (!swapped) {
break;
}
}
}

The space complexity of optimized bubble sort is O(2). It is because


two extra variables are required in optimized bubble sort.

You might also like