Using Python please show how to time a bubble sort such as presented below: def

Question

Using Python please show how to time a bubble sort such as presented below:

def bubbleSort(list):

needNextPass = True
  
k = 1
while k < len(list) and needNextPass:
# List may be sorted and next pass not needed
needNextPass = False
for i in range(len(list) - k):
if list[i] > list[i + 1]:
# swap list[i] with list[i + 1]
temp = list[i]
list[i] = list[i + 1]
list[i + 1] = temp
  
needNextPass = True # Next pass still needed

# A test method
def main():
list = [5000, 200000, 250000, 10000, 150000, 300000]
bubbleSort(list)
for v in list:
  
print(v, end = ",")
  

main()

Explanation / Answer

Please find my answer for Bubble Sort time analysis:

Let's go through the cases for Big O for Bubble Sort

Case 1) O(n) (Best case) This time complexity can occur if the array is already sorted, and that means that no swap occurred and only 1 iteration of n elements

Case 2) O(n^2) (Worst case) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs. Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.