Related Topics
Data Structure
def linear_search(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
Binary search (assuming the array is sorted in ascending order):
def binary_search(arr, x):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
In the linear search implementation, we iterate through the array one element at a time and compare each element to the target value. If we find a match, we return the index of the element. If we reach the end of the array without finding a match, we return -1.
In the binary search implementation, we start by setting the left and right bounds of the search range to the first and last indices of the array, respectively. We then repeatedly find the midpoint of the search range and compare it to the target value. If the midpoint is equal to the target value, we return its index. If the midpoint is less than the target value, we set the left bound to the index immediately to the right of the midpoint. If the midpoint is greater than the target value, we set the right bound to the index immediately to the left of the midpoint. We continue this process until either we find the target value or we have narrowed the search range to an empty interval (in which case we return -1).
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]
Bubble sort:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
Insertion sort:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j]:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
These functions all take an array as input and sort it in ascending order in place.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
i = j = 0
merged = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged += left[i:]
merged += right[j:]
return merged
Quick Sort
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[0]
left = []
right = []
for i in range(1, len(arr)):
if arr[i] < pivot:
left.append(arr[i])
else:
right.append(arr[i])
return quick_sort(left) + [pivot] + quick_sort(right)
Note that these implementations assume that the input is a list of integers, but can be modified to handle other data types or custom comparison functions.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.