Searching and Sorting

# Sequential Search

def seq_search(arr, ele):

pos = 0

while len(arr) > pos:

if arr[pos] == ele:

return True

else:

pos += 1

return False

o = seq_search([1, 2, 3,], 3)

print(o)

# 결과

True

# Binary Search

def binary_search(arr, ele):

first = 0

last = len(arr) - 1

found = False

while first <= last and not found:

mid = (first + last) // 2

if arr[mid] == ele:

found = True

else:

if ele < arr[mid]:

last = mid - 1

else:

first = mid + 1

return found

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

o = binary_search(arr, 7)

print(o)

# 결과

True

# Binary Search - recursive ver

def rec_bin_search(arr, ele):

if len(arr) == 0:

return False

else:

mid = len(arr) // 2

if arr[mid] == ele:

return True

else:

if ele < arr[mid]:

return rec_bin_search(arr[:mid], ele)

else:

return rec_bin_search(arr[mid + 1:], ele)

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]

o = rec_bin_search(arr, 10)

print(o)

# 결과

False

# Binary Search - recursive (sorted)

def rec_bin_search(arr, ele):

sorted_arr = sorted(arr)

if len(sorted_arr) == 0:

return False

else:

mid = len(sorted_arr) // 2

if sorted_arr[mid] == ele:

return True

else:

if sorted_arr[mid] < ele:

return rec_bin_search(sorted_arr[mid + 1:], ele)

else:

return rec_bin_search(sorted_arr[:mid], ele)

arr = [5, 4, 3, 2, 1]

o = rec_bin_search(arr, 2)

print(o)

# 결과

True

# Implementation a Bubble Sort

def bubble_sort(arr):

for n in range(len(arr) - 1, 0, -1):

for k in range(n):

if arr[k] > arr[k + 1]:

temp = arr[k]

arr[k] = arr[k + 1]

arr[k + 1] = temp

return arr

arr = [5, 3, 7, 2]

o = bubble_sort(arr)

print(o)

# 결과

[2, 3, 5, 7]

# Implementation of Selection Sort

def selection_sort(arr):

for fill_slot in range(len(arr) - 1, 0, -1):

posOfMax = 0

for loc in range(1, fill_slot + 1):

if arr[loc] > arr[posOfMax]:

posOfMax = loc

temp = arr[fill_slot]

arr[fill_slot] = arr[posOfMax]

arr[posOfMax] = temp

return arr

arr = [5, 4, 3, 2, 1]

o = selection_sort(arr)

print(o)

# 결과

[1, 2, 3, 4, 5]

# Implementation of Insertion Sort

def insertion_sort(arr):

for i in range(1, len(arr)):

current_val = arr[i]

pos = i

while pos > 0 and arr[pos - 1] > current_val:

arr[pos] = arr[pos - 1]

pos -= 1

arr[pos] = current_val

return arr

 

arr = [5, 4, 1, 2, 3]

o = insertion_sort(arr)

print(o)

# 결과

[1, 2, 3, 4, 5]

# Implementation of Merge Sort

def merge_sort(arr):

if len(arr) > 1:

mid = len(arr) // 2

left_half = arr[:mid]

right_half = arr[mid:]

merge_sort(left_half)

merge_sort(right_half)

i = 0

j = 0

k = 0

while i < len(left_half) and j < len(right_half):

if left_half[i] < right_half[j]:

arr[k] = left_half[i]

i += 1

else:

arr[k] = right_half[j]

j += 1

k += 1

while i < len(left_half):

arr[k] = left_half[i]

i += 1

k += 1

while j < len(right_half):

arr[k] = right_half[j]

j += 1

k += 1

return arr

arr = [5, 4, 1, 2, 3]

o = merge_sort(arr)

print(o)

# 결과

[1, 2, 3, 4, 5]

# Implementation of Quick Sort

def quick_sort(arr):

quick_sort_help(arr, 0, len(arr) - 1)

return arr

def quick_sort_help(arr, first, last):

if first < last:

split_point = partition(arr, first, last)

quick_sort_help(arr, first, split_point - 1)

quick_sort_help(arr, split_point + 1, last)

def partition(arr, first, last):

pivot_val = arr[first]

left_mark = first + 1

right_mark = last

done = False

while not done:

while left_mark <= right_mark and arr[left_mark] <= pivot_val:

left_mark += 1

while arr[right_mark] >= pivot_val and right_mark >= left_mark:

right_mark -= 1

if right_mark < left_mark:

done = True

else:

temp = arr[left_mark]

arr[left_mark] = arr[right_mark]

arr[right_mark] = temp

temp = arr[first]

arr[first] = arr[right_mark]

arr[right_mark] = temp

return right_mark

arr = [5, 4, 1, 2, 3]

o = quick_sort(arr)

print(o)

# 결과

[1, 2, 3, 4, 5]