티스토리 뷰

Python

Searching and Sorting

techbard 2016.05.31 12:53

# 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]


댓글
댓글쓰기 폼
공지사항
Total
409,074
Today
3
Yesterday
40
«   2019/10   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
글 보관함