# 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

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.