Complexity of conventional Sorting
Algorithms
Course Code: CSC2211 Course Title: Algorithms
Dept. of Computer Science
Faculty of Science and Technology
Lecture No: 4.2 Week No: 04 Semester: Summer 22-23
Lecturer: Pritam Khan Boni;
[email protected] Lecture Outline
1. Sorting Algorithms
Counting Sort
Sorting Algorithms with linear time
Counting Sort
Counting sort: No comparisons between
elements.
Input: A[1 . . n], where A[j] ∈ {1, 2, . . . , k}.
Output: B[1 . . n], sorted.
Auxiliary storage: C [1 . . k].
1 for i ← 1 to k
2 do C [i ] ←
3 for j 0
← 1 to n
4 do C [A[j]] ← C [A[j]] d C [i ] = |{key
5 for i +
← 12 to k = i }|
6 do C [i ] ← C [i ] + C
7 [i −
for j ← 1]
n downto 1 d C [i ] = |{key
8 do B[C [A[j]]] ← ≤ i }|
9 A[j]C [A[j]] ← C [A[j]]
−1
12 /
Counting sort example
Counting sort example Loop 1
for i ←1 to k
do C [i ] ←0
Counting sort example Loop 2
for j ←1 to n
do C [A[j ]] ←C [A[j ]] + 1 C [i ] = |{key = i}|
Counting sort example Loop 2
for j ←1 to n
do C [A[j ]] ←C [A[j ]] + 1 C [i ] = |{key = i}|
Counting sort example Loop 2
for j ←1 to n
do C [A[j ]] ←C [A[j ]] + 1 C [i ] = |{key = i}|
Counting sort example Loop 2
for j ←1 to n
do C [A[j ]] ←C [A[j ]] + 1 C [i ] = |{key = i}|
Counting sort example Loop 2
for j ←1 to n
do C [A[j ]] ←C [A[j ]] + 1 C [i ] = |{key = i}|
Counting sort example Loop 3
for i ←2 to k
do C [i ] ←C [i ] + C [i −1] C [i ] = |{key ≤i}|
Counting sort example Loop 3
for i ←2 to k
do C [i ] ←C [i ] + C [i −1] C [i ] = |{key ≤i}|
Counting sort example Loop 3
Consider as index of A
for i ←2 to k
do C [i ] ←C [i ] + C [i −1] C [i ] = |{key ≤i}|
Counting sort example loop 4
Consider as index of A
for j ←n downto 1
do B[C [A[j ]]] ←A[j ]
C [A[j ]] ←C [A[j ]] −1
Counting sort example Loop 4
Consider as index of A
for j ←n downto 1
do B[C [A[j ]]] ←A[j ]
C [A[j ]] ←C [A[j ]] −1
Counting sort example Loop 4
Consider as index of A
for j ←n downto 1
do B[C [A[j ]]] ←A[j ]
C [A[j ]] ←C [A[j ]] −1
Counting sort example Loop 4
Consider as index of A
for j ←n downto 1
do B[C [A[j ]]] ←A[j ]
C [A[j ]] ←C [A[j ]] −1
Counting sort example Loop 4
Consider as index of A
for j ←n downto 1
do B[C [A[j ]]] ←A[j ]
C [A[j ]] ←C [A[j ]] −1
Counting sort Complexity
O(k)
O(n)
O(k)
O(n)
O(n + k)
The worst-case running time of Counting sort is O(n + k).
If k = O(n), then the worst case running time is O(n).
Books
Introduction to Algorithms, Thomas H. Cormen, Charle E.
Leiserson,
Ronald L. Rivest, Clifford Stein (CLRS).
Fundamental of Computer Algorithms, Ellis Horowitz, Sartaj
Sahni, Sanguthevar Rajasekaran (HSR)
Find out the recurrence relation of the algorithm and set a
boundary using Master Theorem
funcA (ArrayA, leftIndex, rightIndex, increment){
if (leftIndex==rightIndex)
return;
for (i=leftIndex; i<rightIndex; i++)
ArrayA[i] = Array[i]+ increment;
mid = (rightIndex-leftIndex)/2;
funcA(ArrayA, leftIndex, mid, increment);
funcA(ArrayA,mid+1, rightIndex,increment);
funcA (ArrayA, leftIndex, mid, increment+1);
}
References
https://www.google.com/search?q=bubble+sort+
step+by+step&sxsrf=ALeKk01uxzgfT3Oy6k1Q3WxVnSpiIN8_4g:1587999728942
&tbm=isch&source=iu&ictx=1&fir=vRwFsGwVfJ6pJM%253A%252CSzhhze6MPQr4c
M%252C_&vet=1&usg=AI4_-kSrEEXqwRL-PkHhVUtn7jNfF9dB6g&sa=X&ved=2ahUK
Ewje0Pz974jpAhXRAnIKHWhMD2UQ_h0wAXoECAcQBg#imgrc=EN4Sdu7veOWVo
M&imgdii=eOqvCu85p9-eBM
https://www.interviewcake.com/concept/java/counting-sort
https://www.geeksforgeeks.org/counting-sort/
https://www.hackerearth.com/practice/algorithms/sorting/quick-sort/tutorial/
