0% found this document useful (0 votes)
58 views20 pages

Lecture 1.2.4

The document discusses sorting algorithms. It introduces bubble sort, insertion sort, and selection sort. For each algorithm, it provides an overview of how it works and its time and space complexity. Bubble sort compares adjacent elements and swaps them if out of order. Insertion sort builds a sorted array by inserting elements one by one. Selection sort divides the array into sorted and unsorted parts and selects the smallest element to move to the sorted part. All three algorithms have a time complexity of O(n2) for average and worst cases.

Uploaded by

Ravesh Rawal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
58 views20 pages

Lecture 1.2.4

The document discusses sorting algorithms. It introduces bubble sort, insertion sort, and selection sort. For each algorithm, it provides an overview of how it works and its time and space complexity. Bubble sort compares adjacent elements and swaps them if out of order. Insertion sort builds a sorted array by inserting elements one by one. Selection sort divides the array into sorted and unsorted parts and selects the smallest element to move to the sorted part. All three algorithms have a time complexity of O(n2) for average and worst cases.

Uploaded by

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

UNIVERSITY INSTITUTE OF

ENGINEERING
DEPARTMENT OF COMPUTER
SCIENCE AND ENGG.
Bachelor of Engineering (Computer Science & Engineering)
DATA STRUCTURES 21CSH-211

DISCOVER . LEARN . EMPOWER


Agenda

•Sorting
• Bubble Sort
• Insertion Sort
• Selection Sort

2
Sorting
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.
Sorting Techniques
Sorting technique depends on the situation. It depends on two
parameters.
1. Execution time of program that means time taken for execution of
program.
2. Space that means space taken by the program.

Sorting techniques are differentiated by their efficiency and space


requirements.
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.
Bubble Sort

● The above diagram represents how bubble sort actually works. This sort takes O(n 2) time. It

starts with the first two elements and sorts them in ascending order.
● Bubble sort starts with first two elements. It compares the element to check which one is greater.

● In the above diagram, element 40 is greater than 10, so these values must be swapped. This

operation continues until the array is sorted in ascending order.


Bubble Sort
Insertion Sort
● Insertion sort is a simple sorting algorithm.

● This sorting method sorts the array by shifting elements one by one.

● It builds the final sorted array one item at a time.

● Insertion sort has one of the simplest implementation.

● This sort is efficient for smaller data sets but it is insufficient for larger lists.

● It has less space complexity like bubble sort.

● It requires single additional memory space.

● Insertion sort does not change the relative order of elements with equal keys because it is

stable.
Insertion Sort

1/7/2022
Insertion Sort

1/7/2022
Insertion Sort

1/7/2022
Insertion Sort
Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place


comparison-based algorithm in which the list is divided into two parts, the sorted part
at the left end and the unsorted part at the right end. Initially, the sorted part is empty
and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the leftmost
element, and that element becomes a part of the sorted array. This process continues
moving unsorted array boundary by one element to the right.
This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n2), where n is the number of items.
Selection Sort

1/7/2022
Selection Sort
Selection Sort

1/7/2022
Selection Sort
Selection Sort
References

• Lipschutz, Seymour, “Data Structures”, Schaum's Outline Series, Tata McGraw Hill.
• Goodrich, Michael T., Tamassia, Roberto, and Mount, David M., “Data Structures and Algorithms in C++”, Wiley
Student Edition.
• https://www.tutorialspoint.com/data_structures_algorithms/algorithms_basics.htm
• https://www.cs.utexas.edu/users/djimenez/utsa/cs1723/lecturehtml
• https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-4.
php
• https://www.programiz.com/dsa/merge-sort
• https://www.geeksforgeeks.org/binary-search/

19
THANK YOU

You might also like