CS102 A Sorted Tale - comparing swaps of bubble sort and quicksort

Hello there,

here is the project I’m refering to:

Project: A Sorted Tale | Codecademy

Long story short. I wanted to compare the nubmer of swaps from bubble_sort (1092069) with the number of swaps of quicksort, but I don’t know how to get the number of swaps from quicksort.
For this I implemented some changes to quicksort under a function called “quicksort2” and got as results ranging from 7215 up to 9817 swaps.
Now the difference between bubble_sort swaps 1 Mio and quicksort less than 10 k is so big I’m amazed. ANd most important, I’m not sure if I’m counting the quicksort swaps correctly.
So my question in short is:
A. Did I get the real the difference in swaps between quicksort and bubble_sort?
B. Is someone interested in looking over the code? (It is ready for copy, paste and run - if there is problems please respond!)

You’ll find my best try below to count the quicksort swaps below:

Given were the documents sort.py where predefined sorting algorithms bubble_sort and quicksort and script.py to work upon. You will find the changes I made explained in the following order:

1.a) my changes to script.py in which I call a quicksort2 which is intended to return the number of recursive calls, swaps and one other measure.
1.b) explanation under the code

2.a) my changes to sort.py in which I changed code from quicksort to quicksort2
2.b) explanation under the code


1.a) Changes to script.py

print("Pre quicksort2 large:")
start = time.time()
rec_calls, rec_layers, rec_swaps = sorts.quicksort2(long_bookshelf,0, len(long_bookshelf)-1,by_total_length)
end = time.time()
print("The total number of\nrecursive layers:  ", rec_layers, "\nrecursive calls: ", rec_calls, "\nrecursive swaps: ", rec_swaps)
print("Post quicksort timeperiod: ", round(end -start,2))

In this code I call the already changed quicksort algorithm to get three numbers:
The number of recursive calls, the number of recursive layers and the total number of swaps
By number of recursive layers, please think of a tree diagramm, representing the recursive calls. As every call of quicksort recursively calls quicksort again on two arrays (lesser than and greater than pivot), we have a diagramm spliting (at most) in two on every new layer.


2.a) Changes from quicksort to quicksort2
To ease your reading, pay close attention to the (# EXTRA) comments which point towards every addition. The changes include only additions but for one exception under 2. with an explanation in the comment.

def quicksort2(list, start, end, comparison_function):
  if start >= end:
    return
  pivot_idx = random.randrange(start, end + 1)
  pivot_element = list[pivot_idx]
  list[end], list[pivot_idx] = list[pivot_idx], list[end]
  less_than_pointer = start
  rec_swaps = 0   # EXTRA: counting swaps
  for i in range(start, end):
    if comparison_function(pivot_element, list[i]):
      list[i], list[less_than_pointer] = list[less_than_pointer], list[i]
      less_than_pointer += 1
      rec_swaps += 1    # EXTRA: counting swaps
  list[end], list[less_than_pointer] = list[less_than_pointer], list[end]
  # EXTRA: number of rec_calls and recursive layers
   # 1. initializing the count of recursive calls, every call counts itself as a recursive call and as part of a recursive layer
  rec_calls = 1
  rec_layers = 1
  # rec swaps
    # 2. adding number calls from upper positions of the call stack requires a way to return this number of calls to the actual call,  that is way the function call defines a variable
  rec_1 = quicksort2(list, start, less_than_pointer - 1, comparison_function)
  rec_2 = quicksort2(list, less_than_pointer + 1, end, comparison_function)
    # 3. add layers and calls in case there exist some
  if rec_1 and rec_2:
    rec_layers += max(rec_1[1],rec_2[1])
    rec_calls += rec_1[0] + rec_2[0]
    rec_swaps += rec_1[2] + rec_2[2]
    
  elif rec_1:
    rec_layers += rec_1[1]
    rec_calls += rec_1[0]
    rec_swaps += rec_1[2]
  elif rec_2:
    rec_layers += rec_2[1]
    rec_calls += rec_2[0]
    rec_swaps += rec_2[2]
  else:
    pass
    # 4. returning layers and calls
  return rec_calls, rec_layers, rec_swaps

2.b) As most of my changes are explained in the comments in the code, I don’t know what to explain here. Just ask and I’ll respond :sweat_smile:

I’d really love to know how to count hte swaps of quicksort and understand what makes the huge difference in the number of swaps. Still lacking a clear picture in that.