Bubble Sort Without Loops

Disclaimer: The title of this Story is clickbait.

Lately, I was coding mostly in Imperative languages such as Golang, Python, and Javascript, etc. I was planning to give myself a break from these imperative languages, just for having some fun, and I started playing with Elixir, which I was attracted to because of its concurrency-friendly features. But Elixir didn’t work for me, Although it’s a functional language it feels OOPs Language, can’t explain why.

Then I convinced myself to go with Haskell. Yeah, I know at first it looks scary, but Appearances are deceiving.

So to motivate me further, I watched some Youtube Meets on functional programming languages and Haskell is Queen of Functional Programming languages. I got to know a fact that, Haskell will change the way you think about a problem, I mean computational problem. After reading some books like “Learn you some Haskell for great good”, I finally started playing with it. The first thing I coded was the Bubble Sort algorithm which is a classic CS algorithm for sorting an array in Quadratic time complexity. So In this story, I’ll walk you through the functional way of doing bubble sort, As most of my readers ain’t familiar with Haskell, We will go with python.

Imperative implementation of Bubble sort in python

Let’s deconstruct it

This has 3 major parts,

1. The Upper For Loop at Line 3
2. The Inner For Loop at Line 5
3. The Conditional swap statement at Line 8

To understand the magic let's take an example array [1,0,3,2].

The upper loop helps in slicing the array in a way, that after each iteration of the upper loop the inner loop processes one less element than the last iteration of the upper loop, i.e. On the first iteration of the upper loop inner loop will run 4–1–0 = 3 Times, In second iteration 4–1–1=2, In Third Iteration 4–1–2=1 times, In Fourth Iteration 4–1–3 = 0 Times. That's what it does, it just shortens the array by one element from the right direction so in

1. Iteration array under process = [1,0,3,2]
2. Iteration array under process = [0,1,2]
3. Iteration array under process = [0,1]

Also Mind the bubble sort invariant, “In bubble sort algorithm, after each iteration of the loop largest element of the array is always placed at the rightmost position.”

The inner loop does the real magic, it compares adjacent elements and swaps them if they are out of order and this process continues until the end of the array.

So in [1,0,3,2] The first iteration of inner loop the swapping goes like this

1. a[0] = 1, a[1] = 0, as 1>0 , these elements will be swapped so now a[1] = 0, a[0] = 0.
2. a[1]=1, a[2]=3, as 1 < 3 , no swap will happen, so a[1] = 1, a[2] = 3
3. a[2] = 3, a[3] = 2, as 3>2 so swap will happen, so a[2] = 2, a[3]=3

So after one complete iteration of upper loop, the largest element of under consideration array (3) is at the right most place i.e. at index 3

This process is followed in all the 3 iterations of upper loop. Please read this deconstruction once again, so we can jump into its functional equivalent.

Functional implementation of Bubble Sort

The Functional way of bubble sort

So for implementing it in a functional way, We’ll take the help of our bubby Recursion.

This functional implementation also has 3 major parts

1. Corner case (Line 2): When the array has 0 or 1 element, We’ll just return the incoming array as it is.
2. Corner case (Line 4): When the array has exactly 2 elements, We’ll check if those 2 elements are out of order or not, if they are, we will swap them and will return a new array with their right positions.
3. Main Body (After Line 7): When the array has more than 2 elements, Now we will decompose the array into 3 parts.

a) First Element of the array (i.e .1)

b) Second Part = Second Element of array (i.e. 0)

c) Third Part = Subarray from the Third element. (i.e. [3,2])

Now remember what we did in the inner loop of imperative implementation, we compared adjacent elements and swapped them if they were out of order.

So as after the first iteration of the inner loop are array became [0*,1*,3,2], now what happens at line 13, we did a recursive call to bubble_sort on subarray [1,3,2] and append it to the first element of the original array, it would evaluate as

[0] + bubble_sort( [1] + [3,2] ) => [0] + bubble_sort([1,3,2]) — — -(fn1)

In the next recursion call,

bubble_sort([1,3,2]) evaluates as

• The array has 3 elements, the main body would get executed at line 11, and will evaluate as

[1] + bubble_sort([3]+[2]) => [1] + bubble_sort([3,2]) — — -(fn1.1)

In the next recursion call,

bubble_sort([3,2]) evaluates as

• The array has 2 elements, the second corner case would get executed at line 5, and will evaluate as

[2,3] — — -(fn1.1.1)

so far evaluation in a second recursive call to bubble_sort has became

[1]+[2,3] => [1,2,3] — — (fn1.1)

Now, we will move to line 14, which would evaluate as

bubble_sort([1,2]) + [3] — — (fn1.1)

which will make a recursive call but since [1,2] have only 2 elements it will evaluate to

[1,2] — -(fn1.1.1)

after the second recursion call evaluation is

[1,2]+[3] => [1,2,3] — — (fn1.1)

Now we are out of the first recursion bubble sort body and inside the terminal call of bubble_sort at line 11, and evaluation has become,

res = [0]+[1,2,3] => [0,1,2,3] — — (fn1)

at line 14 expression will evaluate as

bubble_sort([1,0,3,2]) = bubble_sort([0,1,2]) + [3] — — (1)(fn1)

Did you got the gist, it's like completing one single iteration of the upper loop (in imperative implementation), as the biggest element of the array under consideration has been replaced at the rightmost place, following the bubble sort invariant.

Further, bubble_sort([0,1,2]) = bubble_sort([0,1]) + [2] — — (2)(fn1.1)

Subsituting Eq(2) in Eq(1).

bubble_sort([1,0,3,2]) = bubble_sort([0,1]) + [2] + [3] — — (3)(fn1)

Now, bubble_sort([0,1]) = [0,1] — -(4)fn(1.1)

Substituting Eq(4) in Eq(3).

bubble_sort([1,0,3,2])= [0,1] + [2] + [3] — — fn(1)

= [0,1,2,3]

Hurray! You just bubble sort an array in a purely functional manner.

The gist of this story is, “Functional programming gives you a new dimension to think about”, here we applied the Divide and Conquer Strategy to bubble sort an array.

— — Stay Tuned for more fun with functional programs.

Haskell implementation of Bubble Sort the real motivation behind this story