Scribd
Upload
22 views3 pages

Lab4 Dsa

The document discusses bubble sort and selection sort algorithms. It provides code implementations of bubble sort, recursive bubble sort, and selection sort. It also analyzes the time complexities of bubble sort and selection sort, identifying their best and worst cases as well as providing conclusions on their pros and cons.

Uploaded by

Alishba Soomro
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
22 views3 pages

Lab4 Dsa

The document discusses bubble sort and selection sort algorithms. It provides code implementations of bubble sort, recursive bubble sort, and selection sort. It also analyzes the time complexities of bubble sort and selection sort, identifying their best and worst cases as well as providing conclusions on their pros and cons.

Uploaded by

Alishba Soomro
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
You are on page 1/ 3

SE-22063 LAB -4

Lab # 04
Sorting Operation in an Array Bubble Sort Algorithm
EXERCISE: Attach all [code and outputs] printouts here

1. Give implementation of bubble sort algorithm let‟s assume Array


“A” is consisting of6elements which are
stored in descending order.
INPUT CODE
def bubble_sort(arr):
n = len(arr)

for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]

# Assuming array A with 6 elements in


descending order
A = [6, 5, 4, 3, 2, 1]
bubble_sort(A)
print("Sorted Array:",A

2. Re-write bubble sort algorithm for recursive


function call, Also analyze the worst timecomplexity ofrecursive
bubble sort algorithm.
INPUT CODE
def recursive_bubble_sort(arr, n):
if n == 1:
return

for i in range(n-1):
if arr[i] > arr[i+1]:
arr[i], arr[i+1] = arr[i+1], arr[i]

recursive_bubble_sort(arr, n-1)

# Assuming array A with 6 elements in


descending order
A = [6, 5, 4, 3, 2, 1]
recursive_bubble_sort(A, len(A))
print("Sorted Array (Recursive Bubble
Sort):", A)
SE-22063 LAB -4

3. Select any other sorting algorithm and implement. Assume A[]={ 9,7,5,11,12,2,14,3,10,6}

INPUT CODE
def selection_sort(arr):
n = len(arr)

for i in range(n):
min_index = i
for j in range(i+1, n):
if arr[j] < arr[min_index]:
min_index = j

arr[i], arr[min_index] =
arr[min_index], arr[i]

# Assuming array A
A = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
selection_sort(A)
print("Sorted Array (Selection Sort):", A)

When analyzing the time complexity, we focus on the dominant term, so the worst-case
time complexity of recursive bubble sort is O(n2).

4. Analyze the two sorting algorithms (in 1 & 3) and determine


i. Best and Worst cases ii. Calculate Worst and Best bounds iii. Draw conclusion on the
basis of their pros& cons.

Analysis:

Bubble Sort:
 Best Case: O(n) (when the array is already sorted)
 Worst Case: O(n^2)
 Best Bound: O(n)
 Worst Bound: O(n^2)
 Conclusion: Simple to understand, but inefficient for large datasets.
Selection Sort:
 Best Case: O(n^2)
 Worst Case: O(n^2)
 Best Bound: O(n^2)
 Worst Bound: O(n^2)
 Conclusion: More efficient than bubble sort for large datasets, but still has a high
time complexity.
Consider using more efficient sorting algorithms like Merge Sort or Quick Sort for
better performance in practical scenarios.
SE-22063 LAB -4

You might also like