Showing posts with label quicksort. Show all posts
Showing posts with label quicksort. Show all posts

Saturday, June 16, 2012

Sorting data with Fuzuli

In this article, I want to show how to sort data vectors using Bubble sort and Quick sort. Bubble sort is known to be one of the most in-efficient sorting algorithms. Quick sort has lower order of magnitude and it is known to be the most efficient one. There are tons of articles about these algorithms around the Internet and I don't want to give a detailed description and comparison of them.


Let me show how to write them in Fuzuli.



Bubble Sort in Fuzuli:


(def mylist LIST)
(let mylist (list 5 6 4 2 3 9 1 10 5))

(print "Original List:\n")
(print mylist "\n")

(for (let i 0) (< i (length mylist)) (inc i)
    (for (let j (clone i)) (< j (length mylist)) (inc j)
        (if (> (nth mylist i) (nth mylist j))
            (block
            (let temp (nth mylist i))
            (set mylist i (nth mylist j))
            (set mylist j temp)
            )
        )
    )
)

(print "After sorting:\n")
(print mylist "\n")


The output is :

Original List:
[5, 6, 4, 2, 3, 9, 1, 10, 5]

After sorting:
[1, 2, 3, 4, 5, 5, 6, 9, 10] 

 The code is similar to one written in both Lisp, C or Java! Hope the taste of code is good for you. Next one is the Quick sort:

Quick Sort in Fuzuli:


(def mylist LIST)
(let mylist (list 5 6 4 2 3 9 1 10 5))

(print "Original List:\n")
(print mylist "\n")



(function partition (params arr left right)
 (block
  (def i INTEGER) (def j INTEGER)(def tmp INTEGER)
  (def pivot INTEGER)
  (let i (clone left)) (let j (clone right))
  
  (let pivot (nth arr (/ (+ left right) 2)))
  

  (while (<= i  j)
   (block
             (while (< (nth arr i) pivot)(inc i))
                (while (> (nth arr j) pivot) (-- j)) 
       (if (<= i  j) 
     (block
            (let tmp  (nth arr i)) 
               (set arr i (nth arr j))
               (set arr j  tmp)
               (++ i)
               (-- j)
        )
    )
   )
  )
  (return i)
 )
)


(function quicksort (params arr left right) 
 (block
  (def index INTEGER)
  (let index (partition arr left right))
  (if (< left  (- index 1))
     (block
             (quicksort arr left  (- index 1))
   )
  )

       (if (< index right)
   (block
             (quicksort arr  index  right)
   )
  )
 )
)

(quicksort mylist 0 (- (length mylist) 1))
(print "After sorting:\n")
(print mylist "\n")


The output is :

Original List:
[5, 6, 4, 2, 3, 9, 1, 10, 5]

After sorting:
[1, 2, 3, 4, 5, 5, 6, 9, 10]

which is the same for bubble sort but the latter is faster.

Hope you like the code. See you next!