Scribd
Upload
12 views5 pages

Bubble Sort Algorithm in C: Analysis and Code

The document summarizes the bubble sort algorithm in 3 sentences or less. It begins with an introduction to bubble sort, describing it as a simple sorting algorithm that works by repeatedly swapping adjacent elements. It then provides the steps of the bubble sort algorithm. Finally, it analyzes the time and space complexity of bubble sort, noting it has a worst-case time complexity of O(n2) but requires no extra space, and maintains the relative order of items with equal keys.

Uploaded by

Thomas Shelby
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
12 views5 pages

Bubble Sort Algorithm in C: Analysis and Code

The document summarizes the bubble sort algorithm in 3 sentences or less. It begins with an introduction to bubble sort, describing it as a simple sorting algorithm that works by repeatedly swapping adjacent elements. It then provides the steps of the bubble sort algorithm. Finally, it analyzes the time and space complexity of bubble sort, noting it has a worst-case time complexity of O(n2) but requires no extra space, and maintains the relative order of items with equal keys.

Uploaded by

Thomas Shelby
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

TECHNO INTERNATIONAL NEW TOWN

Department of Computer Science and Engineering


Block DG, Action Area 1, New Town, Kolkata-700156, West Bengal, India

Design and Analysis of Algorithms (PCC-CS404)

TECHNICAL REPORT
ON BUBBLE SORT FOR #CA2 EXAMINATION

Name: DRIPTANIL DATTA


Section: CSE-A
Semester: 4th (2nd YEAR)
Roll No: 18700121168
Date of Submission: 05.03.2023

Page 1 of 5
Topic: Bubble Sort

Content

Topics Page No

Introduction 3
Algorithm 3
Performance Analysis 3
Code/Function in C 4
Example 5
Conclusion 5
References 5

Introduction:
Bubble sort is a simple and popular sorting algorithm that is used to sort arrays or lists of
elements. It is a comparison-based sorting algorithm that works by repeatedly swapping
adjacent elements if they are in the wrong order. Bubble sort is easy to understand and
implement, but it could be more efficient for large data sets.

Page 2 of 5
Algorithm:
The algorithm for selection sort can be described as follows:
Step-1: Start with the first element in the array or list.
Step-2: Compare the current element with the next element.
Step-3: If the current element exceeds the next element, swap them.
Step-4: Move to the next pair of elements and repeat steps 2 and 3.
Step-5: Continue until the end of the array or list is reached.
Step-6: If any swaps were made during the previous pass, repeat step 1.

Perfomance Analysis:

Best Time Complexity O(𝑛) the given array is already


sorted

Worst Time Complexity O(𝑛 )


2 the given array is reverse

Average Time Σ
𝑛
(𝑛 − 𝑘) the average of the best and
𝑘= 1
Complexity worst case
𝑛 (𝑛−1) 2
= 2
≈ O(𝑛 )

Space Complexity O(1) auxiliary space is zero / no


Inplace Sorting extra space

Stability Yes maintains the relative order of


the items with equal sort keys

Page 3 of 5
Code / Function in C:

void swap(int *a, int *b){


int temp = *a;
*a = *b;
*b = temp;
}
void BubbleSort(int arr[], int size){
for(int i = 0; i < size; i++){
int sorted = 1;
for(int j = 0;j<size-i-1;j++){
if(arr[j]>arr[j+1]){
sorted = 0;
swap(&arr[j],&arr[j+1]);
}
}
if (sorted) {
return;
}
}
}

Example with Diagram:

Page 4 of 5
Sorting a array containing element [3, 1, 5, 4, 2] using bubble sort algorithm,

Comparing

Swapping

CONCLUSION:
In conclusion, bubble sort is a simple and popular sorting algorithm that works by repeatedly
swapping adjacent elements if they are in the wrong order. While it is easy to understand and
implement, it could be more efficient for large data sets. However, it is a good choice for
small data sets or when simplicity is more important than efficiency.

REFERENCES:
1. Introduction to Algorithms, 4TH Edition, Thomas H Cormen, Charles E Lieserson,
Ronald L Rivest and Clifford Stein, MIT Press/McGraw-Hill.
2. Algorithms Design and Analysis, Udit Agarwal, Dhanpat Rai
3. Bubble Sort (With Code in Python/C++/Java/C)
4. [Link]
rt
5. Bubble Sort Algorithm - Theory + Code

Page 5 of 5

You might also like