Sorting and Searching Programs in Python
SORTING
def bubble_sort(nums):
# We set swapped to True so the loop looks runs at least once
swapped = True
while swapped:
swapped = False
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
# Swap the elements
nums[i], nums[i + 1] = nums[i + 1], nums[i]
# Set the flag to True so we'll loop again
swapped = True
# Verify it works
# nums = [5, 2, 1, 8, 4]
nums = input('Enter the list of numbers: ').split()
nums = [int(x) for x in nums]
bubble_sort(nums)
print("List Sorted using Bubble Sort")
print(nums)
Output:
Enter the list of numbers: 5 23 3 65 74 55
List Sorted using Bubble Sort
[3, 5, 23, 55, 65, 74]
Selection Sort:
def selection_sort(nums):
# This value of i corresponds to how many values were sorted
for i in range(len(nums)):
# We assume that the first item of the unsorted segment is the smallest
low_index = i
# This loop iterates over the unsorted items
for j in range(i + 1, len(nums)):
if nums[j] < nums[low_index]:
low_index = j
# Swap values of the lowest unsorted element with the first unsorted
# element
nums[i], nums[low_index] = nums[low_index], nums[i]
nums = [13, 5, 3, 22, 10]
selection_sort(nums)
print("List Sorted using Selection Sort")
print(nums)
Output:
List Sorted using Selection Sort
[3, 5, 10, 13, 22]
Insertion Sort:
def insertion_sort(nums):
# Start on the second element as we assume the first element is sorted
for i in range(1, len(nums)):
item_to_insert = nums[i]
# And keep a reference of the index of the previous element
j = i - 1
# Move all items of the sorted segment forward if they are larger than
# the item to insert
while j >= 0 and nums[j] > item_to_insert:
nums[j + 1] = nums[j]
j -= 1
# Insert the item
nums[j + 1] = item_to_insert
# Verify it works
nums = [90, 10, 15, 25, 7]
insertion_sort(nums)
print("List Sorted using Insertion Sort")
print(nums)
Output:
List Sorted using Insertion Sort
[7, 10, 15, 25, 90]
SEARCHING
Linear Search:
# Python3 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1
def linearsearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = ['m','a','t','r','u','m','a','n', 'd', 'i', 'r']
x = 'd'
print("element found at index "+str(linearsearch(arr,x)))
Output:
element found at index 8
Binary Search:
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l) // 2
# If element is present at the middle itself
if arr[mid] == x:
return mid
# If element is smaller than mid, then it
# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Driver Code
arr = [ 2, 3, 4, 10, 42, 53, 78, 99 ]
x = 10
# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print ("Element is present at index % d" % result)
else:
print ("Element is not present in array")
Output:
Element is present at index 3
Comments
Post a Comment