understanding sorting notes for class 11

chapter-10
understanding sorting notes for computer science with python class 11

notes pdf file download

understanding sorting notes for class 11

 

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:
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)
          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

You may also like...

1 Response

  1. November 9, 2020

    […] UNDERSTANDING SORTING […]

Leave a Reply

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