License Public Domain
Lines 44
Keywords
algorithm (8) JVM languages (3) quicksort (5) sort (5)
Implements this Algorithm
Permissions
Owner: Stou S.
Viewable by Everyone
Editable by All Siafoo Users
Hide
Easily highlight source code for your blog with our Syntax Highlighter. Join Siafoo Now or Learn More

Imperative implementation of QuickSort Atom Feed 0

In Brief A Scala implementation of Quick Sort using imperative programming (i.e. what you are used to). Compare this implementation to the much shorter functional version
# 's
 1/** Quick sort, imperative style */
2object ImperativeQuickSort {
3
4 /** Nested methods can use and even update everything
5 * visible in their scope (including local variables or
6 * arguments of enclosing methods).
7 */
8 def sort(a: Array[Int]) {
9
10 def swap(i: Int, j: Int) {
11 val t = a(i); a(i) = a(j); a(j) = t
12 }
13
14 def sort1(l: Int, r: Int) {
15 val pivot = a((l + r) / 2)
16 var i = l
17 var j = r
18 while (i <= j) {
19 while (a(i) < pivot) i += 1
20 while (a(j) > pivot) j -= 1
21 if (i <= j) {
22 swap(i, j)
23 i += 1
24 j -= 1
25 }
26 }
27 if (l < j) sort1(l, j)
28 if (j < r) sort1(i, r)
29 }
30
31 if (a.length > 0)
32 sort1(0, a.length - 1)
33 }
34
35 def println(ar: Array[Int]) {
36 def print1 = {
37 def iter(i: Int): String =
38 ar(i) + (if (i < ar.length-1) "," + iter(i+1) else "")
39 if (ar.length == 0) "" else iter(0)
40 }
41 Console.println("[" + print1 + "]")
42 }
43
44 def main(args: Array[String]) {
45 val ar = Array(6, 2, 8, 5, 1)
46 println(ar)
47 sort(ar)
48 println(ar)
49 }
50
51}

A Scala implementation of Quick Sort using imperative programming (i.e. what you are used to). Compare this implementation to the much shorter functional version