Quick sort Implementation

The unit purpose of the quicksort is given below. Code is self explanatory and sufficiently commented. So, we have two pointers and a pivot value. Left pointer makes sure it has crossed smaller values, while the right makes sure, it has crossed larger value than the pivot.  When the left pointer points to a larger value and the right pointer points to a smaller value, they swap their values. And at last, the pivot is swapped at the endpoint of the starting pointer. The partition program should be called recursively in the left and right sub arrays, to achieve the Quicksort.

public class Partition {
   public static void main (String[] args) {
      int toSort[] = {32,3,3,45,67,98,89,102,35,45,21,5};
      Partition part = new Partition();
      part.partitionIt(toSort);
      for(int i = 0; i < (toSort.length); i++) {
         System.out.print(toSort[i] + ", ");
      }
   }
   public void partitionIt(int[] numbers) {

      //Let us choose the first value as pivot
      int pivot = numbers[0];

      // Start after the pivot
      int startptr = 1;

      // Start from the endpoint
      int endptr = numbers.length - 1;

      while (endptr >= startptr) {

         // Move right as long as the values are smaller than the pivot
         while (numbers[startptr] <= pivot) {
            startptr++;
         }

         // Move left as long as the values are larger than the pivot
         while (numbers[endptr] > pivot) {
            endptr--;
         }

         //Stop before the pointers cross each other
         if(endptr > startptr) {
            swap(numbers, startptr, endptr);
         }
      }

      // Swap the startptr with that of the pivot
      swap(numbers, 0, startptr-1);
   }

   public void swap(int[] numbers, int x, int y) {
      numbers[x] = numbers[x] + numbers[y];
      numbers[y] = numbers[x] - numbers[y];
      numbers[x] = numbers[x] - numbers[y];
   }
}

To make it generic, we substitute variables in the place of mere numbers used and insert a quicksort function as shown.

public void quicksort(int[] numbers) {
partitionIt(numbers, 0, numbers.length - 1);
}

public void partitionIt(int[] numbers, int start, int end) {
//Let us choose the first value as pivot
int pivot = numbers[start];
// Start after the pivot
int startptr = start+1;
// Start from the endpoint
int endptr = end;
/**
Function unaltered
**/
// Swap the startptr with that of the pivot
swap(numbers, start, startptr-1);
}

Ok, This does the same partition, but partition the left and right sub array divided by the pivot value in between. For doing that, return the pivot value’s index , so that the left and right sub arrays has its endpoint and startpoint. Add a base case. Also include a condition if the first value is the largest value, otherwise you might end up in ArrayIndexOutOfBound Exception.

public class Partition {
   public static void main (String[] args) {
      int toSort[] = {1000, 1100, 32, 3, 3, 45, 67, 9008, 809, 102, 35, 415, 670, 45,21,5};
      Partition part = new Partition();
      part.quicksort(toSort, 0, toSort.length - 1);
      for(int i = 0; i < (toSort.length); i++) {
         System.out.print(toSort[i] + ", ");
      }
   }

   public void quicksort(int[] numbers, int start, int end) {
      // If this condition is not there, stack overflows, remember the 'base case'
      if(end <= start) {
         return;
      }
      int pivot = partitionIt(numbers, start, end);
      quicksort(numbers, start, pivot -1);
      quicksort(numbers, pivot+1, end);
   }

   public int partitionIt(int[] numbers, int start, int end) {
      //Let us choose the first value as pivot
      int pivot = numbers[start];
      // Start after the pivot
      int startptr = start+1;
      // Start from the endpoint
      int endptr = end;
      while (endptr >= startptr) {
         // Keep moving right as long as the value is smaller than the pivot
         // (startptr <= end) is inserted because, if the first value is the largest, then the startptr keeps on incrementing
         while ((startptr <= end) && numbers[startptr] pivot) {
            endptr--;
         }
         //Stop before the pointers cross each other
         if(endptr > startptr) {
            swap(numbers, startptr, endptr);
         }
      }
      // Swap the startptr with that of the pivot
      swap(numbers, start, startptr-1);
         return startptr - 1;
      }

   public void swap(int[] numbers, int x, int y) {
      if(numbers[x] == numbers[y]) {
         return;
      }
      numbers[x] = numbers[x] + numbers[y];
      numbers[y] = numbers[x] - numbers[y];
      numbers[x] = numbers[x] - numbers[y];
   }

}

Analyzing Quicksort’s Big O and about space complexity in the next post…..

Quick sort – As you name it

