Sorting and Searching Programs in Python

SORTING

Bubble Sort:


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

Popular posts from this blog

પટેલ સમાજનો ઈતિહાસ જાણો : કોણ અને ક્યાંથી આવ્યા હતા પાટીદારો

Python HTML Generator using Yattag Part 1

Java Event Delegation Model, Listener and Adapter Classes