Sorting &Swapping Elements, & Bubble Sort Algorithms!!! [Ruby Programming Language Notes]

Sorting & Swapping Elements, & Bubble Sort Algorithms!!!

Algorithm

• a sequence of actions to take!

Sorting Algorithms

• Swapping Elements Operation:
  • array = [“a”, “b”, “c”, “d”] #let’s swap “a” & “b”
  • temp = array[0]; #save a copy of the first ele
  • array[0] = array[1]; #overwrite the 1st ele with the 2nd ele
  • array[1] = temp; #overwrite the 2nd ele with the 1st ele copy
  • p array # => [“b”, “a”, “c”, “d”]

This works but is a bit messy. Ruby has a clean shortcut (that also works in Python!)!

• array = [“a”, “b”, “c”, “d”] #let’s swap “a” & “b”
• array[0], array[1] = array[1], array[0]
• p array # => [“b”, “a”, “c”, “d”]

There, that was MUCH CLEANER! However, it’s good to understand the old school way because not all languages may have this shortcut.

And this also works for swapping entire variables as well! It can also be applied to sort other data like strings:

• food = “mom’s spaghetti”
• clothing = “sweater”
• food, clothing = clothing, food
• p food # => “sweater”
• p clothing # => “mom’s spaghetti”

Bubble Sort Algorithm!

The Bubble Sort algorithm gets its name because it behaves as if the large numbers “float” to the top of the array like bubbles!

Bubble Sort manipulates the array by swapping the position of two elements, using the swapping elements operation!

• def bubble_sort(array)
  • sorted = false #when this variable is ‘false’, that means the array is not fully sorted yet.
  • while !sorted #while the array is NOT sorted…
    • sorted = true #reset the sorted flag to true
  • (0…array.length -1).each do |i| #1 (see ‘comment-key’ below)
  • if array[i] > array[i+1] #2
    • array[i], array[i+1] = array[i+1], array[i] #3
    • sorted = false #4
  • end
  • end
  • end
• return array
• end

• The ‘comment-key’ to the preceding is:
  • #1–The .each method will perform a single “pass” of bubble sort, and using a range on .each, will let us control how far we go in the given array. Here we want an index of ‘-1’ from the end.
  • #2–…if adjacent elements are out of order, then…
  • #3–…then swap their positions
  • #4–Since we just made a swap, we may need to perform an additional “pass”, so we set the flag to false.

Notes on sorting arrays:

• How would we really check if an array is already sorted programmatically?
• There are really 2 ways to sort numbers, in increasing order or in decreasing order.
• We can iterate through elements of an array, particularly meaning adjacent elements of an array, and check if they’re out of order.
• If they are out of order, we’d return “false”.
• And only after checking every set of adjacent elements do we know that the entire thing is fully sorted.