Lecture: 13-14

Data Structures and Algorithm Analysis

Batch: 18CS, Semester: Second, Year: Second

Sorting Operations
(Sorting: Bubble Sort and Its Complexity)

Presented by: Dr. Sammer Zai

Assistant Professor
Department of Computer Systems, Mehran, UET.

1
 Fair Use Notice

The material used in this presentation i.e., pictures/graphs/text, etc.

is solely intended for educational/teaching purpose, offered free of
cost to the students for use under special circumstances of Online
Education due to COVID-19 Lockdown situation and may include
copyrighted material - the use of which may not have been
specifically authorized by Copyright Owners. It’s application
constitutes Fair Use of any such copyrighted material as provided in
globally accepted law of many countries. The contents of
presentations are intended only for the attendees of the class being
conducted by the presenter.
 Contents

• What is Sorting?
• Important Terms associated with Sorting
• Sorting Algorithms
• Bubble Sort
• Complexity of Bubble Sort

3
Sorting Operation
• Sorting refers to arranging data in a particular format. Sorting algorithm
specifies the way to arrange data in a particular order. Most common
orders are in numerical or lexicographical order.
• The importance of sorting lies in the fact that data searching can be
optimized to a very high level, if data is stored in a sorted manner. Sorting
is also used to represent data in more readable formats. Following are
some of the examples of sorting in real-life scenarios −
• Telephone Directory − The telephone directory stores the telephone
numbers of people sorted by their names, so that the names can be
searched easily.
• Dictionary − The dictionary stores words in an alphabetical order so that
searching of any word becomes easy.
4
In-place Sorting and Not-in-place Sorting
• Sorting algorithms may require some extra space for comparison and
temporary storage of few data elements. These algorithms do not
require any extra space and sorting is said to happen in-place, or for
example, within the array itself. This is called in-place sorting. Bubble
sort is an example of in-place sorting.
• However, in some sorting algorithms, the program requires space
which is more than or equal to the elements being sorted. Sorting
which uses equal or more space is called not-in-place sorting. Merge-
sort is an example of not-in-place sorting.

5
Internal and External Sorting
• In internal sorting all the data to sort is stored in memory at all times
while sorting is in progress.
• Some common internal sorting algorithms include: Bubble Sort.
• In external sorting data is stored outside memory (like on disk) and only
loaded into memory in small chunks.
• External sorting is usually applied in cases when data can't fit into
memory entirely.
• While sorting the data will pulled over in chunks from disk to main
memory. Later all the sorted data will be merged and stored back to
disk, where it can fit. External merge sort can be used here
• One example of external sorting is the external merge sort algorithm,
which sorts chunks that each fit in RAM, then merges the sorted
chunks together.
6
Important Terms
• Some terms are generally coined while discussing sorting techniques,
here is a brief introduction to them −
• Increasing Order: A sequence of values is said to be in increasing
order, if the successive element is greater than the previous one. For
example, 1, 3, 4, 6, 8, 9 are in increasing order, as every next element
is greater than the previous element.
• Decreasing Order: A sequence of values is said to be in decreasing
order, if the successive element is less than the current one. For
example, 9, 8, 6, 4, 3, 1 are in decreasing order, as every next element
is less than the previous element.

7
Important Terms
• Non-Increasing Order: A sequence of values is said to be in non-increasing
order, if the successive element is less than or equal to its previous
element in the sequence. This order occurs when the sequence contains
duplicate values. For example, 9, 8, 6, 3, 3, 1 are in non-increasing order, as
every next element is less than or equal to (in case of 3) but not greater
than any previous element.
• Non-Decreasing Order: A sequence of values is said to be in non-
decreasing order, if the successive element is greater than or equal to its
previous element in the sequence. This order occurs when the sequence
contains duplicate values. For example, 1, 3, 3, 6, 8, 9 are in non-decreasing
order, as every next element is greater than or equal to (in case of 3) but
not less than the previous one.

8
Bubble Sort
• Bubble sort is a simple sorting algorithm.
• This sorting algorithm is comparison-based algorithm in which each
pair of adjacent elements is compared and the elements are swapped
if they are not in order.
• This algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2) where n is the number of items.
• It is known as bubble sort, because with every complete iteration the
largest element in the given array, bubbles up towards the last place
or the highest index, just like a water bubble rises up to the water
surface.
9
How Bubble Sort Works?
• We take an unsorted array for our example. Bubble sort takes Ο(n2)
time so we're keeping it short and precise.

• Bubble sort starts with very first two elements, comparing them to
check which one is greater.

• In this case, value 33 is greater than 14, so it is already in sorted

locations. Next, we compare 33 with 27.

10
How Bubble Sort Works?
• We find that 27 is smaller than 33 and these two values must be
swapped.

• The new array should look like this −

• Next we compare 33 and 35. We find that both are in already sorted
positions.

11
How Bubble Sort Works?
• Then we move to the next two values, 35 and 10.

• We know then that 10 is smaller 35. Hence they are not sorted.

• We swap these values. We find that we have reached the end of the
array. After one iteration, the array should look like this −

12
How Bubble Sort Works?
• To be precise, we are now showing how an array should look like after
each iteration. After the second iteration, it should look like this −

• Notice that after each iteration, at least one value moves at the end.

13
How Bubble Sort Works?
• And when there's no swap required, bubble sorts learns that an array
is completely sorted.

14
Algorithm for Bubble Sort

15
 16

Complexity Analysis of Bubble Sort

• In Bubble Sort, n-1 comparisons

will be done in the 1st pass, n-2 in
2nd pass, n-3 in 3rd pass and so
on. So the total number of
comparisons will be,
Complexity Analysis of Bubble Sort
• Hence the time complexity of Bubble Sort is O(n2).
• The main advantage of Bubble Sort is the simplicity of the algorithm.
• The space complexity for Bubble Sort is O(1), because only a single additional
memory space is required i.e. for temp variable.
• Also, the best case time complexity will be O(n), it is when the list is already
sorted.
• Following are the Time and Space complexity for the Bubble Sort algorithm.
• Worst Case Time Complexity [ Big-O ]: O(n2)
• Best Case Time Complexity [Big-omega]: O(n)
• Average Time Complexity [Big-theta]: O(n2)
• Space Complexity: O(1)
17
• O(n) is the best-case running time for bubble sort. It is possible to
modify bubble sort to keep track of the number of swaps it performs.
If an array is already in sorted order, and bubble sort makes no swaps,
the algorithm can terminate after one pass. With this modification, if
bubble sort encounters a list that is already sorted, it will finish
in O(n)O(n) time.

18
Exercise Problem

19
Task-1
1. Use Bubble Sort algorithm to sort the following elements stored in
an array DATA[]. Show step-by-step procedure for each of the following
arrays and also find the total number of passes, comparisons and
interchanges.
i. DATA[]=PEOPLE
ii. DATA[]= 5,1,6,2,4,3
iii. DATA[]= 14,33,27, 35,10
iv. DATA[]= 32,51,27,85,66,23,13,57

20
Task-2
• Implement bubble sort algorithm using C++ language (or java).

21