Lecture 1.2.4
Lecture 1.2.4
ENGINEERING
DEPARTMENT OF COMPUTER
SCIENCE AND ENGG.
Bachelor of Engineering (Computer Science & Engineering)
DATA STRUCTURES 21CSH-211
•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.
● 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
● This sorting method sorts the array by shifting elements one by one.
● This sort is efficient for smaller data sets but it is insufficient for larger lists.
● 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
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