I have the assignment to calculate the total number of list visits in the quick-sort program by Python. Please check the code below:
arr1 = [4, 5, 3, 7, 2]
def inplace_quick_sort(arr, a, b, y):
count = y
count += 1 # for the access to the "a" element in the list while calling the function
if a >= b:
return
count += 1 # access for arr[b]
pivot = arr[b]
left = a
right = b - 1
while left <= right:
count += 1 # access for arr[left]
while left <= right and arr[left] <= pivot:
left += 1
count += 1 # access for arr[right]
while left <= right and pivot < arr[right]:
right -= 1
if left <= right:
count += 4 # access for swap left and right
arr[left], arr[right] = arr[right], arr[left]
left, right = left + 1, right - 1
count += 4 # access for swap left and last
print(count)
arr[left], arr[b] = arr[b], arr[left]
inplace_quick_sort(arr, a, left - 1, count)
inplace_quick_sort(arr, left + 1, b, count)
x = 0
print("count = " + str(inplace_quick_sort(arr1, 0, len(arr1) - 1, x)))
I have two questions. The first is the "count" add the numbers for the list-visit correctly? The second is I got a wired output like below:
count = 8
I do not understand the iteration about the "count." Why did "count" equal to 8? The "count" suppose to be greater than 8. Sorry, I made some mistakes in my code. I revised it and still got the wired output. I appreciate any guidance from you. Thank you very much.
The main changes you need, to count array access correctly are:
Keep count as a global variable so that each branch of inplace_quick_sort() towards the end of your function updates the same counter. Remove y from the function definition and usage and start the main func with global count.
The two count += 1's just before while should be just inside/at the start of each while loop because each while loop is accessing either arr[left] or arr[right]. So that counter should increment for each iteration of the while
For the statements while left <= right and arr[left] <= pivot, it's not necessary that arr[left] is accessed - if left <= right is False, then arr[left] <= pivot is never evaluated, and arr[left] is not accessed. That has to be split out into a different step:
This line should be removed because a is being accessed only once when you call it. The remaining times, it's recursive so update count there.
count += 1 # for the access to the "a" element in the list while calling the functionIf array "access" includes only reading but not writing, then the two count += 4 lines should be just count += 2. I've left it as per your code, change it accordingly or leave it as is.
def inplace_quick_sort(arr, a, b):
global count
if a >= b:
return
count += 1 # access for arr[b]
pivot = arr[b]
left = a
right = b - 1
while left <= right:
while left <= right:
count += 1 # access for arr[left]
if arr[left] <= pivot:
left += 1
else:
break # needed to match the original while-logic
while left <= right:
count += 1 # access for arr[right]
if pivot < arr[right]:
right -= 1
else:
break # needed to match the original while-logic
if left <= right:
count += 4 # access for swap left and right
arr[left], arr[right] = arr[right], arr[left]
left, right = left + 1, right - 1
count += 4 # access for swap left and last
# print(count)
arr[left], arr[b] = arr[b], arr[left]
inplace_quick_sort(arr, a, left - 1)
inplace_quick_sort(arr, left + 1, b)
Execute with:
arr1 = [4, 5, 3, 7, 2]
count = 1 # because you sart with `len(arr1)`
inplace_quick_sort(arr1, 0, len(arr1) - 1)
print("count = ", count)
print('array afer:', arr1)
Output:
count = 30
array afer: [2, 3, 4, 5, 7]
Btw, if you did want to use count as a local variable, then:
if a >= b: return statement should be if a >= b: return countinplace_quick_sort should increment the previous count and make sure to return count at the end:
count = inplace_quick_sort(arr, a, left - 1, count)
count = inplace_quick_sort(arr, left + 1, b, count)
return count
Also, this answer is only wrt counting correctly, not fixing the implementation of quick sort as done.