Python programing lab
Selection and Bubble sort
[Link] : 10
Name :[Link]
[Link] : 24Z353
Problem 1 : Basic Selection sort
Input
def selection_sort(arr):
for i in range(len(arr)):
min_idx = i
for j in range (i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i],arr[min_idx] = arr[min_idx], arr[i]
return arr
input_list = [64,25,12,22,11]
output_list = selection_sort(input_list)
print(output_list)
output
[11, 12, 22, 25, 64]
Conclusion
Thus the above problem is executed successfully.
Problem 2 : basic bubble sort
input
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]
return arr
input_list = [5,1,4,2,8]
output_list = bubble_sort(input_list)
print(output_list)
output
[1, 2, 4, 5, 8]
Conclusion
Thus the above problem is executed successfully.
Problem 3 : selection sort in descending order
Input
def selection_sort_desc(arr):
for i in range(len(arr)):
max_idx = i
for j in range(i+1, len(arr)):
if arr[j] > arr[max_idx]:
max_idx = j
arr[i], arr[max_idx] = arr[max_idx], arr[i]
return arr
input_list = [3, 1, 4, 1, 5]
output_list = selection_sort_desc(input_list)
print(output_list)
output
[5, 4, 3, 1, 1]
Conclusion
Thus the above problem is executed successfully.
Problem 4 : bubble sort in descending order
Input
def bubble_sort_desc(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]
return arr
input_list = [10, 20, 5, 15]
print(bubble_sort_desc(input_list))
output
[20, 15, 10, 5]
Conclusion
Thus the above problem is executed successfully.
Problem 5 : selection sort with strings
Input
def selection_sort_strings(arr):
for i in range(len(arr)):
min_idx = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
input_list = ["banana", "apple", "cherry"]
output_list = selection_sort_strings(input_list)
print(output_list)
output
['apple', 'banana', 'cherry']
Conclusion
Thus the above problem is executed successfully.
Problem 6 : bubble sort with strings
Input
def bubble_sort_strings(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]
return arr
input_list = ["dog", "cat", "bat"]
output_list = bubble_sort_strings(input_list)
print(output_list)
output
['bat', 'cat', 'dog']
Conclusion
Thus the above problem is executed successfully.
Problem 7 : optimized bubble sort
Input
def optimized_bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
input_list = [2, 1, 3]
print(optimized_bubble_sort(input_list))
output
[1, 2, 3]
Conclusion
Thus the above problem is executed successfully.
Problem 8 : selection sort with indices
Input
def selection_sort_with_indices(arr):
n = len(arr)
indices = list(range(n))
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
indices[i], indices[min_idx] = indices[min_idx], indices[i]
return arr, indices
input_list = [4, 2, 5, 1]
sorted_list, original_indices = selection_sort_with_indices(input_list)
print("Sorted List:", sorted_list)
print("Original Indices:", original_indices)
output
Sorted List: [1, 2, 4, 5]
Original Indices: [3, 1, 0, 2]
Conclusion
Thus the above problem is executed successfully.
Problem 9 : Bubble sort for floating numbers
Input
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]
return arr
numbers = [1.1, 3.3, 2.2, 5.5]
sorted_numbers = bubble_sort(numbers)
print(sorted_numbers)
output
[1.1, 2.2, 3.3, 5.5]
Conclusion
Thus the above problem is executed successfully.
Problem 10 : selection sort for floating number
Input
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
numbers = [2.5, 1.5, 3.5]
sorted_numbers = selection_sort(numbers) print(sorted_numbers)
output
[1.5, 2.5, 3.5]
Conclusion
Thus the above problem is executed successfully.
Problem 11 : Bubble sort with custom swaps
Input
def bubble_sort_count_swaps(arr):
n = len(arr)
swap_count = 0
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]
swap_count += 1
return arr, swap_count
data = [4, 3, 2, 1]
sorted_data, swaps = bubble_sort_count_swaps(data)
print("Sorted List =", sorted_data, ", Swaps =", swaps)
output
Sorted List = [1, 2, 3, 4] , Swaps = 6
Conclusion
Thus the above problem is executed successfully.
Problem 12 : selection sort with custom key
Input
def selection_sort_custom_key(arr, key):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j][key] < arr[min_idx][key]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
data = [{"age": 30}, {"age": 25}, {"age": 20}]
print(selection_sort_custom_key(data, "age"))
output
[{'age': 20}, {'age': 25}, {'age': 30}]
Conclusion
Thus the above problem is executed successfully.
Problem 13 : Bubble sort with custom key
Input
def bubble_sort_custom_key(arr, key):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j][key] > arr[j+1][key]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
data = [{"height": 6.0}, {"height": 5.5}, {"height": 5.8}]
print(bubble_sort_custom_key(data, "height"))
output
[{'height': 5.5}, {'height': 5.8}, {'height': 6.0}]
Conclusion
Thus the above problem is executed successfully.
Problem 14 : selection sort for negative numbers
Input
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
data = [-1, 3, -2, 5]
print(selection_sort(data))
output
[-2, -1, 3, 5]
Conclusion
Thus the above problem is executed successfully
Problem 15 : Bubble sort for negative numbers
Input
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]
return arr
data = [10, -10, -5, 5]
print(bubble_sort(data))
output
[-10, -5, 5, 10]
Conclusion
Thus the above problem is executed successfully
Problem 16 : : selection sort for 2D array
Input
def selection_sort_2d(arr):
for row in arr:
n = len(row)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if row[j] < row[min_idx]:
min_idx = j
row[i], row[min_idx] = row[min_idx], row[i]
return arr
data = [[3, 2, 1], [6, 5, 4]]
print(selection_sort_2d(data))
output
[[1, 2, 3], [4, 5, 6]]
Conclusion
Thus the above problem is executed successfully
Problem 17 : Bubble sort for 2D array
Input
def bubble_sort_2d(arr):
for row in arr:
n = len(row)
for i in range(n):
for j in range(0, n-i-1):
if row[j] > row[j+1]:
row[j], row[j+1] = row[j+1], row[j]
return arr
data = [[9, 7, 5], [8, 6, 4]]
print(bubble_sort_2d(data))
output
[[5, 7, 9], [4, 6, 8]]
Conclusion
Thus the above problem is executed successfully
Problem 18 : selection sort for limited range
Input
def selection_sort_limited(arr, start, end):
for i in range(start, end):
min_idx = i
for j in range(i + 1, end + 1):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
arr1 = [5, 3, 8, 6, 2]
start1, end1 = 1, 3
print(selection_sort_limited(arr1, start1, end1))
output
[5, 3, 6, 8, 2]
Conclusion
Thus the above problem is executed successfully.
Problem 19 : Bubble sort for limited range
Input
def bubble_sort_limited(arr, start, end):
for i in range(start, end):
for j in range(start, end - (i - start)):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
arr2 = [4, 1, 3, 2, 5]
start2, end2 = 0, 2
print(bubble_sort_limited(arr2, start2, end2))
output
[1, 3, 4, 2, 5]
Conclusion
Thus the above problem is executed successfully.
Problem 20 : visualize sorting steps
Input
def bubble_sort_visualize(arr):
n = len(arr)
for i in range(n - 1):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
print(arr)
input_list = [4, 3, 2, 1]
bubble_sort_visualize(input_list)
output
[3, 2, 1, 4] [2, 1, 3, 4] [1, 2, 3, 4]
Conclusion
Thus the above problem is executed successfully.
Linear and Binary searching
Problem 1 : linear search
Input
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
arr1 = [15, 8, 25, 30, 10]
target1 = 25
print(linear_search(arr1, target1))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 2 : Binary search
Input
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
arr = [5, 10, 15, 20, 25, 30]
target = 15
result = binary_search(arr, target)
print(result)
Output
Conclusion
Thus the above problem is executed successfully.
Problem 3 : Recursive Binary search
Input
def recursive_binary_search(arr, target, left, right):
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return recursive_binary_search(arr, target, mid + 1, right)
else:
return recursive_binary_search(arr, target, left, mid - 1)
arr3 = [3, 8, 11, 15, 18, 20]
target3 = 11
print(recursive_binary_search(arr3, target3, 0, len(arr3) - 1))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 4 : Linear search for maximum elements.
Input
def find_max(arr):
max_element = arr[0]
for i in range(1, len(arr)):
if arr[i] > max_element:
max_element = arr[i]
return max_element
arr4 = [10, 25, 30, 5, 15]
print(find_max(arr4))
Output
30
Conclusion
Thus the above problem is executed successfully.
Problem 5 : Binary search for First occurrences
Input
def binary_search_first_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
right = mid - 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
arr5 = [1, 2, 2, 2, 3, 4]
target5 = 2
print(binary_search_first_occurrence(arr5, target5))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 6 : Linear search with string elements
Input
def linear_search_strings(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
arr6 = ["apple", "banana", "cherry", "date"]
target6 = "cherry"
print(linear_search_strings(arr6, target6))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 7 : Binary search for range
Input
def binary_search_for_range(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return True
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
arr7 = [5, 10, 15, 20, 25, 30]
target7 = 18
print(binary_search_for_range(arr7, target7))
Output
False
Conclusion
Thus the above problem is executed successfully.
Problem 8 : Linear Search with Condition
Input
def linear_search_greater_than(arr, value):
result = [x for x in arr if x > value]
return result
arr8 = [10, 20, 5, 15, 30]
condition = 15
print(linear_search_greater_than(arr8, condition))
Output
[20, 30]
Conclusion
Thus the above problem is executed successfully.
Problem 9 : Binary Search in Rotated Sorted Array
Input
def binary_search_rotated(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[left] <= arr[mid]:
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else:
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
arr9 = [15, 20, 25, 5, 10]
target9 = 5
print(binary_search_rotated(arr9, target9))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 10 : Linear Search for Frequency
Input
def linear_search_frequency(arr, target):
count = sum(1 for x in arr if x == target)
return count
arr10 = [2, 3, 2, 5, 2, 7]
target10 = 2
print(linear_search_frequency(arr10, target10))
Output
Conclusion
Thus the above problem is executed successfully.
Problem 11 : Binary Search for Last Occurrence
Input
def binary_search_last_occurrence(arr, target):
left, right = 0, len(arr) - 1
result = -1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
result = mid
left = mid + 1
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return result
arr11 = [2, 3, 3, 3, 4, 5]
target11 = 3
print(binary_search_last_occurrence(arr11, target11)
Output
Conclusion
Thus the above problem is executed successfully.
Problem 12 : Linear Search for Minimum Element
Input
def find_min(arr):
min_element = arr[0]
for i in range(1, len(arr)):
if arr[i] < min_element:
min_element = arr[i]
return min_element
arr12 = [20, 15, 30, 10, 25]
print(find_min(arr12))
Output
10
Conclusion
Thus the above problem is executed successfully.
Problem 13 : Binary Search for Closest Value
Input
def binary_search_closest(arr, target):
left, right = 0, len(arr) - 1
closest = arr[0]
while left <= right:
mid = (left + right) // 2
if abs(arr[mid] - target) < abs(closest - target):
closest = arr[mid]
if arr[mid] < target:
left = mid + 1
elif arr[mid] > target:
right = mid - 1
else:
return arr[mid]
return closest
arr13 = [10, 20, 30, 40, 50]
target13 = 35
print(binary_search_closest(arr13, target13))
Output
30
Conclusion
Thus the above problem is executed successfully.
Problem 14 : Linear Search for Even Numbers
Input
def find_even_numbers(arr):
result = [x for x in arr if x % 2 == 0]
return result
arr14 = [5, 10, 15, 20, 25, 30]
print(find_even_numbers(arr14))
Output
[10, 20, 30]
Conclusion
Thus the above problem is executed successfully.
Problem 15 : Binary Search for Multiple Targets
Input
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
def binary_search_multiple(arr, targets):
return [binary_search(arr, target) for target in targets]
arr15 = [5, 10, 15, 20, 25]
targets = [10, 25]
print(binary_search_multiple(arr15, targets))
Output
[1, 4]
Conclusion
Thus the above problem is executed successfully.
Problem 16 : Linear Search with Indices
Input
def linear_search_indices(arr, target):
indices = [i for i, value in enumerate(arr) if value == target]
return indices
print(linear_search_indices([1, 3, 1, 4, 1], 1))
Output
[0, 2, 4]
Conclusion
Thus the above problem is executed successfully.
Problem 17 : Binary Search in 2D Array
Input
def binary_search_2d(matrix, target):
if not matrix:
return None (1, 1)
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = (left + right) // 2
mid_value = matrix[mid // cols][mid % cols]
if mid_value == target:
return mid // cols, mid % cols
elif mid_value < target:
left = mid + 1
else:
right = mid - 1
return None
print(binary_search_2d([[1, 2, 3], [4, 5, 6], [7, 8, 9]], 5))
Output
(1, 1)
Conclusion
Thus the above problem is executed successfully.
Problem 18 : Linear Search for Custom Key
Input
def linear_search_custom_key(arr, target):
for item in arr:
if item == target:
return item
return None
print(linear_search_custom_key([{"id": 1}, {"id": 2}], {"id": 2}))
Output
{'id': 2}
Conclusion
Thus the above problem is executed successfully.
Problem 19 : Binary Search with Duplicate Values
Input
def binary_search_duplicates(arr, target):
result = []
for i in range(len(arr)):
if arr[i] == target:
[Link](i)
return result
print(binary_search_duplicates([1, 2, 2, 2, 3], 2))
Output
[1, 2, 3]
Conclusion
Thus the above problem is executed successfully.
Problem 20 : Linear Search for Palindromes
Input
def is_palindrome(s):
return s == s[::-1]
def linear_search_palindromes(arr):
palindromes = [word for word in arr if is_palindrome(word)]
return palindromes
print(linear_search_palindromes(["radar", "hello", "level", "world"]))
Output
['radar', 'level']
Conclusion
Thus the above problem is executed successfully.