2nd PUC Computer Science Chapter 5 Sorting Notes | Bubble Sort, Selection Sort, Insertion Sort

Sorting is the process of ordering or arranging a given collection of elements in some particular order. Numbers can be arranged in ascending or descending order. Strings can be arranged alphabetically or according to their length.

Examples given in the textbook include words in a dictionary being arranged alphabetically, examination seats being ordered according to candidates’ roll numbers, and a list of students being sorted based on height or weight.

Sorting a large number of items can require substantial time. This extra time, called overhead, can nevertheless be worthwhile compared with the time required to find an element in an unsorted list.

This chapter discusses three sorting methods and their implementation using Python: Bubble Sort, Selection Sort and Insertion Sort.

Ways of Sorting Mentioned in the Chapter

• Numbers can be sorted in ascending (increasing) order.
• Numbers can be sorted in descending (decreasing) order.
• Strings can be sorted alphabetically from a-z or z-a.
• Strings can also be sorted according to their length.
• Words in a dictionary are sorted alphabetically.
• Examination seats can be ordered according to candidates’ roll numbers.
• A list of students can be sorted based on height or weight.

Meaning of Swapping

Swapping two elements means changing their positions with each other.

Pass

In the algorithm, every iteration through each element of a list is called a pass.

Number of Passes

For a list containing n elements, bubble sort makes a total of n − 1 passes to sort the list.

Working of Bubble Sort

1. Adjacent elements are compared.
2. For ascending order, if the first element is bigger than the second, they are swapped.
3. If they are already in the correct order, no change is made.
4. The comparisons continue until the end of the list is reached.
5. After each pass, the largest element reaches its correct position at the end.
6. The largest element is said to be “bubbled up”.
7. The sorted element is not considered in the remaining passes.
8. Therefore, the list of elements considered becomes smaller in successive passes.

Important Observation from Figure 5.1

The list becomes sorted in the 4th pass itself. However, the normal bubble sort technique performs a redundant 5th pass, which does not result in any swap.

Algorithm 5.1: 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
Step 8: SET i=i+1

💻 Program 5-1 — Implementation of Bubble Sort using Python

def bubble_Sort(list1):
    n = len(list1)
    for i in range(n): # Number of passes
        for j in range(0, n-i-1): 
            # size -i-1 because last i elements are already sorted 
            #in previous passes
            if list1[j] > list1[j+1] : 
                # Swap element at jth position with (j+1)th position
                list1[j], list1[j+1] = list1[j+1], list1[j]

numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)

The sorted list is :
-9 1 4 7 8 13

Activity 5.1

Algorithm 5.1 sorts a list in ascending order. Write a bubble sort algorithm to sort a list in descending order.

Activity 5.2

Apply bubble sort technique to sort a list of elements: numList2 = [8, 7, 6, 5, 4]. Show the positions of elements in the list after each pass. In which pass does the last swap happen?

Basic Structure

Number of Passes

For a list containing n elements, selection sort makes n − 1 passes.

Working in Ascending Order

1. In the first pass, traverse all elements in the unsorted list.
2. Find the smallest element.
3. Swap it with the leftmost element of the unsorted list.
4. The selected element becomes the first element of the sorted list.
5. It is not considered in further passes.
6. In the second pass, find the next smallest element from the remaining unsorted elements.
7. Swap it with the leftmost element of the unsorted list.
8. Continue until n − 1 smallest elements are found and placed.
9. The nth element is the last element and is already in its place.

Algorithm 5.2: 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

💻 Program 5-2 — Implementation of Selection Sort using Python

def selection_Sort(list2):
    flag = 0     #to decide when to swap
    n=len(list2)
    for i in range(n): # Traverse through all list elements
        min = i
        for j in range(i + 1, len(list2)):    #the left elements
        #are already sorted in previous passes
            if list2[j] < list2[min]: # element at j is smaller
            #than the current min element
                min = j
                flag = 1
        if flag == 1 :     # next smallest element is found
            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=" ")

The sorted list is :
-9 1 4 7 8 13

Activity 5.3

Consider a list of 10 elements:

randList = [7,11,3,10,17,23,1,4,21,5]

