[go: up one dir, main page]
Scribd
Upload
41 views11 pages

Bubble Sort Algorithm (Future Uni)

This document discusses bubble sort, a simple sorting algorithm. Bubble sort works by repeatedly comparing adjacent elements in an array and swapping them if they are in the wrong order. It has a time complexity of O(n^2) in the average and worst cases, making it inefficient for large data sets. While simple to implement, other algorithms like quicksort and mergesort should be used for large arrays. The document provides an example of bubble sort, discusses its pros and cons, and emphasizes the key takeaways.

Uploaded by

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

Bubble Sort Algorithm (Future Uni)

This document discusses bubble sort, a simple sorting algorithm. Bubble sort works by repeatedly comparing adjacent elements in an array and swapping them if they are in the wrong order. It has a time complexity of O(n^2) in the average and worst cases, making it inefficient for large data sets. While simple to implement, other algorithms like quicksort and mergesort should be used for large arrays. The document provides an example of bubble sort, discusses its pros and cons, and emphasizes the key takeaways.

Uploaded by

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

Data Structures

and Algorithms Course


SORTING
ALGORITHMS

BUBBLE SORT
Outline
 What is sorting?

 Why do we need sorting?

 Bubble sort algorithm

 Example of bubble sort

 Time complexity of bubble sort

 Pros and cons

 The key takeaways


2
Motivation of Sorting
 Sorting refers to arranging data in some order.
 Why do we need Sorting???
1. Data searching can be more optimized if data is well-sorted.
• For example, List of alphabets
o P A K I S T A N (Unsorted list)
o A A I K N P S T (Sorted list, ascending)

2. Sorting is also used to represent data in more readable formats.


• For example, List of numbers
o 10 20 50 30 40 60 25 (Unsorted list)
o 10 20 25 30 40 50 60 (Sorted list, ascending)
o 60 50 40 30 25 20 10 (Sorted list, descending)

3
Sorting Algorithms
1. Bubble Sort

2. Selection Sort

3. Insertion Sort

4. Quick Sort

5. Merge Sort
4
Bubble Sort Algorithm
 Bubble Sort is the simplest sorting algorithm.

 It works by repeatedly swapping the two adjacent elements if


they are in the wrong order.
o If elements are not in the required order, swap them
(change their position)
o Otherwise do nothing

5
Bubble Sort Example

6
Example (cont.)

 The algorithm continues to iterate, comparing and swapping


adjacent elements until the end of the array is reached.
 After the last iteration, the algorithm is sorted in ascending
order, which is: [3, 4, 5, 6, 8]
7
Your Turn
 Trace the operation of bubble sort on the following list, show
all steps in detail:
4, 7, 2, 5, 6, 1
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
------------------------------------------------------------------------
---------------- 8
Bubble Sort Time Complexity
Best-Case Worst-
Case

Passes O(1) O(n)


Comparisons O(n) O(n)
Total O(n) O(n2)
Linear
Quadratic

9
Pros and Cons
 Pros:
1. It is very simple to learn.
2. Easy to implement.

 Cons:
1. This algorithm is not suitable for large data sets.
2. Its average and worst case complexity are of Ο(n2) where n is the
number of items.

10
The key takeaways
 Bubble sorting is a simple sorting algorithm that works by
repeatedly comparing adjacent elements in an array and
swapping them if they are in the wrong order.

 The time complexity of bubble sorting is O(n2) in the worst-


case and average-case scenarios. This means that the bubble
sort algorithm will become very slow for large arrays.

 If you need to sort a large array, you should use a different


sorting algorithm, such as quick sort or merge sort.

11

You might also like