Bubble Sort Algorithm
The Bubble Sort Algorithm is a simple and widely known sorting algorithm used to sort elements in an array, list, or any other data structure. The algorithm works by repeatedly iterating through the list and comparing each adjacent pair of elements. If the elements are out of order, they are swapped, and the process continues until the entire list is sorted. Bubble Sort gets its name from the way smaller elements "bubble" to the top of the list (i.e., the beginning of the array) as larger elements "sink" to the bottom (i.e., the end of the array) during the sorting process. This algorithm has a straightforward implementation and is easy to understand, making it an excellent choice for teaching sorting concepts to beginners.
However, Bubble Sort Algorithm has its limitations, as it is not the most efficient sorting algorithm for large datasets. It has a worst-case and average-case time complexity of O(n^2), where n is the number of items being sorted. This means that the algorithm's performance degrades substantially as the size of the input increases. In practical applications, other sorting algorithms such as Quick Sort, Merge Sort, or Heap Sort are often preferred due to their better performance characteristics. Despite its limitations, Bubble Sort Algorithm remains a fundamental sorting technique and serves as a great introduction to the world of algorithms and computer science.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Bubble Sort http://en.wikipedia.org/wiki/Bubble_sort
*
* Worst - O(n^2)
* Best - O(n)
* Average - O(n^2)
*
* -Notes-
*
* This is a functional implementation of standard bubble sort. There are two lists which represent
* source and result lists correspondingly. So, the 'bubble' function performs element-wise swaps and
* bubbles the greater element to the last position in the source list. This element should be transferred
* to the head of result list (which is Nil by default). The interesting thing here is that source list
* was reversed and we have to reverse it back to origin order. But, we didn't do that, since we don't
* care about source data which is still unsorted. We only have to keep sorted data in a right order.
*
* Thus this implementation fits into standard requirements about performance. Also, it works in O(n)
* for lists which are already sorted.
*/
def bubblesort[A <% Ordered[A]](list: List[A]): List[A] = {
def sort(as: List[A], bs: List[A]): List[A] =
if (as.isEmpty) bs
else bubble(as, Nil, bs)
def bubble(as: List[A], zs: List[A], bs: List[A]): List[A] = as match {
case h1 :: h2 :: t =>
if (h1 > h2) bubble(h1 :: t, h2 :: zs, bs)
else bubble(h2 :: t, h1 :: zs, bs)
case h1 :: Nil => sort(zs, h1 :: bs)
}
sort(list, Nil)
}
