Selection Sort Algorithm in Java and Python

The next definition is from Wikipedia:

"In computer science, a Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited."

It mentions also they are variants of this algorithm: heapsort, cocktail sort, bingo sort.

Also there is a table where n is the number of records to be sorted. The columns "Average" and "Worst" give the time complexity in each case.

Name	Best	Average	Worst
Selection sort

Now, here the code in Java (take in account that I will implement the same interface and use the same tool class and it was defined in Insertion Sort Algorithm).

package melg.algorithms.sorting;

/**
 * @author Manuel Loayza
 * 
 */
public class SelectionSortAlgorithm implements ISorting {

 private long runningTime = 0;
 private long numberOfIteration = 0;

 /**
  * Implementation of Selection sort Algorithm
  * 
  * @param array
  *            array object of long values to be sorted.
  * @return the sorted array
  */
 public long[] makeSorting(long[] array, boolean debug) {
  runningTime = System.nanoTime();
  int initPosition = 0, minPosition = 0;
  for (initPosition = 0; initPosition < (array.length - 1); initPosition++) {
   minPosition = initPosition;
   if (debug) {
    System.out.format("Reviewing the %d element (%d)\n",
      initPosition + 1, array[initPosition]);
   }
   for (int j = initPosition + 1; j < array.length; j++) {
    if (array[j] < array[minPosition]) {
     minPosition = j;
    }
    numberOfIteration++;
   }
   if (minPosition != initPosition) {
    // swapping the values
    long temp = array[minPosition];
    array[minPosition] = array[initPosition];
    array[initPosition] = temp;
    if (debug) {
     System.out.format("There is a min value: (%d)\n",
       array[initPosition]);
     SortUtilAlgorithm.showArray(array);
    }
   }
   numberOfIteration++;
  }
  runningTime = System.nanoTime() - runningTime;
  return array;
 }

 @Override
 public String getStats() {
  return SortUtilAlgorithm.getStats(runningTime, numberOfIteration);
 }

 public static void main(String... args) {
  long array[] = SortUtilAlgorithm.genereteArray(20, 100);
  System.out.println("Source array has a size of : " + array.length);
  SortUtilAlgorithm.showArray(array);
  ISorting algorithm = new SelectionSortAlgorithm();
  array = algorithm.makeSorting(array, false);
  SortUtilAlgorithm.showArray(array);
  System.out.println(algorithm.getStats());
 }
}

For the code in Python, I have using an abstract and a little variation of the Template Pattern. Python do not use interface because it allows multiple inheritance, so it does not need the use of interfaces like Java.
The template class is named SortingBase, as it is defined as following:

'''
Created on 21/03/2012

@author: Manuel Loayza
@contact: mloayzagahona at gmail dot com
'''

import math
from random import random 
from decimal import Decimal

class SortingBase(object):
    '''
    classdocs
    '''

    def __init__(self):
        '''
        Constructor
        '''
        self.numberOfIterations = 0
        self.runningTime = Decimal('0')
        
    '''
    Shows the array in the console
    '''
    def showArray(self, array):
        size = len(array)
        string = "["
        for i in range(0, size):
            string = string + "%s" % array[i]
            if i != (size - 1) :
                string = string + ","
            else:
                string = string + "]"
        print(string)

    '''
    Show statistics information
    '''
    def getStats(self):
        stats = 'Time of Execution:\t {0:.30f} s.\n'.format(self.runningTime)
        stats += 'Number of Iterations:\t {0}.\n'.format(self.numberOfIterations)
        return stats

    def generateArray(self, factorSize, factorMaxValue):
        array = []
        items = int(math.floor(random() * factorSize))
        for i in range (0, items):
            array.append(int(math.floor(random() * factorMaxValue)))    
        return array
 
    def makeSorting(self, array, debug):
        raise NotImplementedError( "Should have implemented this" )
    

The selection sort class python is:

'''
Created on 21/03/2012

@author: Manuel Loayza
@contact: mloayzagahona at gmail dot com

'''
import time
from decimal import getcontext, Decimal
from melg.algorithms.sorting.algorithmbase import SortingBase

class SelectionSortAlgorithm(SortingBase):
    def __init__(self):
        SortingBase.__init__(self)
        getcontext().prec = 22
        self.start = None
        self.end = None
        
    '''
    Implementation of the Selection Sort Algorithm
    '''
    def makeSorting(self, array, debug):
        self.start = Decimal(time.time())
        #print self.start
        size = len(array)
        initPosition = 0
        minPosition = 0
        for initPosition in range(size - 1):
            minPosition = initPosition
            if debug:
                print("Reviewing the {0} element {1}".format(initPosition + 1, array[initPosition]))
            for j in range(initPosition + 1, size):
                if array[j] < array[minPosition]:
                    minPosition = j
                self.numberOfIterations += 1
            if minPosition != initPosition:
                temp = array[minPosition]
                array[minPosition] = array[initPosition]
                array[initPosition] = temp
                if debug:
                    print("There is a min value: {0}".format(temp))
                    self.showArray(array)
            self.numberOfIterations += 1
            
        self.end = Decimal(time.time())
        #print self.end
        self.runningTime = self.end - self.start
        return array

if __name__ == "__main__":
    sorting = SelectionSortAlgorithm()
    myarray = sorting.generateArray(20, 100)
    print("The source array has a size of : {0}".format(len(myarray))) 
    sorting.showArray(myarray)
    myarray = sorting.makeSorting(myarray, False)
    print("The sorted target array")
    sorting.showArray(myarray)
    print sorting.getStats()

I'd want finished by making a little comparison between performance between these 2 languages. For arrays with size around less than 100, the time of sorting in Python is almost zero, and in Java is near to 0.001 seconds. But when the array size is bigger, maybe greater than 1500 elements, in Java, time of sorting the array take almost the same time for the previous 100 element, instead Python took around 0.3 seconds. I have done a lot of attempts, and Java always had a better performance than Python for big arrays.

In my next post I will talk about merge sort algorithm.