/
CHAPTER- 5
SORTING
SORTING: rs-
Sorting is a process of arranging the elements either in Ascending order or
descending order.
S!'1l11 ,.
Types of
[email protected]~ 2 / ~
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
1. BUBBLE SORT METHOD: ._;
► Bubble sort is a simple sorting algorithm.
► It repeatedly steps through the list, compares adjacent elements,
and swaps them if they are in the wrong order.
► After each pass, the largest unsorted element "bubbles up" to its
correct position.
► Requires n - 1 passes for a list of size n
► The pass through the list is repeated until no swaps are needed
► which indicates that the list is sorted
Algorithm: Bubble Sort (mylist, N)
-~ep 1: for I = 1 to N-1 do
Step 2: for J = 0 to N-1-1 do
Step 3: if (mylist[ J ] > mylist[ J + 1] then
Step 4: swap (mylist[ J] , mylist{ J+ 1 ]
End if
•
End of Step 2 for loop
End of Step 1 for loop
Step 5: output mylist(n)
Step 6: Stop
·----·-
DEPT OF COMPUTE.R SCIENCE, PRESIDENCY PU- COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
2
J
Pvthon Program V C:.,
def hubbleSort(mylist):
n = len(mylist)
for i in range(n):
for j in range (0, n-i-1):
if mylist [ j ] > mylist[ j+ 1 ]:
mylist[ j ], mylist[ j+ 1) = mylistLJ+ 1], mylistu]
numList = [17, 8, 6 -9, 4 1
bubbleSort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[ i ), end=" ")
f_..,
Example: V 'J
First pass Second pass Third pass
1 6 4 3 6 4 3
1 1 1 1 11 1
-\,J'
swap
'\.I'
swap swap
swap
1 4
Is 4
1 1 3 11 13 16 11
'\J'
swap
,-
2. SELECTION SORT METHOD: V '?
► Selection Sort is a simple, comparison-based sorting algorithm.
► It works by repeatedly finding the minimum element from the
unsorted part of the list and putting it at the beginning of the sorted
part.
).- Requires n - 1 passes for a list of size n
- - - ---- -
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
3
Algorithm: Selection Sort (mylist, N)
Step 1: for I= 1 to N-1 do
Step 2: Min= I, Flag= 0
Step 3: for J = I+ 1 to N -1 do
Step 4: if (mylist[ J ) < mylist[ Min ) then
Step 5: Min = J, Flag = 1
End if
Step 6: if (Flag== 1) then
Step 7: swap (mylist[ I ] , mylist[ Min))
End if
End of Step 3 for loop
End of Step 1 for loop
Step 5: output mylist(n)
Step 6: Stop
. _,/,
Python Program / . ·-.
def selectionSort(mylist):
n = len(mylist)
for i in range(O, n):
min= i
flag= 0
for j in range (i+l, n-1):
if (mylist [ j ] < mylist[ min ]):
. .win= j
flag= 1
if (flag == 1)
mylist[ i ], mylist[ min) = mylist[ min], mylist[i]
numList = [17, 8, 6 -9, 4)
selectionSort(numList)
print("The sorted list is:")
for i in range(len(numList)):
11
print(numList[ i ], end=" )
-------- - -
- - - - - -· --- - -- - - -
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
4
Examp le:
First Pass I 1 110 I 231 •2 I ~ I -2 I 10 / 23 / 1 I
Second Pass I -2 I 10 / 23 / 1 I ~ / -2 / 1 / 23 / 10 I
Third Pass I-2 I i 123 I.10 Ii:> I-2 I 1 I10 I23 I
Fourth Pass I -2 I 1 / 10 I23 Ic:> I -2 / 1 / 10 / 23 /
G:l Sorted Array
Ljsmallest number in unsorted array
D Correct p~sition for smallest number in unsorted array
3. INSER TION SORT METH OD: ;,c.-
► Inserti qn ~Ort is a simple sorting algorit hm
► It works by jterativ ely inserti ng each elemen t of an unsort ed list into
its correc t positio n in a sorted portion of the list.
Algori thm: Inserti on Sort (mylist, N)
Step 1: for I = 1 to N-1 do
Step 2: for J = I down to 1 do
Step 3: if (mylist[ J ] < mylist[ J-1 } then
Step 4: swap (mylist[ J ] , mylist[ J-1])
End if
End of Step 2 for loop
End of Step 1 for loop
Step 5: outpu t mylist( n)
Step 6: Stop
- ...... ·- -- -·- - -
ORE -24
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGAL
....
5
fvthon Program
def insertio nSort(m ylist):
n = len(myl ist)
for i in range(l , n):
for j in range (i, 1, -1):
if (mylist [ j ) < mylist[ j-1 )) :
mylistl j ), mylistl j-1 J = mylist! j-1), mylist[ j ]
numLis t = [17, 8, 6 -9, 4)
insertio nSort(n umList)
print("T he sorted list is:")
for i in range(len(numList)):
print(nu mList[ i ], end=" ")
Exampl e:
~~l I ➔ I s 1
12311 j 10 1 s 2 / I23 1 110 1 12
f First Pass . I ®
I10 I5 I2 I➔ II I23 I10 I5 I2 I
ISecond Pass/ 1 @§0 5 I2 I➔ II I10 I23/s I2 I
J J
I Third P~ss I j 1 ~ l2l ➔ J1 is l1olnl2 I
l,,.rourth Pass I I 1 1 s /10 I 23 / 2 1 ➔ 11 1 2 1 s I 10 123 /
'-.__ /
Time Comple xity of Algorith ms
Complexity analysi s explain s how an algorith m will perform when input
values grows larger.
1. Consta nt time Algorithm: An algorith m which does not contain any
loop. It has a time complex ity of 1.
2. Linear time Algorithm: An algoritm which has a loop [contain 1 to n
iteration s] has a time complexity n.
3. Quadra tic time Algorithm: An Algorithm Contain nested loops has a
time complex ity of n 2
-------------------
DEPT OF COMPUTER SCIENCE, PRESIDENCY PU COLLEGE, HEBBALKEMPAPURA, BANGALORE -24