Determine the partially sorted list after four complete passes of selection sort.

Working of Insertion Sort

• The list is divided into a sorted part and an unsorted part.
• Elements from the unsorted list are considered one by one.
• Each element is inserted into its appropriate position in the sorted list.
• In each pass, the sorted list is traversed from the backward direction to find the insertion position.
• If the element to be inserted is smaller than an element in the sorted list, that element is shifted towards the right.
• The shifting creates space for the new element.
• The process continues until all elements in the unsorted list have been inserted.
• The final result is a sorted list arranged in ascending order.

Pass 1

The unsorted list has n − 1 elements and the sorted list has a single element. The first unsorted element is compared with the sorted element. If it is smaller, the sorted element is shifted to the right and the new element is inserted.

Subsequent Passes

The first element of the unsorted list is compared with the elements of the sorted list starting from the backward direction until the appropriate position for insertion is found. The sorted elements are shifted towards the right to create space for the element.

Algorithm 5.3: Insertion Sort

INSERTIONSORT( numList, n)
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 6: numList[j+1] = numList[j] 
Step 7: SET j=j-1
Step 8: numList[j+1] = temp #insert 
temp at position j
Step 9: set i=i+1

💻 Program 5-3 — Implementation of Insertion Sort using Python

def insertion_Sort(list3):
    n= len(list3)
    for i in range(n): # Traverse through all elements
        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=" ")

The sorted list is :
-9 1 4 7 8 13

Activity 5.4

Consider a list of 10 elements:

Array = [7,11,3,10,17,23,1,4,21,5]

Determine the partially sorted list after three complete passes of insertion sort.

There can be more than one approach to solve a problem using a computer. Different algorithms for the same problem may require different amounts of processing time.

For a small set of data elements, the difference in time and memory required by different algorithms may not be significant. However, sorting algorithms may have to work with huge amounts of data in real-world situations. In such cases, total time utilisation becomes significant.

Therefore, it is important to consider the time complexity of an algorithm before using it for a real-world data set.

Computer scientists study time complexity to understand how a sorting algorithm behaves when the order of input elements changes or when the number of elements increases or decreases.

Basic Rules for Estimating Time Complexity

Time Complexity of the Three Sorting Algorithms

The Python programs of Bubble Sort, Selection Sort and Insertion Sort each contain a nested loop. According to the rules given in the textbook, all three sorting algorithms have a time complexity of n².

• Sorting is the process of placing or rearranging a collection of elements into a particular order.
• Bubble Sort is the simplest sorting algorithm that repeatedly swaps adjacent elements when they are unordered in n−1 passes.
• In Selection Sort, the smallest element is selected from the unsorted array and swapped with the leftmost element.
• Insertion Sort places an element of a list at its suitable place in each pass. It is similar to placing cards at their right position while playing cards.
• Complexity analysis is performed to explain how an algorithm will perform when the input grows larger.

1. Define sorting.
2. What is swapping?
3. What is a pass?
4. How many passes does Bubble Sort make for n elements?
5. What is time complexity?
6. What is a constant time algorithm?
7. What is a linear time algorithm?
8. What is a quadratic time algorithm?

1. Explain why sorting is useful.
2. Explain Bubble Sort.
3. Explain the sorted and unsorted lists in Selection Sort.
4. Explain the basic idea of Insertion Sort.
5. Explain the basic rules for estimating time complexity.

1. Explain the working of Bubble Sort.
2. Explain the working of Selection Sort.
3. Explain the working of Insertion Sort.
4. Explain the importance of time complexity.

1. Write Algorithm 5.1 for Bubble Sort.
2. Write the Python program for Bubble Sort.
3. Write Algorithm 5.2 for Selection Sort.
4. Write the Python program for Selection Sort.
5. Write Algorithm 5.3 for Insertion Sort.
6. Write the Python program for Insertion Sort.
7. Explain the time complexity rules discussed in the chapter.

Bubble Sort — Key Code Structure

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]

Selection Sort — Key Code Structure

for i in range(n):
    min = i
    for j in range(i + 1, len(list2)):
        if list2[j] < list2[min]:
            min = j

Insertion Sort — Key Code Structure

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