what is number of passes exactly in sorting algorithm?
Back to General discussions forum
In reference to bubble sort problem, I am confused with the number of passes that should be one of the output for eg in 3 1 4 1 5 9 2 6 no of passes is 5, but according to me it should be 28 here is my program:
import numpy
def main():
n = int(raw_input())
input_list = map(int, raw_input().split())
no_of_passes = 0
total_no_of_swaps = 0
a = numpy.array(input_list)
for i in range(len(input_list)-1):
for j in range(len(input_list)-i-1):
no_of_passes += 1
if a[j] > a[j+1]:
a[j],a[j+1] = a[j+1],a[j]
total_no_of_swaps += 1
print no_of_passes,total_no_of_swaps
if __name__ == '__main__':
main()
Please can someone tell me what does passes mean in sorting algorithms.
Hi! Thanks for your question!
As you probably have seen, problem statement explains it like this:
Take a pass through array, examining all pairs of adjacent elements (N-1 pairs for array of N elements).
So "pass" is the iteration of outer loop, while you are counting iterations of inner loops (while inner loop performs the "passing" through array, pushing the "bubble" to the end).
May I ask why you're using a numpy array instead of a standard list?
sorry @Christopher Matthews, I just swithced from C/C++ world to python , I figured out now that I didn't have to do that, I will just remove it.