II PUC CH: 5 : SORTING
Chapter:5
SORTING
Introduction:
Sorting is the process of ordering / arranging a given collection elements in some particular order.
The different types of sorting techniques are bubble sort selection sort in session sort, etc.
Bubble sort:
Bubble sort is a simple algorithm that organises a list of terms in order by repeatedly comparing and
swapping adjacent elements known as sinking sort.
The name come from the way larger element “bubble” to the top of the list.
Bubble sort is useful for sorting small set of elements, but it’s inefficient for the larger set of elements.
Process :
• It sorts an element by repeatedly comparing adjacent elements and swapping them if they are in
wrong order.
• The algorithm iterates through the element’s multiple times, with each pass pushing the largest
unsorted element to its current position at end.
• Code includes an optimization. If no swaps are made during a pass, the elements are already sorted
and sorting process stops.
Algorithm of bubble sort:
BUBBLESORT( numList, n)
Step 1: SET i = 0
Step 2: WHILE i< n REPEAT STEPS 3 to 8
Step 3: SET j = 0
Step 4: WHILE j< n-i-1,REPEAT STEPS 5 to 7
Step 5: IF numList[j] > numList[j+1] THEN
Step 6: swap(numList[j],numList[j+1])
Step 7: SET j=j+1
IDEAL JAYANAGAR 1
II PUC CH: 5 : SORTING
Step 8: SET i=i+1
Implementation of bubble sort using Python:
def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
print(list1)
numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
Selection sort :
It is the simple algorithm that sorts an array by repeatedly finding largest element in the unsorted part
of a swapping It with the first unsorted element.
Selection got its name because it operates by repeatedly selecting min or max Element from the
unsorted portion of element and placing it at beginning of the sorted portion.
Process:
• First, we find the smallest element and swap it with the first element. The way we get the smallest
element at its correct position.
• Then we find the smallest among remaining elements (or second smallest) and swap it with the
second element.
• We keep doing this until we get all elements moved to the correct position.
IDEAL JAYANAGAR 2
II PUC CH: 5 : SORTING
Algorithm : Selection Sort :
SELECTIONSORT( numList, n)
Step 1: SET i=0
Step 2: WHILE i< n REPEAT STEPS 3 to 11
Step 3: SET min = i, flag = 0
Step 4: SET j= i+1
Step 5: WHILE j<n, REPEAT STEPS 6 to 10
Step 6: IF numList[j] < numList[min] THEN
Step 7: min = j
Step 8: flag = 1
Step 9: IF flag = 1 THEN
Step 10: swap(numList[i],numList[min])
Step 11: SET i=i+1
Implementation of selection sort using Python :
def selection_Sort(list2):
flag = 0
n=len(list2)
for i in range(n):
min = i
for j in range(i + 1, len(list2)):
if list2[j] < list2[min]:
min = j
flag = 1
if flag == 1 :
list2[min], list2[i] = list2[i], list2[min]
numList = [8, 7, 13, 1, -9, 4]
selection_Sort(numList)
print ("The sorted list is :")
for i in range(len(numList)):
print (numList[i], end=" ")
Insertion Sort:
It is a sorting algorithm that builds a sorted list by inserting each element into its correct position.
Insertion sort has got name because the algorithm works by iteratively inserting each element. From an
unsorted list into its correct position with in a sorted portion of the list.
Insertion sort works by continually inserting each element from an unsorted sub list into a sorted sub
list.
Process:
• We start with second element of the list as first element in the list is assumed to be sorted.
• Compare 2nd element with the 1st element and check if the 2nd element is smaller then, swap
them.Move to the 3rd element and compare it with first 2 elements and put at its correct position.
IDEAL JAYANAGAR 3
II PUC CH: 5 : SORTING
• repeat until the entire array is sorted.
Algorithm for insertion sort:
Step 1: SET i=1
Step 2: WHILE i< n REPEAT STEPS 3 to 9
Step 3: temp = numList[i]
Step 4: SET j = i-1
Step 5: WHILE j> = 0 and numList[j]>temp,REPEAT STEPS 6 to 7
Step 8: numList[j+1] = temp #insert temp at position j
Step 9: set i=i+1
Implementation of insertion sort using Python:
def insertion_Sort(list3):
n= len(list3)
for i in range(n):
temp = list3[i]
j = i-1
while j >=0 and temp< list3[j] :
list3[j+1] = list3[j]
j = j-1
list3[j+1] = temp
numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)
print (“The sorted list is :”)
for i in range(len(numList)):
print (numList[i], end=" ")
IDEAL JAYANAGAR 4
II PUC CH: 5 : SORTING
Time complexity of algorithm:
The amount of time and algorithm takes to process a given data can be called its time complexity.
The aim is to find how sorting algorithm behaves when changes in input or number of elements
increases or decrease. Such comparison helps which algorithm is suitable for which kind of data.
Calculating complexity of different algorithm involves mathematical calculations and detailed analysis.
Some of them are following:
• If algorithm doesn’t have loop, then time complexity is one and known as constant time
algorithm.
• If algorithm has loop (1 to N) then time complexity is n and known as linear time algorithm.
• If algorithm has loop within a loop, then time complexity will be n2, and known as quadratic
time algorithm.
• If there is a nested loop and also a single loop, then time complexity will be estimated on
nested loop only.
Note : in all 3 sorting technique there are loop with in other loop, so time complexity will be n 2
IDEAL JAYANAGAR 5
