1. Introduction
Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The process is repeated until the list is sorted.
2. Implementation Steps
1. Start at the beginning of the list.
2. Compare the first two elements.
3. If the first element is greater than the second element, swap them.
4. Move on to the next pair of elements and compare them. Swap if necessary.
5. Continue this process for each pair of adjacent elements until the end of the list is reached.
6. After the end of the list is reached, start again from the beginning and repeat the process.
7. Continue passing through the list until no swaps are made.
3. Implementation in Ruby Programming
def bubble_sort(arr)
n = arr.length
# Outer loop for traversal
for i in 0...n
swapped = false
# Inner loop for comparison and swapping
for j in 0...n-i-1
if arr[j] > arr[j+1]
arr[j], arr[j+1] = arr[j+1], arr[j] # Swap the elements
swapped = true
end
end
# If no swaps are made in the inner loop, the array is already sorted
break unless swapped
end
arr
end
# Client code
array = [64, 34, 25, 12, 22, 11, 90]
puts "Original Array: #{array}"
sorted_array = bubble_sort(array)
puts "Sorted Array: #{sorted_array}"
Output:
Original Array: [64, 34, 25, 12, 22, 11, 90] Sorted Array: [11, 12, 22, 25, 34, 64, 90]
Explanation:
1. Bubble Sort is a straightforward sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order.
2. The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
3. For each pass through the list, the algorithm compares each pair of adjacent elements and swaps them if necessary.
4. After each pass, the largest element (or the bubble) will have bubbled to its correct position at the end of the list.
5. This process continues until no swaps are needed, indicating that the list is sorted.
6. Despite its simplicity, Bubble Sort is not very efficient for large lists compared to other sorting algorithms.
Comments
Post a Comment