Question

Using PYTHON. Implement the stooge sort algorithm3to sort an array/vector of integers.

Your program should be able to read inputs from a file called “data.txt” where the first value of each line is the number of integers that need to be sorted, followed by the integers

The output will be written to a file called “stooge.txt”.

Stooge sort is a “bad” recursive sorting algorithm. Given an array A, the algorithm can be defined as follows:

Step 1:

If the value at the leftmost position of the array is larger than the value at the rightmost position then swap values.

Step 2: If there are 3 or more elements in the array, then:

 Recursively call Stooge sort with the initial 2/3 of the array

 Recursively call Stooge sort with the last 2/3 of the array.

 Recursively call Stooge sort with the initial 2/3 of the array again.

Examplevalues for data.txt :

4 19 2 5 11

8 1 2 3 4 5 6 1 2

Answer 1

ANSWER:-

def stooge_sort(list, low, high):
if low >= high:
return
# if the value at left is larger then swap
if list[low] > list[high]:
temp = list[low]
list[low] = list[high]
list[high] = temp
# if there are 3 or more elements in the array
# recursively call stooge_sort with intial 2/3 of the array
# recursively call stooge_sort with last 2/3 of the array
# recursively call stooge_sort with intial 2/3 of the array
if high-low+1 > 2:
t = (int)((high - low + 1)/3)
stooge_sort(list, low, (high-t))
stooge_sort(list, low+t, (high))
stooge_sort(list, low, (high-t))
out_file = open("stooge.txt","w")
with open("data.txt") as f:
for line in f: # reads file line by line
l = []
dummy = line.split() # it splits line by space
for i in range(1,len(dummy)):
l.append(int(dummy[i])) # convert every element to int and append
stooge_sort(l,0,len(l)-1) # call sort
s = ''
for i in l:
s += str(i) + ' ' # convert elements into string to append into file
s += '\n'
print(s)
out_file.write(s)
out_file.close()

  
  

OUTPUT:-

NOTE:- If you have any doubts, please comment below. THANK YOU!!! Please give positive rating.