quick sort and merge sort using Divide-and-Conquer

Quick Sort Algorithm:

Algorithm Partition(a,m,p)

{

v:=a[m]; i:=m; j:=p; repeat

{

repeat

i: =i + l; until(a[i]>=v); repeat

j:=j-1;

until(a[j] <=u);

if (i <j)then Interchange(a,i,j);

} until(i >=j);

a[m] :=a[j];a[j] :=v; return j;

}

 

Algorithm Interchange(a,i,j)

{

p:=a[i]; a[i]:=a[j];a[j]:=p;

}

 

Algorithm QuickSort(p, q)

{

if (p <q) then //If there are more than one element

{

j :=Partition(a,p, q + 1); QuickSort(p,j-1); QuickSort(j+ l,q);

}

}

 

Quick Sort Source Code:

import random

def quick_sort(a, p, q): if p < q:

j = partition(a, p, q) quick_sort(a, p, j-1) quick_sort(a, j+1, q)

def partition(a, m, p): v = a[m]

i = m

j = p

while True:

while a[i] < v: i += 1

while a[j] > v: j -= 1

if i >= j:

return j

a[i], a[j] = a[j], a[i]

arr = [random.randint(1, 100) for_in range(10)] print("Unsorted array:", arr)

quick_sort(arr, 0, len(arr)-1) print("Sorted array:", arr)

Merge Sort Algorithm:

Algorithm MergeSort(Low, high)

{

if (low< high) then //If therearemorethan oneelement

{

mid:=[(low+high)/2]; MergeSort(low,mid); MergeSort(mid+ I,high); Merge(lowm, mid,high);

}

}

 

Algorithm Merge(low,mid,high)

{

h:=low; i:=low; j:=mid+1;

while ((h<=mid) and (j<=high)) do

{

if(a[h]<=a[j]) then

{

b[i]:=a[h];h:=h+1;

}

else

{

b[i]:=a[j];j:=j+1;

}

i:=i+1;

}

if(h>mid) then

for k:=a[k];i:=i+1;

{

b[i] :=a[k];i :=i +1;

}

else

for k:=h to mid do

{

b[i]:=a[k];i:=i+1;

}

for k:= low to high do a[k]:=b[k];

}

Source Code:

def merge_sort(a): if len(a) <= 1:

return a

mid = len(a) // 2

left = merge_sort(a[:mid]) right = merge_sort(a[mid:]) return merge(left, right)

def merge(left, right): result = []

i = j = 0

while i < len(left) and j < len(right): if left[i] <= right[j]:

result.append(left[i]) i += 1

else:

result.append(right[j]) j += 1

result += left[i:] result += right[j:] return result

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

print("Sorted Array",merge_sort(a))