SZU
Shaikh Zayed University
CS511
Data Structures and Algorithms
Semester: Spring 1404
Senior-Teach-Assist Nasim Jan Taniwall
[Link]@[Link]
Department of Information Technology (IT)
Computer Science Faculty
Shaikh Zayed University
Khost, Afghanistan
1
Sorting Algorithm
■ Sorting algorithm is a method for reorganizing a large number
of items into a specific order, such as alphabetical, highest-to-
lowest value or shortest-to-longest distance.
2
Different Sorting Algorithms
■ Many different techniques available for sorting, differentiated
by their efficiency and space requirements.
■ Following are some sorting techniques.
Bubble Sort
Insertion Sort
Selection Sort
Merge Sort
Shell Sort
3
Insertion Sort
■ Insertion sort is a sorting algorithm that places an unsorted element at
its suitable place in each iteration.
■ Insertion sort works similarly as we sort cards in our hand in a card
game.
■ We assume that the first card is already sorted then, we select an
unsorted card. If the unsorted card is greater than the card in hand, it is
placed on the right otherwise, to the left. In the same way, other
unsorted cards are taken and put in their right place.
■ A similar approach is used by insertion sort.
4
Working of Insertion Sort
■ Suppose we need to sort the following array.
9 5 1 4 3
Sorted Part Unsorted Part
1. The first element in the array is assumed to be sorted. Take the second
element and store it separately in key.
Compare key with the first element. If the first element is greater
than key, then key is placed in front of the first element.
5
Working of Insertion Sort
■ Step 1
9 5 1 4 3
Key 5 9 9 1 4 3
5 9 1 4 3
■ If the first element is greater than key, then key is placed in front of the first
15
element.
Working of Insertion Sort
■ Now, the first two elements are
sorted. 5 9 1 4 3
■ Take the third element and compare
it with the elements on the left of it.
Placed it just behind the element 1 5 9 9 4 3
smaller than it. If there is no
element smaller than it, then place Key
it at the beginning of the array.
5 5 9 4 3
■ Place 1 at the beginning
1 5 9 4 3
7
Working of Insertion Sort
■ Similarly, place every unsorted
element at its correct position.
1 5 9 4 3
■ Place 4 behind 1
4 1 5 9 9 3
Key
1 5 5 9 3
1 4 5 9 3
8
Working of Insertion Sort
■ Place 3 behind 1
1 4 5 9 3
and the array is
sorted.
3 1 4 5 9 9
Key
1 4 5 5 9
1 4 4 5 9
1 3 4 5 9
9
Insertion Sort Implementation
def insertionSort(List):
for step in range(1, len(List)):
key = List[step]
j = step - 1
# Compare key with each element on the left of it until an element smaller than
it is found
# For descending order, change key<array[j] to key>array[j].
while j >= 0 and key < List[j]:
List[j + 1] = List[j]
j = j - 1
# Place key at after the element just smaller than it.
List[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print('Sorted List:')
print(data) 19
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. It is also known
as Sorting by exchange.
Working of Bubble Sort
■ Algorithm:
Step1: Starts with the first two elements, comparing them to check
which one is greater.
Step2: If the current and the next element are out of order, swap
them.
Step3: Repeat this process for all the elements until the entire list
is sorted
Bubble Sort
■ Example 1 Assume the following List
5 1 4 2
Bubble Sort
■ First Iteration
Compare the first and second elements
5 1 4 2
� �
j j+1
Bubble Sort
■ First iteration:
Swap first and second element
1 5 4 2
� �
j j+1
Bubble Sort
■ First Iteration
Compare the second and third element
1 5 4 2
� �
j j+1
Bubble Sort
■ First iteration:
Swap them
1 4 5 2
� �
j j+1
Bubble Sort
■ First Iteration
Compare the third and fourth elements
1 4 5 2
� �
j j+1
Bubble Sort
■ First iteration:
Swap them, because 2 is smaller than 5
1 4 2 5
� �
j j+1
Bubble Sort
■ List after first iteration
1 4 2 5
Bubble Sort
■ Second Iteration
Compare again the first and second elements, they are
already sorted no need to swap them.
1 4 2 5
� �
j j+1
Bubble Sort
■ Second Iteration
Compare the second and third elements
1 4 2 5
� �
j j+1
Bubble Sort
■ Second iteration:
Swap them
1 2 4 5
� �
j j+1
Bubble Sort
■ Second iteration:
Now compare the third and fourth elements, they are
already sorted no need to sort them.
1 2 4 5
Bubble Sort
■ Third iteration:
Again compare the first two elements, if they are in a
wrong position, swap them other wise no need to swap
them.
1 2 4 5
� �
j j+1
Bubble Sort
■ List is now sorted
1 2 3 4
Bubble Sort
■ Example 2:
5 4 2 1 3 2 4 1 3 5
4 5 2 1 3 2 1 4 3 5
4 2 5 1 3 2 1 3 4 5
4 2 1 5 3 2 1 3 4 5
4 2 1 3 5 1 2 3 4 5
4 2 1 3 5 1 2 3 4 5
Bubble Sort
■ Python implementation of bubble sort algorithm
def BubbleSort(arr):
for i in range(len(arr)-1):
for j in range(len(arr)-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
arr = [5, 11, 4, 2, 7, 9, 1, 3]
Sortedarr = BubbleSort(arr)
print(Sortedarr)