Sorting Algorithms Comparison and Quicksort example

Today I’ve remembered those days back in University, when we learned Algorithms and Data Structures. Among the big amount of algorithms we studied, there were the sorting algorithms. The first algorithm introduced was the Bubble Sort, the worst efficient one. Afterwards, the most efficient algorithms were introduced: Merge Sort and Quicksort. Let’s remember the basics of these algorithms.

Bubble Sort

This is the simplest algorithm, however it’s the worst one in performance speaking. The average and worst case complexity are both O(n²). But there is good news, its complexity, for the best case, is only O(n). Here there is an animation that explains how it works: Bubble Sort Animation.

Merge Sort

The Merge Sort algorithm is better than Bubble Sort. The average and worst case complexity is O(nlogn). The best case (when the array is sorted) is also O(nlogn), but with some optimizations can be reduced to O(n). Here you can find another animation Merge Sort.

Quicksort

The Quicksort algorithm is usually faster than Merge Sort, despite they have the same average case complexity O(nlogn). However, the complexity for the worst case is O(n²), with some improvements it can be reduced. Here there is an animation: Quicksort.

Implementation Quicksort

After this brief comparison between sorting algorithms, let’s see the implementation of Quicksort algorithm in Java and Scala.

Java

This is the implementation in Java of the Quicksort algorithm:

public static void sort(int[] xs){
	sort(xs,0,xs.length-1);
}
public static void sort(int[] xs, int left, int right){
	int pivot = xs[(left+right)/2];
	int i = left;
	int j = right;
	while(i <= j){
		while(xs[i] < pivot){
			i++;
		}
		while(xs[j] > pivot){
			j++;
		}
		if(i<=j){
			int sw = xs[i];
			xs[i] = xs[j];
			xs[j] = sw;
			i++;
			j--;
		}
	}
	if(left < j){
		sort(xs,left,j);
	}
	if(j < right){
		sort(xs,i,right);
	}
}

Scala

First the algorithm in a no functional way, as you could see, this implementation is equivalent to Java’s:

def sort(xs: Array[Int]) {
	def swap(i: Int, j: Int) {
		val t = xs(i); xs(i) = xs(j); xs(j) = t
	}
	def sort1(l: Int, r: Int) {
		val pivot = xs((l + r) / 2)
		var i = l; var j = r
		while (i <= j) {
			while (xs(i) < pivot) i += 1
			while (xs(j) > pivot) j -= 1
			if (i <= j) {
				swap(i, j)
				i += 1
				j -= 1
			}
		}
		if (l < j) sort1(l, j)
		if (j < r) sort1(i, r)
	}
	sort1(0, xs.length - 1)
}

And now, let’s rewrite it in a functional way:

def sort(xs: Array[Int]): Array[Int] = {
	if (xs.length <= 1) xs
	else {
		val pivot = xs(xs.length / 2)
		Array.concat(
			sort(xs filter (pivot >)),
			xs filter (pivot ==),
			sort(xs filter (pivot <)))
	}
}

Getters & Setters and its goodness and evilness

If you are a DZone reader, you will have read many posts about getters and setters and its evilness. Getters and setters are the response to an old Object Oriented principle which says that object’s implementation must not be exposed. On the other hand, there is also another old principle called Uniform Access Principle which says that client code should not be affected by a decision to implement an attribute as a method or field. Unfortunately, Java doesn’t follow this last principle.

Don’t Expose the Implementation

Currently, the most used IDE’s can generate the getters and setters for fields. Sometimes this doesn’t help, and developers automatically generate unnecessary getters and/or setters. This next example could be seen as a situation where generating getters and setters automatically is a bad practice:

package com.wordpress.j2eethoughts.ooPrinciples;
public class Odometer{
    private BigDecimal total;
    private BigDecimal partial;
    public Odometer (){
        total = BigDecimal.ZERO;
        partial = BigDecimal.ZERO;
    }

    public BigDecimal getTotal(){
       return total;
    }
    public void setTotal(BigDecimal total){
       this.total = total;
    }

    public BigDecimal getPartial(){
       return partial;
    }
    public void setPartial(BigDecimal partial){
       this.partial = partial;
    }
}

Now let’s explain because this is a bad practice. Maybe at a first glance, you may think that this implementations satisfies the principle of not expose the internal implementation of the object. Unfortunately, this is not true, everything is exposed. There isn’t much difference between this implementation with getters and setters and the hypothetical implementation with public fields. In addition, you can do illegal things with this implementation, as decrement the number of Kilometres of the Odometer. The unique advantage between this implementation and one with public fields is that you could attach some functionality in any function, like logging, checking permissions…

A more correct implementation for this class would be:

package com.wordpress.j2eethoughts.ooPrinciples;
public class Odometer{
    private BigDecimal total;
    private BigDecimal partial;
    public Odometer (){
        total = BigDecimal.ZERO;
        partial = BigDecimal.ZERO;
    }
    public BigDecimal getTotal(){
       return total;
    }
    public BigDecimal getPartial(){
       return partial;
    }

    public void resetPartial(){
       partial = BigDecimal.ZERO;
    }
    public void increment(BigDecimal inc){
       partial.add(inc.abs());
       total.add(inc.abs());
   }
}

This class implementation ensures that nothing wrong is done with the Odometer, Kilometres can only increase and you can’t rig the Odometer decreasing the total amount of Kilometres made.

Uniform Access Principle

As we have explained before, Java doesn’t satisfy the Uniform Access Principle, for this reason we will explain it using Scala. The client code must not be affected if the developer decides to implement an attribute as a method or as a field. For illustrating this example we will use a Circle class. There will be two different implementations for the attributes perimeter and area.

package com.wordpress.j2eethoughts.uap

import Math.Pi

class CircleVal (radius : Int){
   val perimeter = 2 * Pi * radius
   val area = Pi * radius * radius
}

class CircleDef (radius : Int){
   def perimeter = 2 * Pi * radius
   def area = Pi * radius * radius
}

The client uses these classes exactly the same way in both implementations. The client doesn’t care if the developer had decided to implement these attributes as methods or as fields.

package com.wordpress.j2eethoughts.uap

object Main {
  def main(args : Array[String]) : Unit = {
    val c1 = new CircleVal(4)
    println(c1.perimeter)
    println(c1.area)
    val c2 = new CircleDef(4)
    println(c2.perimeter)
    println(c2.area)
  }
}

This post is not supposed to decide about the evilness or goodness of getters and setters, its only intention is to think about its use. So, we would be very glad if after reading this post, you think twice before ask your IDE to automatically generate the getters and setters.

The power of Lists in Scala

Let me introduce you the piece of code possibly most used in history:

for(int i = 0; i < list1.length() ; i++){
   //do something
}

Since java 1.5 we have a more concise way to do the same, the foreach iteration:

for(Object o : list1){
   //do something
}

If we want to create a list with all elements of list1 that fulfill some condition, we need some boilerplate code:

List list2 = new ArrayList();
for(Integer i : list1){
   if(i > 0){
        list2.add(i);
   }
}

Every time we want to find elements that fulfill some condition, we need to copy this code except for the third line, which has to be adapted.

One of the main goals of Scala is to reduce the boilerplate code that exists in our Java code. To accomplish this goal, there are some higher-order operators, which can take a function as a parameter. Some useful higher-order operators will be described in this post.

Filter

The filter operator takes as operands a list of type List[T] and one function of type T => Boolean called predicate. This operator returns a new list with all elements of the original list for which the predicate is true. With this operator we can, in only one line, do the same that the Java code.

scala> val list1 = List(1,3,4,0,-1,6)
list1: List[Int] = List(1, 3, 4, 0, -1, 6)
scala> val list2 = list1 filter (_ > 0)
res0: List[Int] = List(1, 3, 4, 6)

The list created will contain only the elements of list1 that are greater than 0.

Find

This operator is very similar to filter, except that returns the first element for which the predicate is true. Actually it returns an optional value; this is the Scala approach for nullable objects. If at least one element makes predicate true, it will return Some(T), otherwise None. This approach ensures in compilation time that no optional values are considered as common variables of type T.

scala> list1 find (_ > 0)
res1: Option[Int] = Some(1)
scala> list1 find (_ > 100)
res2: Option[Int] = None

Partition

The partition operator returns a pair of lists. The first one includes all elements that satisfies the predicate. The second includes all elements for which the predicate is false.

scala> list1 partition (_ > 0)
res3: (List[Int], List[Int]) = (List(1, 3, 4, 6),List(0, -1))

TakeWhile

The takeWhile operator iterates the original list until it finds one element that doesn’t satisfy the predicate, all this elements are added in the result list. In other words, it returns the longest prefix such that every element satisfies the predicate.

scala> list1 takeWhile (_ > 0)
res4: List[Int] = List(1, 3, 4)

DropWhile

The dropWhile operator iterates the original list until it finds one element that doesn’t satisfy the predicate, the remaining elements are added in the result list. In other words, it drops the longest prefix such that every element satisfies the predicate.

scala> list1 dropWhile (_ > 0)
res5: List[Int] = List(0, -1, 6)

These are few operations that can help us in our everyday coding. The less lines we code, the less chances of introducing errors we have. In addition, we can avoid repeating the most repetitive and error-prone code.

