# understanding sorting notes for class 11

Contents

## ### sorting:-

sorting in computer means arranging elements in a specific order-ascending or increasing order or  descending or decreasing order. For instance, if you have sequence as:
s1=[4,6,2,8,1,6]
the sorted sequence in ascending order will be:
[1,2,4,5,6,8]
and in ascending order, it would be:
[8,6,5,4,2,1]

### Bubble sort:-

the basic idea of Bubble sort is to compare two adjoining values and exchange them if they are not in proper order.to understand this, we take following example below:

### Q 1. program to sort a list using Bubble sort.

ans.   alist=[15,6,13,22,3,52,2]
print(“original list is :”,alist)
n=len(alist)
for i in range(n):
for j in range(0,n-i-1):
if alist[j]>alist[j+1]:
alist[j],alist[j+1]=alist[j+1],alist[j]
print(“list after sorting:”,alist)

### the output produce by code is like

original list is : [15,6,13,22,3,52,2]
list after sorting : [2,3,6,13,15,22,52]

## the number off swapping will vary depending upon the elements of the sequence:

### Best case:-

in the best case, i.e., when all the elements of the sequence are already sorted(i.e., in desired sort order), no swapping will take place.
~ n2 comparisons + 0 swapping = N2 ops

### Worst case:-

in the worst case , i.e., when all elements are in opposite order, every comparison will result into a swapping.
~  N2 comparison + N2 swapping = 2N2  ops

### Insertion sort:-

insertion sort is a sorting algorithm that builds a sorted list one element at a time from the unsorted list by inserting the element at its correct position in sorted list.

### Q 2. program to sort a sequence using insertion sort.

ans.     alist=[15,6,13,22,3,52,2]
print(“orginal list is:”,alist]
for i in range(1,len(alist)):
key=alist[i]
j=j-1
while j>=0 and key<alist[j] :
alist[j+1]=alist[j]   #shift element to right to make room for key
j-j-1
else:
alist[j+1]=key
print(“list after sorting:”,alist)

#### output produced by above program is shown below:

original list is : [15,6,13,22,3,52,2]
list after sorting : [2,3,6,13,15,22,52]

### Number of operation:-

as we mentioned during bubble sort discussion that two costly operation and swapping.
the operation that effect of insertion sort in terms of number of operation are:
(i) the comparison operation in the inner loop ,and
(ii)the exchange operation in the inner loop.
(i)the number of comparisons:
~ N2 comparisons in insertion sort
(ii) the number of exchanges:
< N2 exchanges i insertion sort

### best case:-

in the best case when the sequence is already in desired sorted order, there will be maximum N-1 number of comparison and exchanges(i.e., N-1 ops).
worst case:-
in the worst case, there will be maximum possible number (< N2) of comparisons and exchanges (i.e., < N2 ops).
understanding sorting notes for class 11

### 1 Response

1. November 9, 2020

[…] UNDERSTANDING SORTING […]