understanding sorting notes for class 11

understanding sorting notes for computer science with python class 11

notes pdf file download

understanding sorting notes for class 11



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:
the sorted sequence in ascending order will be:
and in ascending order, it would be:

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:
understanding sorting notes for class 11

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

ans.   alist=[15,6,13,22,3,52,2]
          print(“original list is :”,alist)
          for i in range(n):
                 for j in range(0,n-i-1):
                       if alist[j]>alist[j+1]:
           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)):
                     while j>=0 and key<alist[j] :
                               alist[j+1]=alist[j]   #shift element to right to make room for 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

You may also like...

1 Response

  1. November 9, 2020


Leave a Reply

Your email address will not be published. Required fields are marked *