Happy new year! I am finally back with a new post on code… yay!

now I am not a cs major, but come on all engineers should know the basics of cs, right?

Given an unsorted list of numbers, a bubble sort

- repeatedly step through the list to be sorted
- compare each pair of adjacent items and swap them if they are in the wrong order
- repeat until no swaps are needed

Recently, I picked up O’Reilly’s <Computer Science Programming Basics in Ruby>, and their bubble sort method threw me off…

note: I modified it so that I have a rndm_grades method that generates grades for me, so it is not an exact copy from the book, but the core loop functions the same way.

def bubble_sort(n)
grades = rndm_grades(n)
compare = 0
for i in (0..n-2)
for j in ((i+1)..n-1)
compare +=1
if (grades[i] > grades[j])
temp = grades[j]
grades[j] = grades[i]
grades[i] = temp
end
end
end
end

————– Bubble Sort? ————–

grades: [96, 29, 27, 7, 15]

i 0

j 1

comparing 96 & 29

swap takes place…….

j 2

comparing 29 & 27

swap takes place…….

j 3

comparing 27 & 7

swap takes place…….

j 4

comparing 7 & 15

currently grades are [7, 96, 29, 27, 15]

i 1

j 2

comparing 96 & 29

swap takes place…….

j 3

comparing 29 & 27

swap takes place…….

j 4

comparing 27 & 15

swap takes place…….

currently grades are [7, 15, 96, 29, 27]

i 2

j 3

comparing 96 & 29

swap takes place…….

j 4

comparing 29 & 27

swap takes place…….

currently grades are [7, 15, 27, 96, 29]

i 3

j 4

comparing 96 & 29

swap takes place…….

currently grades are [7, 15, 27, 29, 96]

number of comparisons made 10

in other words, given [96, 29, 27, 7, 15], in the first round of comparing…

compare 96 & 29 >> [29, 96, 27, 7, 15]

compare 29 & 27 >> [27, 96, 29, 7, 15]

compare 27 & 7 >> [7, 96, 29, 27, 15]

compare 7 & 15 >> [7, 96, 29, 27, 15]

compare and swap with the first element

*the first number is always in the right order (aka the smallest number).*

Bam! I am old school or what? I was stuck in this mind set >>

compare 96 & 29 >> [29, 96, 27, 7, 15]

compare 96 & 27 >> [29, 27, 96, 7, 15]

compare 96 & 7 >> [29, 27, 7, 96, 15]

compare 96 & 15 >> [29, 27, 7, 15, 96]

compare and swap with the current element

**the last number is always in the right order (aka the biggest number).**

now is this method necessarily comparing two “adjacent” numbers? hmmm…

————– Bubble Sort? ————–

grades: [60, 45, 55, 86, 60]

comparing 60 & 45 >> [45, 60, 55, 86, 60]

comparing 45 & 55 >> [45, 60, 55, 86, 60]

comparing 45 & 86 >> [45, 60, 55, 86, 60] nope

comparing 45 & 60 >> [45, 60, 55, 86, 60] nope

so is this still considered a “bubble” sort? hmmm…

anyway here is my take on the “traditional” bubble sort

def old_bubble_sort(n)
grades = rndm_grades(n)
compare = 0
sorted = false
until sorted
sorted = true
for i in (0..n-2)
compare +=1
if grades[i] > grades[i+1]
grades[i], grades[i+1] = grades[i+1], grades[i]
sorted = false
end
end
n -=1
end
end

————– Bubble Sort? ————–

grades: [67, 90, 17, 27, 80]

comparing 67 & 90 >> [67, 90, 17, 27, 80]

comparing 67 & 17 >> [17, 90, 67, 27, 80]

comparing 17 & 27 >> [17, 90, 67, 27, 80]

comparing 17 & 80 >> [17, 90, 67, 27, 80]

comparing 90 & 67 >> [17, 67, 90, 27, 80]

comparing 67 & 27 >> [17, 27, 90, 67, 80]

comparing 27 & 80 >> [17, 27, 90, 67, 80]

comparing 90 & 67 >> [17, 27, 67, 90, 80]

comparing 67 & 80 >> [17, 27, 67, 90, 80]

comparing 90 & 80 >> [17, 27, 67, 80, 90]

sorted grades are [17, 27, 67, 80, 90]

number of comparisons made: 10

————– “Traditional” Bubble Sort ————–

grades: [67, 90, 17, 27, 80]

compare 67 & 90 >> [67, 90, 17, 27, 80]

compare 90 & 17 >> [67, 17, 90, 27, 80]

compare 90 & 27 >> [67, 17, 27, 90, 80]

compare 90 & 80 >> [67, 17, 27, 80, 90]

compare 67 & 17 >> [17, 67, 27, 80, 90]

compare 67 & 27 >> [17, 27, 67, 80, 90]

compare 67 & 80 >> [17, 27, 67, 80, 90]

compare 17 & 27 >> [17, 27, 67, 80, 90]

compare 27 & 67 >> [17, 27, 67, 80, 90]

sorted grades are [17, 27, 67, 80, 90]

number of comparisons made: 9

lots of different ways to implement this… what’s your take?