Scribd
Upload
6 views4 pages

Bubble and Counting Sort Explained

The document provides an overview of two sorting algorithms: Bubble Sort and Counting Sort. Bubble Sort has a time complexity of O(N) in the best case and O(N^2) in average and worst cases, while Counting Sort has a time complexity of O(N + K) for all cases. Key points about Counting Sort include its non-comparison-based nature, requirement for positive integers, and inefficiency with large value ranges.

Uploaded by

rocedo8037
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views4 pages

Bubble and Counting Sort Explained

The document provides an overview of two sorting algorithms: Bubble Sort and Counting Sort. Bubble Sort has a time complexity of O(N) in the best case and O(N^2) in average and worst cases, while Counting Sort has a time complexity of O(N + K) for all cases. Key points about Counting Sort include its non-comparison-based nature, requirement for positive integers, and inefficiency with large value ranges.

Uploaded by

rocedo8037
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Lab 4

Sorting Algorithms
3. Bubble Sort
Code
BubbleSort(arr)
while(swap)
swapped = false
for (i = 1 to n-1)
if(arr[i - 1] > arr[i])
swap(arr[i - 1], arr[i])
swapped = true
end if
end for
end while

Time Complexity

Best Case: O(𝑵) The array is already sorted.

Average Case: O(𝑵𝟐 )

Worst Case: O(𝑵𝟐 )

Space Complexity of Bubble Sort is O(1) (no extra space)

For more information about bubble sort watch the following video:
[Link]
4. Counting Sort
Code
for i=0 to k
C[i] = 0
end for
for i=0 to length(A)
C[A[i]] = C[A[i]] + 1
end for
for i = 1 to k
C[i] = C[i] + C[i-1]
end for
for i = length(A)-1 downto 0
B[C[A[i]]] = A[i]
C[A[i]] = C[A[i]] – 1
End for

Time Complexity

Best Case: O(𝑵 + 𝑲)

Average Case: O(𝑵 + 𝑲)

Worst Case: O(𝑵 + 𝑲)

Space Complexity

Worst-case scenario: O(𝑵 + 𝑲)

Best-case scenario: O(𝑵 + 𝑲)

Conclusion
1. Counting sort is not a comparison-based sorting algorithm
2. Counting sort can be performed only on positive numbers.
3. Counting sort is inefficient if the range of values to be sorted is very large.
4. Counting sort is not an In-place sorting algorithm, It uses extra space for sorting the array
elements.

You might also like