CHAPTER -5 SORTING

3M QUESTIONS: PART C [Link].30

1. What is sorting? Mention the two types of sorting.
Ans: Sorting is the process of ordering or arranging a given collection of
elements in some particular order.
Types of sorting are:
i)Bubble sort
ii)Insertion sort
iii)Selection sort
2. Define constant time, linear time and quadratic time
algorithm.
Ans: Constant time algorithm: Any algorithm that does not have any
loop will have time complexity as 1 since the number of instructions to be
executed will be constant, irrespective of the data size. Such algorithms
are known as Constant time algorithms.
Linear time algorithm: Any algorithm that has a loop (usually 1 to n)
will have the time complexity as n because the loop will execute the
statement inside its body n number of times. Such algorithms are known
as Linear time algorithms.
Quadratic time algorithm: A loop within a loop (nested loop) will have
the time complexity as n². Such algorithms are known as Quadratic time
algorithms.
3. Write bubble sort algorithm to sort the elements in
ascending order.
Ans: 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
4. What is the basic principle behind bubble sort?
Ans: Basic principle behind bubble sort is it sorts a given list of elements
by repeatedly comparing the adjacent elements and swapping them if
they are unordered. Swapping two elements means changing their
positions with each other such that the larger element
gradually move to their correct position.
5. Explain how selection sort arranges elements in
ascending order.
Ans: For arranging elements in ascending order, in the first
pass, all the elements in the unsorted list are traversed to find
the smallest element. The smallest element is then swapped
with the leftmost element of the unsorted list. This element
occupies the first position in the sorted list, and it is not
considered in further passes. This process continues until n-1
smallest elements are found and moved to their respective
places.
6. Explain how insertion sort arranges elements in
ascending order.
Ans: In insertion sort , the list is divided into two parts - one of
sorted elements and another of unsorted elements. Each
element in the unsorted list is considered one by one and is
inserted into the sorted list at its appropriate position. In each
pass, the sorted list is traversed from the backward direction to
find the position where the unsorted element could be inserted.
The elements of sorted list will be shifted towards right making
space for the first element where it could be inserted. This
continues till all the elements in unsorted lists are inserted at
appropriate positions in the sorted list.
5M QUESTIONS: PART E [Link].42 (COMPULSORY QN.)
1. Write an algorithm to sort elements using bubble
sort method.
Ans: 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
2. Write an algorithm to sort elements using
insertion sort method.

Ans: 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
Step 9: SET i=i+1
3. Write an algorithm to sort elements using selection
sort method.
Ans: 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
4. Write the process
Step to sort the following elements using insertion
10: swap(numList[i],numList[min])
sort method. 80,60, 20, 40, 50, 10
Step 11: SET i=i+1
Pass1:

8 6 2 4 5 1 swa

0 0 0 0 0 0
No
change
2 4 6 8 5 1
0
8 0 0
2 0
6 swa 4 0
5 0
1
0 0 0 0 0 0 2 4 6 8 5 1
6 8 2 4 5 1 0 0 0 0 0 0
swa
0 0 0 0 0 0 2 4 6 5 8 1 p
Pass 4:
0 0swa
0 0 0 0
6 8 2 4 5 1 2 4 5 6 8 1
0 0 0 0 0 0 0 0 0 No
0 0 0
6 2 8 4 5 1 Pass 2: change
2 4 5 6 8 1
0 0 0 0 0 0 0 0 0 0 0 0
2 6 8 4
swa 5 1
0 0 0 0 0 0
swa 2 4 5 6 8 1
2 6 8 4 5 1 0 0 0 0 0 0
0 swa
0 0 0 0 0
Pass 5:
2 6 4 8 5 1 Pass 3:
0swa 0 0 0 0 0
2 4 6 8 5 1 swa

0 0 0 0 0 0
2 4 swa
1 5 6 8
0 0 0 0 0 0
2 1 4 5 6 8
0 0 0 0 0 0
1 2 4 5 6 8
0 0 0 0 0 0
 5. Perform Selection sort algorithm on the following list of
elements correctly and neatly showing no change
the various
min=77 passes while
sorting in ascending order 99 88 77 65 55
Ans:
Pass 1:
9 8 7 6 5
9 8 7 5 5
Min=99 Pass 2:
9 8 7 6 5 5 8 7 6 9
9 8 7 5 5 5 8 7 5 9
Min=88
9 8 7 6 5 5 8 7 6 9 Min=88
9 8 7 5 5 5 8 7 5 9

9 8 7 6 5 Min=77 5 8 7 6 9
9 8 7 5 5 5 8 7 5 9
Min=77
Min=65
9 8 7 6 5 5
Swa 8 7 6 9 min=65
9 8 7 5 5 5
p 8 7 5 9
Min=55
swap Min=

5 6 7 8 9
5 8 7 6 9 5 5 7 8 9
5 8 7 5 9

Pass 3:
Pass 4:
5 6 7 8 9 5 6 7 8 9
5 5 7 8 9
Min=77 5 5 7 8 9
5 6 7 8 9 5 6 7 8 9 Min=88
5 5 7 8 9 5 5 7 8 9
5 6 7 8 9 Min=77
5 5 7 8 9
 Min=88 no
change 3 4 1 1 -6 2
0
3 1 4 1 -6 2 swap
6. Arrange the following elements in ascending order using insertion sort
5algorithm
6 7 4, 8 9 1, -6, 2
3, 10, 0
5 5 7 8 9
Pass 1:
swap

4 3 1 1 -6 2
3 1 4 1 -6 2
0
0
4 3 1 1 -6 2
Pass 4:
0
Swap
3 4 1 1 -6 2
1 3 4 1 -6 2
0
0
Pass 2: 1 3 4 -6 1 2 swap
0
3 4 1 1 -6 2
0 swap
No
1 3 -6 4 1 2
3 4 1 1 -6 2 0
0
1 -6 3 4 1 2 swap
change
0

swap
-6 1 3 4 1 2
Pass 3:
0

3 4 1 1 -6 2 Pass 5:
0
swap
-6 1 3 4 1 2
0
 swap Pass 2:
-6 1 3 4 2 1
0 3 5 6 2 8
-6 1 3 2 4 1 No change
0 swap

3 5 6 2 8 No
-6 1 2 3 4 1 change
0 swap

-6 1 2 3 4 1 swap
0 3 5 2 6 8

7. Sort the list 5,3,8,6,2 using bubble sort.

5 3 8 6 2 Pass 1:
Pass 3;

3 5 8 6 2
swap 3 5 2 6 8

3 5 8 6 2 No change
No 3 5 2 6 8
change
swap
3 5 6 8 2 3 2 5 6 8
swap

3 5 6 2 8
Pass 4:
swap

3 2 5 6 8
swap
3 5 6 2 8
2 3 5 6 8