from random import randint
def hoare_partition(in_arr, l_index, r_index):
pivot = in_arr[(l_index+r_index)//2]
r_pointer = r_index
l_pointer = l_index
while l_pointer <= r_pointer:
while in_arr[l_pointer] < pivot:
l_pointer += 1
while in_arr[r_pointer] > pivot:
r_pointer -= 1
if l_pointer >= r_pointer:
break
in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
r_pointer -= 1
l_pointer += 1
l_pointer = 0
r_pointer_1 = r_pointer
while l_pointer <= r_pointer_1:
while in_arr[l_pointer] < pivot:
l_pointer += 1
while in_arr[r_pointer_1] == pivot:
r_pointer_1 -= 1
if l_pointer >= r_pointer_1:
break
in_arr[l_pointer], in_arr[r_pointer_1] = in_arr[r_pointer_1], in_arr[l_pointer]
r_pointer_1 -= 1
l_pointer += 1
l_pointer = r_pointer + 1
r_pointer = len(in_arr) - 1
while l_pointer < r_pointer:
while in_arr[l_pointer] == pivot:
if l_pointer + 1 == len(in_arr):
return in_arr
l_pointer += 1
while in_arr[r_pointer] > pivot:
r_pointer -= 1
if l_pointer >= r_pointer:
break
in_arr[l_pointer], in_arr[r_pointer] = in_arr[r_pointer], in_arr[l_pointer]
r_pointer -= 1
l_pointer += 1
print(pivot)
return in_arr
for j in range(0, 1000):
print("N:", j)
a = [randint(0, 10) for i in range(0, 10)]
print(a)
print(hoare_partition(a, 0, len(a) - 1))def hoare_partition(arr, low, high):
pivot = arr[low]
i = low
j = high
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]