Bubble sort using Tensorflow

sorting
tensorflow

#1

So here I am, trying to prove a point that tensorflow == numpy In this needless attempt, I will show you an application of a sorting technique “Bubble Sort” using TensorFlow.

A little intro to Bubble Sort; Its the simplest sort you can think of. In this, you are essentially comparing each adjacent value in array again and again till it “sorts itself”

[Image Credits: Bubble Sort wiki Page]

Now let’s jump on to the code!

We can write a pseudocode of our problem as follows:

for i in range(array_length):
  for j in range(array_length - i - 1):
    if current_value > next_value:
      replace(current_value, next_value)
      replace(next_value, current_value)

Now, let’s see our tensors flow!

# import modules
import tensorflow as tf

# create interactive session
sess = tf.InteractiveSession()

# create unsorted array
unsorted_array = tf.Variable([1, 4, 2, 3])
# find length of array
len_array = unsorted_array.get_shape()[0].value

# initialize variables
init = tf.initialize_all_variables()
sess.run(init)

cnt = 0

# bubble sort
for i in range(len_array):
    for j in range(0, len_array - i - 1):
        
        if tf.greater(unsorted_array[j], unsorted_array[j+1]).eval():
            # extract values
            temp1 = unsorted_array[j].eval()
            temp2 = unsorted_array[j + 1].eval()
            
            # replace unsorted array
            unsorted_array = tf.scatter_update(unsorted_array, j, temp2)
            unsorted_array = tf.scatter_update(unsorted_array, j+1, temp1)
            
        print "After iteration", cnt, ':', unsorted_array.eval()
        cnt += 1

Our output is as follows:

After iteration 0 : [1 4 2 3]
After iteration 1 : [1 2 4 3]
After iteration 2 : [1 2 3 4]
After iteration 3 : [1 2 3 4]
After iteration 4 : [1 2 3 4]
After iteration 5 : [1 2 3 4]

Looks like our array is sorted! (I knew that already :expressionless: ) Many improvements could still be done in our code, but for display purposes, I think its ok.

So are you convinced that tensorflow is numpy?


My Random Nonsense!
#2

An optimization is suggested by @BeautifulCodes

So one more optimization is possible. Check if the elements are really getting swapped or not by a flag variable and break the loops if they are not This way your bubble sort will be theoretically more fast.

Through he suggested pseudocode I’ve updated the main code.

# import modules
import tensorflow as tf

# create interactive session
sess = tf.InteractiveSession()

# create unsorted array
unsorted_array = tf.Variable([1, 4, 2, 3])
# find length of array
len_array = unsorted_array.get_shape()[0].value

# initialize variables
init = tf.initialize_all_variables()
sess.run(init)

cnt = 0

# bubble sort
for i in range(len_array):
    isSwapped = False
    for j in range(0, len_array - i - 1):
        
        if tf.greater(unsorted_array[j], unsorted_array[j+1]).eval():
            # extract values
            temp1 = unsorted_array[j].eval()
            temp2 = unsorted_array[j + 1].eval()
            
            # replace unsorted array
            unsorted_array = tf.scatter_update(unsorted_array, j, temp2)
            unsorted_array = tf.scatter_update(unsorted_array, j+1, temp1)
            isSwapped = True
        
        print "After iteration", cnt, ':', unsorted_array.eval()
        cnt += 1

    if isSwapped: break

#3

A feedback from @Sunil sir was to give a resource explaining Bubble Sort in detail. Here’s a resource!


#4

There were requests for performance comparison between TF and Numpy (@kunal Sir, @caiotaniguchi ). I got this result

TF time: 0.2167978286743164
Numpy time: 0.0028018951416015625

Hmmm…it looks like numpy is way better than tensorflow in terms of time complexity.

Well I would argue with this conclusion, as I think there’s still much optimizations that could be done in TF code. Also, there could be hardware dependency on both the implementations, so the results may change. A better survey on this is a must.


#5

Hey, @jalFaizy

How did you implement the sorting for numpy? If you used the built-in sort method, it’s not really a fair comparison with your TF solution, since it’s bound by the for loop performance, which is terrible, while the numpy solution isn’t.


#6

Hello!

I did a manual implementation of bubble sort, mostly similar to the pseudo-code above. Didn’t use python’s inbuilt sort cuz as far as I know it uses adaptive merge sort technique.