How to do bubble sort in Haskell

Bubble sort is a simple brute-forceAn exhaustive approach that systematically checks all possible solutions or combinations without employing specific optimization techniques. sorting algorithm that compares the adjacent elements in a list (or an array) and swaps them if they are in the wrong order. The algorithm keeps repeating this process until all the elements are in the expected order (ascending or descending).

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:

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] -> Bool
isSorted [] = True
isSorted [x] = True
isSorted (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 = do
  let unsortedList = [4,3,5,2]
  putStrLn "Unsorted list:"
  print unsortedList
  let sortedList = bubbleSortMain unsortedList
  putStrLn "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.

Complexity

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