Block -4
14.6 EXERCISE - 1
1.
2.
SELF-ASSESSMENT
What do you understand by
Discuss
sorting
3. complexity of sorting olgornths
List the types of sorting
techniques?
10.6 INSERTION SORT
A|N| sin memory The nsertion sort algorithn
Suppose an array Awith nelennents A| I), A|21. A|K| into it, proper poition in the previously
scans Afrom A[l| to AN). inserting each clement
sorted subarray A|I]. A|2]l.... A[K- I| That is
Pass I.
A[]by itself is trivialy sorted.
Pass 2. thot: A( | A[2]is sorted.
A[2] Iis mserted either before or after A[l| so
A(2|, that is, before A||], betwren
Poss 3.
AS is inserted into its proper place in A||],
A[)ond A|2], or after A|2], so thot: A[ l], A[2], A[3| ssorted.
sothat:
Pass 4. A{4} is inserted into its proper place in A[l], A[2|, A[3|
A[|], A[2], A(3], A[4] is sorted.
A[N -1] so that:
Pass N.
A[NJ isinserted into its proper place in A[!], A[2], ...
A[I],A[2], .. .A[N] is sorted.
small. For example, this algorithmis very popular
Inis sorting algorithmn is frequenty used when nis
with bridge players when they are first sorting their cards. sorted
only the problem of deciding how to insert A[K] in its proper place in the
Ihere rermains A[K] with A[K - I,
can be accomplished by comparing meeting an elerment
Subarray A[I], A[2], . .. , A[K - I]. ThisA[K] with A[K- 3], and so on, until first
Comparing A[K] with A[K - 2], comparing elements A[K- |], A[K- 2], ..., AJ + I] is moved
forward
that A||] SA[K]. Then each of the
AU] such the J+Istposition in the array.
one location, and AK] is then inserted in otherwise we
simplified if there always is an element A[J] such that AI|]|< A[K]; accomblished
The algorithm is comparing A[K] with A[l]. This condition can be
must constantly check to see if we are
introducing a sentinel element A{0] = -co (or a very small number).
by
Block -.
Paxs
A|1) A|34 A|6) A(7) A|8|
K-1:
77 44 88 22 66 55
88
33) 44 22 66 55
33 7 44 11 88 22 66 S5
33 44 77 88 22 66 55
33 44 77 88 22 66
K=6: 44 77 88 22 66 )55
K=7: 22 33 44 77 88 66 55
22 33 44 66 77 88
Sorted: 11 22 33 44 55 66 77 88
Figure 3 : Insertion sort for n=8items
Wotst (a aja omple xity
t1j uilbay
Insertonsort
Arple d eih ieit
coniparison ast nths alauritl tah tesatirns
Ahil im8erts it ino fhe
correct terneres a
Tandom and thisposition
the inut is in the Hat beitg
pHes s repeated sti allscted The
ingut lenents hae t
4anlages
le implementation
i ent for small data
Ataptive: If the
input list
whete d is the number of is presorted (may not be completely) then insertions sott takes on d
Practically more inversions
efficient than selection and bubble sorts even thnugh all of thetn haye n'; wrs
case complexity
Stable: Maintains relative order of input
In place: It requires only a data if the keys are sarne
cConstant
Onine: Insertion sort can sort the listamount O(1) of additional rmenory space
as it receives it
Algorithm
Cyey repetition oi 1nsertion sort removes an elerment frorm the innut data inaerts it tnto the
the already-sorted list until no input elements correct
remain. Sorting 0s typically done in place. The psit
resulting array
er iterations has the property where the first k + 1
k
entries are sorted.
Sorted partial result Unsorted elernents
Sorted partial result Unsorted elements
becomes
Each elernent greater than x copied to the right as it is compared against x.
Implementation
def Insertionsort( A):
for iin range( 1, lenl A)):
temp =Ai)
k=i
while k >0 and tenp <A|k - 11:
A|k] =A|k - 1|
k =1
A<k| =temp
A 154,26,93,17,77,31,44,55,20)
Insertionsort|A)
print(A)
Example
Given an array: 6 8I45372 and the goal is to put them in ascending order.
68145372 (Consider index 0)
68145372(Consider indices 0- 1)
16845372(Consder indices 0 -2: insertion places 1in front of 6 and 8)
1468S372 (Process sane as above is repeated until array is sorted)
1456 8 372
J07 Iny- *ion sort
289
Block -4
14.8 SELECTION SORT
Suppose an oroy Awith n isin memory. The selection sort
elements A|.A[2,.AIN]
irst find the smallest clement in the ist and put it inalthe
gorithfimrst
for
sorting A works os follows
position. Then find the second smallest elernent in the list and put t inthe second þosition. And s0
on. More preisely
Pass Findthe
location LOC of the smallest in the list t of Nelements
A). A|2). A(N], and then nterchange A|LOC and A[I]. Then:
Pass 2.Fnd the A|l| Is sorted.
location LOC of the smallest in the sublist of N- I elerments
A[2]. A[3),.... A[NJ, and then
interchangeA[LOC) and A[2). Then:
A[I], A(2] is sorted,since A[l] EA[2).
Pass 3.Find the location
LOC of thesmallest in the sublist of N- 2 elements
A[3], A[4),...A[N], and then interchange A[L0c and
A|:
A[], A[2],..., A[3] is sorted, since A[2] £ A[B|
Pass N-I. Find the location LOCof the smaler of the elements A[N- I], A[N], and then interchange A[LOC
and A[N - I], Then:
A[U], A[2, ...,A[N] is sorted, since A[N-1]£A[NJ.
Thus Ais sorted after N - I passes.
Block -4
A|3| AJ4]
A[6] A[7] A[81
Pass A|] A|2) 66 55
88 22
K=1, LOC 4 44
(77 33
88 22 66 55
77
K2, LOC 6 11 (33) 44
66 55
77 88 (33
K=3, LOC = 6 11 22 44
44 66 55
88
K =4, LOC =6 22 33 (77) 77 66 55
44 88
K= 5, LOC 8 11 22 33
66 88
44 55
K=6, LOC= 7 22 33
88
55 66
K=7, LOC =7 1! 22 33 44
77 88
55 66
Sorted: 11 22 33 44
Figure4 :Selection sort for n=8items.
ire and \leor
tlu
Aappecd 1
def swepA KV
temp A[N
Alv] tenp
933!
A1127, 220, 246 277, 321, 454, 534, S68,
BubbleSorti)
pinti
Thus modifiei versOn noes the best ease4)
Performance complesity : On) version) : O(n)
Vorat casecomplexity (lmproved
Bestcase complexity (Basic version) : O(n)
Avernge case complexity : 0(1) auxiliary
Worst case space
10.6 Selection Sort
stmall files, It i
Selection sort works well for
Selection sort
fles wth very
is an in- place sorting algorithm,
kevs. This is because selection is Imade
based on kevs
large alues and small
only ahen requircd
AdvantagesEasy to implement
In-place sort (requires no additional storage space)
Disadvantages
Doesn't scale well:O(n²)
Algorithm
1. Find the minimum value in the list
2. Swap it with the value in the current position
sorted
J. Kepeat this process for all the elements until the entire array is
1his algorithm is called selection, sort since it repeatedly selects the smallest element.
Implementation
def SelectionSort[A):
for iin rangef len{ A)):
least =i
for k in range( i + 1, len(A)):
if Ak] < A[least):
least = k
swap( A, least, i )
def swap( A, x, y :
temp Ax]
A - Aly]
Aly]- temp
A- (54,26,93, 17,77,31,44,55,20|
Selection
Sort(A)
print(A)
Performance
Worst case complexity : O(n)
Best case complexity : 0()
10.6 Selection Sort
Algorithmic Thinking with ython
fiorting
le il tor all
recedes indiceN TAn uch that the
Teord R\U\ n key Ali) euals key
(equivalent
clementa retaintheihcirsoteiltelutive
list. Few soting AL if precedes rerord R/| in the
algothms record R\|relatiye
Acdaptabit honitioun ryen atermsiaorting)
ntaln the ordet of elements
mgtme, compl
Algorietxihtmsy changea
that take based on
this lnto pre sotedneas
24OherClassifications account Ate (yulek aort pre
knwu to be adnptive
sortedness of the input
of classifying sorting
lntemal Sort algorithms is:
External Sort
at use main memory
paofaAOnithn
assumes high- exclusively during the sort are called
h-speed random algorithms. Thís
access to all memory. internal sorting
Atemal
Sort
Kragalgorithmsthat use external memory, such as tape or disk, during the sort Come under this category.
05Bubblesort
bbiesortisthe simplest sorting algorithm. It works by iterating the input array from the first element to last,
amparngeach nair of elements and swapping them if needed. Bubble sort continues its iterations until no
atSWaps are needed The algorithm gets its name from the way smaller elements "bubble" to the top of the
Generally.insertion sort has better performance than bubble sort. Some researchers suggest that we should
t teachbubble sort because of its simplicity and complexity.
onl signifcant advantage that bubble sort has over other implementations is that it can detect whether the
istiss already sorted or not.
S
Inplementation
def BubbleSort( A):
for iin range( len( A)):
for kin range( len( A)1,i-1).
if (A[k| <AK -1] ):
swap A, k, k-1)
def swap( A, x, y ):
termp =A<x
Alx] =Alyl
Alyl =temp
A=(534,246,933,127,277,321,454,565,220|
BubbleSort|A)
print/A)
ligorithm takes O(n) (even in best case). We can improve it by using one extra flag. No more swaps indicate the completion of
Irng, If the ist is already sorted, we can use this flag to skip the remaining pases.
def BubbleSort( A):
Swapped =1
for i in range( len( A]):
if (swapped 0):
return
for kin range( len( A)-1,i,-1):
if(Ak] <A|k-1|):
287
04Other Classifications
Block -4
present and discUss a very simble
there are many. mony different sortng dlgoriths. Here we
sorting algorithm known as the bubble sort. order; this restriction
in increasing numerical dato
Remark: The above definition of sorting refers to nngng numerical datamnean arranging
is only for notationol convenience. Cleorly. sorting mnay oso Actually, Ais frequently a
decreasing order or arranging nonnunnericolI datain alphabetical order.
thatthe values ofa given key
recerds, ond sorting Arefers to reorangwg the ecords ofAso
file of
are ordered.
bubble sort algorithm works as
Supposethe list of numbers A[l ]. A[2]. ... A[N] issin memory. The
follows :
compare
Step I. poreAI] and A[2]and arrange them in the desired order, so that A[l] <A<21: hen
nd arrange them so that A/21 <A3).Then compare
A[3] and A|4| and arrange
them
r a t A|3| <A[4). Contue until we combare A/N. Il with A/N] and arronge them so thot
A[N- I] <A[N].
"bubbled
Observe that Step I involves rn- I (During Step I, the largest element is
comparisons.
e nnposition or "sinks" to the nth bosition ) When Steb lis completed, A|N] Wll contain
the largest element.
Step 2. Repeat Step I with one less comparison; that is, now we stop after we compare and possibly
rearrange A[N- 2] and A(N- IL (Step 2involves N- 2comparisons and, when Step2is compieted,
the second largest element will occupy
A[N- I)
Step 3. Kepeat Step Iwith two fewer comparisons; that is, we stop after we compare and possibly redrange
A[N -3] and A[N - 2].
Step N- 1. Compare A[lI] with A[2] and arrange them sothat A[l] <A|21.
After n - Isteps, the list will be sorted in increasing order.
The process ofisequentially traversing through all or part of a list is frequently called a"pass", so
each of the above steps is called a pass. Accordingly, the bubble sort algoithm requires
n-lpasses, where n is the number ofinput items.
Example
Suppose the following numbers are stored in an array A:
32, 51, 27, 85, 66, 23, 13, 57
We apply the bubble sort to the array A. We discuss each pass separately.
Pass I. . We have the following comparisons :
(a) Compare A, and A,. Since 32 < 51, the list is not altered.
(b) Compare A, and A, Since 51 > 27, interchange 5l and 27 as follows :
UNIT -14 (38)
Block -4
32, (27,)(51) 85, 66, 23, 13, 57
Compare A, ond A. Since S1 <85, the list is not olterrd.
(
(ollows :
(0 Compare A, ond A, Since 85 > 66. interchange 85 and 66 as
32, 27, sI, (66.)(05.) 23, 13, 57
(e Compate A, and A,. Snce 85 > 23, Interchange 85 and 23 as follows
32, 27, SI, 66, (23,) (85,) 13, 57
) Compare A, and A. Since 85 > 13, interchange 85 ond 13 to yield:
32, 27, 51, 66, 23, (13,)(85,) 57
(8) Compare A, and A, Sicne 85 >57, interchange 85 and 57 to yield :
32, 27, SI, 66, 23, 13, (57,)(85
t oic eid of tnis first pass, the largest number. 85. has moved to the last position. However the rest of the
numbers are not sorted, even though some of them have changed their positons.
For the remainder of the passes, we show only the
interchanges.
Pass 2.
(27,)(33,) 51, 66, 23, 13, 57, 85
27, 33, 51, (23,) (66,) 13, 57, 85
27, 33, 51, 23, (13,) (66,) 57, 85
27, 33, 51, 23, 13, (57,) (66,) 85
At the end of Pass 2, the second largest number, 66, has moved its way down to the next-to-last position.
Pass 3. 27, 33, (23) (5T) 13, 57, 66, 85
27, 33, 23, 13) 61) 57, 66, 85
Pass 4. 27, (23) 33) 13, 51, 57, 66, 85
27, 23, 13) (33) 51, 57, 66, 85
Pass 5. 23) (27) 13, 33, 51, 57, 66, 85
23, 13) (27) 33, 51, 57, 66, 85
Pass 6. 13) 23) 27, 33, 51, 57, 66, 85
Pass 6 actualy has two comparisons, A, with A, and A, and A, The second
combarison does not involve an
interchange.
Poss 7.Finally, A, is compared with A, Since 13 <23, no interchange
takes place.
Since the list has 8 elements; it is sorted after the
seventh pass. (Observe that in this example, the list was
actually sorted ofter the sixth þass.)
(39)