Scala: Implementing Factory

In a previous post we explained the Design Pattern Factory Method and how it differs from the Builder Pattern. Now we will explain how to implement this pattern in Scala. However, first we need to learn a new concept in Scala: the Companion Objects.

Companion Object

Previously, we said that a Companion Object could be seen, from a Java point of view, as a Static Class.

A Companion Object is an Object that shares the same name and source file with another Class or Trait. A Trait could be seen as a Java Interface.

The Companion Object is useful for implementing utility methods, factories, apply and unapply methods…

When it does exist a Companion, the class is called Companion Class and the object is called Companion Object. This name’s collision is possible because they don’t share the same namespace. While classes are stored in the type namespace, objects are stored in the term namespace. You can read the Scala language specifications here.

Implementing Queue Factory in Java

We want to implement a factory that produces different types of shapes depending on the number of sides given.
First of all, we need the abstract class. In this example it could be an interface, but we could also add some other common properties as fill colour, line colour…

package com.wordpress.j2eethoughts.factory;

public abstract class Shape {
   public abstract double getArea();
   public abstract double getPerimeter();
}

We will work with two different kinds of shapes: triangle and rectangle. Here comes the code for Triangle:

package com.wordpress.j2eethoughts.factory;

public class Triangle extends Shape {
   private double ab;
   private double bc;
   private double ac;
   public Triangle(double ab, double bc, double ac) {
      super();
      this.ab = ab;
      this.bc = bc;
      this.ac = ac;
   }
   @Override
   /**
     * Heron's way
     */
   public double getArea() {
      double s = getPerimeter()/2;
      return Math.sqrt(s*(s-ac)*(s-ab)*(s-bc));
   }
   @Override
   public double getPerimeter() {
      return ab+bc+ac;
   }
}

And this is the source for Rectangle:

package com.wordpress.j2eethoughts.factory;

public class Rectangle extends Shape {
   private double height;
   private double length;

   public Rectangle(double height, double length){
      super();
      this.height = height;
      this.length = length;
   }
   @Override
    public double getArea() {
       return height*length;
    }
    @Override
    public double getPerimeter() {
       return (height*2)+(length*2);
    }
}

And finally, the source of the factory:

package com.wordpress.j2eethoughts.factory;

public class ShapeFactory {
   public static Shape getShape(double len1, double len2,
		double len3){
      return new Triangle(len1,len2,len3);
   }
   public static Shape getShape(double len1, double len2){
      return new Rectangle(len1,len2);
   }
}

After this, we can test this classes with this little application:

package com.wordpress.j2eethoughts.factory;

public class Main {
   public static void main(String[] args) {
      Shape sh1 = ShapeFactory.getShape(32.34, 23);
      System.out.println(sh1.getArea());
      System.out.println(sh1.getPerimeter());
      Shape sh2 = ShapeFactory.getShape(5, 3, 4);
      System.out.println(sh2.getArea());
      System.out.println(sh2.getPerimeter());
   }
}

Implementing Queue Factory in Scala

If we want to implement this shape factory in Scala we will need only one source file. We will use a companion class Shape and a companion object Shape, this last one will act as a factory. Therefore, the concrete implementations of Shape will be private classes of the companion object. With this approach, we hide any concrete implementation of Shape from the client.

This is the source code for the companion class and object.

package com.wordpress.j2eethoughts.queue

import scala.Math.sqrt

abstract class Shape {
  def perimeter : Double
  def area : Double
}

object Shape {
   private class Triangle (ab : Double, bc : Double, ac : Double)
  	extends Shape{
    override val perimeter = ab + bc + ac
    private val s = perimeter / 2
    override val area = sqrt(s*(s-ac)*(s-ab)*(s-bc))
  }
  private class Rectangle (height : Double, length : Double)
  	extends Shape{
    override val perimeter = height * 2 + length * 2
    override val area = height * length
  }

  def apply(ab : Double, bc : Double, ac : Double) : Shape =
    new Triangle(ab,bc,ac)

  def apply(height : Double, length : Double) : Shape =
    new Rectangle(height,length)
}

I would like to make some considerations about this implementation. When we override a method, the keyword override is mandatory, it won’t compile if it’s not included. Furthermore, it’s possible to override a method with a variable. If you look at the concrete classes, the abstract methods defined in Shape are overridden with a val.

Now we will test the Shape Factory:

package com.wordpress.j2eethoughts.queue

object Main {
  def main(args : Array[String]) : Unit = {
    val sh1 = Shape (32.34, 23)
    println(sh1.area)
    println(sh1.perimeter)

    val sh2 = Shape (3,4,5)
    println(sh2.area)
    println(sh2.perimeter)
  }
}