data_structure) 6 sorting algorithms using python(2)

Hello, this is second posting about sorting algorithms.

I'll show you rest 3 sorting algorithms.

Fourth is merge sort. This algorithm has O(nlogn) time complexity regardless Best, average, Worst case. I think this is really great. Also, this algorithm is stable.

def __merge(data, left, middle, right):

a = data[left:middle + 1]

b = data[middle + 1: right + 1]

i = 0

j = 0

k = left

while i < len(a) and j < len(b):

if a[i] <= b[j]:

data[k] = a[i]

i += 1

else:

data[k] = b[j]

j += 1

k += 1

while i < len(a):

data[k] = a[i]

i += 1

k += 1

while j < len(b):

data[k] = b[j]

j += 1

k += 1

def __merge_sort(data, left, right):

if left >= right:

return

m = int((left + right) / 2)

__merge_sort(data, left, m)

__merge_sort(data, m + 1, right)

__merge(data, left, m, right)

def merge_sort(data):

__merge_sort(data, 0, len(data) - 1)

This is the source code of merge_sort.

Fifth is quick sort. This algorithm has O(nlogn) time complexity at Best, Average case. However, it's Worst case has O(n^2) time complexity.

import random

def __partition(data, left, right):

r = random.randint(left, right)

data[left], data[r] = data[r], data[left]

pivot = left

store = left + 1

for i in range(left + 1, right + 1):

if data[i] < data[pivot]:

data[i], data[store] = data[store], data[i]

store += 1

data[pivot], data[store - 1] = data[store - 1], data[pivot]

return store - 1

def __quick_sort(data, left, right):

if left >= right:

return

pivot = __partition(data, left, right)

__quick_sort(data, left, pivot - 1)

__quick_sort(data, pivot + 1, right)

def quick_sort(data):

__quick_sort(data, 0, len(data) - 1)

This is the source code of quick_sort.

Last is heap sort. This algorithm has O(nlogn) time complexity regardless Bset, Average, Worst case but it is not stable.

def __heapify(data, n, i):

while True:

left, right = 2 * i + 1, 2 * i + 2

if right >= n or data[left] > data[right]:

child = left

else:

child = right

if child >= n or data[i] > data[child]:

return

data[child], data[i] = data[i], data[child]

i = child

def heap_sort(data):

n = len(data)

for i in range(n, -1, -1):

__heapify(data, n, i)

for i in range(n-1, 0, -1):

data[i], data[0] = data[0], data[i]

__heapify(data, i, 0)

This is the source code of heap_sort.

If you have any questions or any opinions, tell me you'll be welcomed :-)

Thank you :-)