Quick sort is the next sorting technique, I would like to analyze in this post. How to sort quickly? The array is recursively divided into two parts with a pivot value. The division is such that, the left part will contain values less than the pivot value and the right part will contain values greater than the pivot value. This is done recursively. (As a self-taught programmer, Recursion is something you encounter in your programming tasks. Every Recursion should have a stop condition that is also known as a ‘base case’ and a basic function that it intends to do. Otherwise, recursion executes forever and your stack memory overflows. Because stack memory is the one, dealing with the overheads caused by function calls and arguments, usually)

To start with, a pivot value must be chosen. A pivot value can be at any position in the array to be sorted. But usually the last term or the first term is chosen in order to reduce the complexity.

Recursion:

Having outlined the algorithm, let us brush up our ‘Recursion’ a bit. A program to find the factorial of a given number is good to start with. Consider this factorial program below. Factorial can be calculated as x-1 * x-2 * x-3 …. till x=1. This can be mathematically expressed as:

 n! = \begin{cases} 1 & \text{if } n = 0, \\ (n-1)!\times n & \text{if } n > 0. \end{cases}

Factorial calculated in an iterative way:
public class Factorial {
public static void main(String args[]) {
Factorial factobj = new Factorial();
int factorial = factobj.fact(5);
System.out.println("Factorial: " + factorial);
}

public int fact(int i) {
int factorial = 1;
for(int j = i; j > 1; j--) {
factorial = factorial * j;
}
return factorial;
}
}

Mathematically, The common operation in a Factorial is x! = x * (x-1)!

The second step if substitued x! = x * ((x-1) * ((x-1)-1)!). The x-1 is continuously fed to the function until x value is reduced to 1. So x * (x-1)! is the core intention or the unit purpose of this function. So let us rewrite our factorial method in a recursive way.

public int fact(int i) {
if (i < 1) {
return 1;
}
return i * fact(i-1);
}

Now you feel recursion is more mathematically inclined and easy to implement. But it has its side effects too for not being efficient like possible stack-overflow error.

Back to Quicksort:

The array is recursively divided into a lesser and greater parts with reference to a pivot value. Consider this simple example:

An array of five numbers – {32,3,45,21,5} pivot value – 32

Our indent is to insert the 32 as a pivot value in its correct index, within the list of five numbers. – {5, 3, 21, 32, 45}. Then split the list as {5, 3, 21} and {45}.

In the left part, 5 is the pivot value. After second pass – {3, 5, 21}. Again, separate the list into {3} and {21}. Then do nothing.This is an example of in-place quick sort which reduces space complexity.

How to transform this logic into code? What is the unit purpose of this Algorithm in order to do it recursively? What is space complexity?

- To be continued

Binary search

Binary search is the efficient search mechanism with one precondition that the input should be an sorted array. The following binary search returns the index of the search item, otherwise -1. Binary search is dividing the array into two parts continuously until we find the search term. First we point to the middlemost term and check whether that is the term we are searching for. If that is the search term return it, otherwise check if the term we search for is lesser or greater than the middle term. If its lesser that the middle term, proceed the same process with the left part, otherwise proceed with the right part.

public class BinarySearch {
    
    public static void main (String args[]) {
        int []b={7,19,21,32,39,42,51,78,88,141,150};
        int result = search(b,141);
        System.out.println(“Result ” + result);
    }
    
    public static int search (int[] a, int b) {
        int result = -1;
        int lowerbound = 0;
        int upperbound = a.length – 1;
        while(upperbound-lowerbound != 0) {
            int currpos = (lowerbound + upperbound) / 2 ;
            System.out.println(“currpos: ” + currpos);
            if(a[currpos] == b) {
                return currpos;
            } else if(a[currpos] > b) {
                upperbound = currpos – 1;
            } else {
                lowerbound = currpos + 1;
            }
        }
        return result;
    }
}

For the range of 10 numbers, comparisons needed are 4. For a range of 100 its 7, for 1000 its 10. So, we need to model the Big-O-notation for this operation. Analyzing the relationship between the range of numbers and the comparisons, we get the following table. It tells that an array containing more than 8 and upto 16 numbers need 4 comparisons, In our case we had 10 numbers, we needed 4 comparisons

comparisons                Range of array       Power of 2

1                                        2                          1

2                                        4                          2

3                                        8                          3

4                                       16                         4

5                                       32                         5

6                                       64                         6

7                                     128                         7

8                                     256                         8

This boils down to the fact it can be expressed as log2(16) = 4 similar to log10(10000) = 4

Hence Big-O-notation may be O(log n) for the worst case scenario.

Algorithms

What is an Algorithm? Well, you can google for a definition.

Basic algorithm that’s too bad on analysis is Bubble sort. Sorting is always useful in case of implementing searching or eliminating duplicates. Bubble sorting is one of the easiest algorithm anyone can pick up even without a programming knowledge.

The Algorithm is implemented in the Java Language:

class BubbleSort {

public static void main(String args[]){
int []b={21,141,32,51,42,19,7,39,88,78};
int limit = b.length;
for(int i = 0; i < limit-1; i++) {
for(int j = 0; j < limit-1; j++) {
if(b[j] > b[j+1]) {
int temp = b[j];
b[j] = b[j+1];
b[j+1] = temp;
}
}
System.out.print(“Pass ” + (i+1) + “: “);
for(int k = 0; k < limit; k++) {
System.out.print(b[k] + “,”);
System.out.print(“\n”);
}
}
}

This is the rough implementation of the Bubblesort in Java. This is neither the perfect implementation nor its object oriented. But this is what, I came up with without looking at any source. Well you can still make the swap as a new method and the bubble sort too.The output printed for each pass by executing the above program.

Pass 1: 21,32,51,42,19,7,39,88,78,141,
Pass 2: 21,32,42,19,7,39,51,78,88,141,
Pass 3: 21,32,19,7,39,42,51,78,88,141,
Pass 4: 21,19,7,32,39,42,51,78,88,141,
Pass 5: 19,7,21,32,39,42,51,78,88,141,
Pass 6: 7,19,21,32,39,42,51,78,88,141,
Pass 7: 7,19,21,32,39,42,51,78,88,141,
Pass 8: 7,19,21,32,39,42,51,78,88,141,
Pass 9: 7,19,21,32,39,42,51,78,88,141,

I am sure that there is no need to explain this bubble sort. But, we shall learn two important things from this implementation. They are Big-O and Invariants. By looking at the output, you can spot the invariant somehow. Invariant means something or some condition doesn’t change for the whole execution of the algorithm.
Notice in the first pass the last element is sorted. For the second pass, the last and its previous elements are sorted. This condition is the invariant here.

Next, Big-O notation which is the asymptotic analysis of an algorithm. This is the performance indicator and it describes the efficiency of the algorithm for larger input. Let us examine this bubble sort, how many times we iterate the array and compare two values in each pass. Its 9 in the first pass and decreases by one in every pass. So its

9+8+7+6+5+4+3+2+1=45 => (n-1)+(n-2)…..+1 = n(n-1)/2

n^2/2 approximately for large n values, We also have another operation i.e swap. At max, the total swaps will be half time as the comparisons, we get N^2/4 or even N^2/2 itself. So, by ignoring the /4 and /2 we get O(N^2) as the big-o-notation for bubble sort.

Hu(a)rray

Array – Arrays are the basic Data structure.

Arrays are used to store a group of values. Arrays are represented in different ways in different languages. Operations on Arrays also varies. Let us examine Arrays in three different languages like Java, Python and Javascript.

Java is Object oriented, static and strongly typed and compiled language.

Python is Object oriented, functional, dynamic and strongly typed and interpreted server-side and scipting language.

Javascript is Prototype based, dynamic and weakly typed and interpreted scripting language.

In Java:

Arrays are passed by value across functions. Array size need to be conveyed to the compiler before hand. Array type should be specified while declaring. An Array doesn’t grow in Java.

Declaration:

You should read that ‘sample’ is the reference variable that holds an integer array.

int[] sample;  // this is preferred

int sample[];

An array is an object in java. Create array like any other object using new operator.

Initialization:

int[] sample = new int[10];

In Javascript:

Arrays are dynamic. Arrays need not be initialized with a limit value. And more importantly, Arrays can store any data type unlike Java.

var sample = new Array();

or var sample = ["I am String", 221,'c'];

In Python:

Arrays are declared as array(typecode, initializer), where typecode represents each datatype. For Example ‘c’ is used to denote character.

array(‘c’,['hello','hi','world','earth']); – array of Strings

array(‘l’,[6778, 420, 100]); – array of long values

Array methods are in general include reading, inserting, slicing, length, looping, joining and sorting.

Java has a utility class which manipulates Arrays – http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html

Hello world!

This is my second blog. My first 2 bytes would be “Hi All”. I plan to blog here, a series of posts which would serve as a journal for my journey into core Computer science and also other technical areas in general. You are always welcome to join me. Let us explore together. Being a self-taught programmer & a mechanical engineer by education, I was curious to learn Data Structures, Algorithms and Fundamental Mathematics. But, severe procrastination has played a major villain role in disorienting me. At last, I plan to gain an upper hand over it, through my blog. Mine will be a series of organized and linear posts towards Data Structures and Algorithms right from ‘List’ to ‘blah blah’ and ‘bubble sort’ to ‘blah blah’. And, “blah blah” are placeholders :)

But I am glad If you think mine is a worthwhile tech blog and I will be thankful to all of you who will spend a fraction of their lifetime in reading my blog and commenting on my posts. Buzz!!!!!!!!