Bubble sort is a simple
For example, if we have a list of numbers, say [4,3,5,2]
, and we want them in ascending order, then the following slides describe how the bubble sort algorithm would do the job:
Note: Read more about bubble sort algorithm.
Here's how you implement bubble sort in Haskell:
bubbleSort :: Ord a => [a] -> [a]bubbleSort [] = []bubbleSort [x] = [x]bubbleSort (x:y:xs) = if x > y then y : bubbleSort (x:xs) else x : bubbleSort (y:xs)isSorted :: Ord a => [a] -> BoolisSorted [] = TrueisSorted [x] = TrueisSorted (x:y:xs) = if x > y then False else isSorted (y:xs)bubbleSortMain :: Ord a => [a] -> [a]bubbleSortMain list = if isSorted list then list else bubbleSortMain (bubbleSort list)main :: IO ()main = dolet unsortedList = [4,3,5,2]putStrLn "Unsorted list:"print unsortedListlet sortedList = bubbleSortMain unsortedListputStrLn "Sorted list:"print sortedList
Lines 1–4: The bubbleSort
function performs a single iteration by traversing the entire list
and swapping elements out of order in one go. To continue with the next iteration, we need to call the bubbleSort
function again, which is done within the bubbleSortMain
function.
Lines 6–9: isSorted
function examines the elements of the list
and checks if they are in ascending order. It returns True
if the list is sorted, otherwise False
. This function is utilized in the bubbleSortMain
function to decide whether further sorting is necessary.
Lines 11–12: In bubbleSortMain
function, if isSorted
returns True
, indicating that the list
is already sorted, it will stop and return the sorted list. If the isSorted
function returns False
, implying that the list
is not sorted, the bubbleSortMain
function proceeds with additional sorting iterations using bubbleSort
.
Lines 14–22: The main
function is used to test the bubbleSortMain
function. Initially, the unsorted list
is printed to display its original order. Then, the unsorted list
is passed as input to the bubbleSortMain
function. The bubbleSortMain
function performs the sorting process and returns the sorted list
. Finally, the sorted list
is printed to show the result of the sorting operation performed by bubbleSortMain
.
Since bubble sort algorithm is a brute-force approach, it's complexity is O(n^2)
where n
represents the number of elements in the list being sorted. This indicates that the time it takes to execute bubble sort grows quadratically with the input size.
Note: Read about merge sort algorithm in Haskell which does the similar job but in
O(nlogn)
complexity.
Free Resources