Month: May 2020

Merge Sort

by

Merge Sort is a Divide and Conquer algorithm. How this works is, it first divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

The Idea is :

The mergeSort method should recursively sort the subarray array[l..r] i.e. after calling mergeSort(array,l,r) the elements from index l to index r of array should be sorted in ascending order.

Time complexity :

Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array into two halves and take linear time to merge two halves.

MergeSort Code :

class MergeSort {
	
	// Main method
	public static void main(String args[]) {
		int arr[] = { 11, 10, 12, 4, 6, 5 };

		System.out.println("Given Unsorted Array :");
		printArray(arr);

		MergeSort ob = new MergeSort();
		ob.mergeSort(arr, 0, arr.length - 1);

		System.out.println("\nSorted array :");
		printArray(arr);
	}

	// The method that sorts arr[l..r] using merge()
	void mergeSort(int arr[], int l, int r) {
		if (l < r) {
			// Find the middle point
			int m = (l + r) / 2;

			// Sort first and second halves
			mergeSort(arr, l, m);
			mergeSort(arr, m + 1, r);

			// Merge the sorted halves
			merge(arr, l, m, r);
		}
	}

	/*
	 * Merges two subarrays of arr[]. First subarray is arr[left..mid] Second
	 * subarray is arr[mid+1..right]
	 */
	void merge(int arr[], int l, int m, int r) {
		// Find sizes of two subarrays to be merged
		int size1 = m - l + 1;
		int size2 = r - m;

		/* Create temp arrays */
		int Left[] = new int[size1];
		int Right[] = new int[size2];

		/* Copy data to temp arrays */
		for (int i = 0; i < size1; ++i)
			Left[i] = arr[l + i];
		for (int j = 0; j < size2; ++j)
			Right[j] = arr[m + 1 + j];

		/* Merge the temp arrays */

		// Initial indexes of first and second subarrays
		int i = 0, j = 0;

		// Initial index of merged subarray array
		int k = l;

		while (i < size1 && j < size2) {
			if (Left[i] <= Right[j]) {
				arr[k] = Left[i];
				i++;
			} else {
				arr[k] = Right[j];
				j++;
			}
			k++;
		}

		/* Copy remaining elements of Left[] if any */
		while (i < size1) {
			arr[k] = Left[i];
			i++;
			k++;
		}

		/* Copy remaining elements of Right[] if any */
		while (j < size2) {
			arr[k] = Right[j];
			j++;
			k++;
		}
	}

	// method to print array of size n
	static void printArray(int arr[]) {
		for (int i = 0; i < arr.length; ++i)
			System.out.print(arr[i] + " ");
		System.out.println();
	}

}

OUTPUT

Given Unsorted Array :
11 10 12 4 6 5 

Sorted array :
4 5 6 10 11 12

Summary

In this tutorial, we saw the concept of merge sorting algorithm and we wrote a recursive merge sorting code in java. I suggest copy this code in your favorite IDE and test it.
I hope you liked it !

Bubble Sort

by

Bubble Sort is the simplest sorting algorithm that works by repeatedly checking and swapping the next adjacent elements if they are in wrong order.

Time complexity :

In Average/Worst Case : it usually takes n number of passes to sort an array and complexity becomes O(n^2)
In Best Case : it takes O(n) time complexity , and it happens only when the array is already sorted.

Bubble Sort Example :

// Java program to implement Bubble Sort 
class BubbleSortPT
{ 
  void bubbleSort(int arr[]) 
  { 
    int n = arr.length; 
    for (int i = 0; i < n-1; i++) 
    for (int j = 0; j < n-i-1; j++) 
    if (arr[j] > arr[j+1]) 
    { 
     // swap arr[j+1] and arr[i] 
     int temp = arr[j]; 
     arr[j] = arr[j+1]; 
     arr[j+1] = temp; 
    } 
  }

  /* Prints the array */
  void printArray(int arr[]) 
  { 
    int n = arr.length; 
    for (int i=0; i<n; ++i) 
    System.out.print(arr[i] + " "); 
    System.out.println(); 
  }

  // Main method to test the above code
  public static void main(String args[]) 
  { 
    BubbleSortPT ob = new BubbleSortPT(); 
    int arr[] = {64, 34, 25, 12, 22, 11, 90}; 

    ob.bubbleSort(arr); 
    System.out.println("Sorted array"); 
    ob.printArray(arr); 
  } 
}

OUTPUT

Sorted array
11 12 22 25 34 64 90

Summary

In this article we learnt about bubble sort and its time complexities.
Hope you liked it !

Design Patterns for application development

by

Design patterns for application development are programming language independent strategies for solving a common problem. It means a design pattern represents an idea, not a particular implementation. By using design patterns you can make your code more flexible, maintainable and reusable.

The concept of design patterns in software development was originally presented in the 1994 book Design Patterns: Elements of Reusable Object-Oriented Software. The book was written by four authors who are now known collectively as the “Gang of Four”.

A design pattern provides a general reusable solution for the common problems occurs in software design.

It’s not mandatory to implement design patterns in your project always.

However, the lack of applying successful patterns will surely be visible as the effect of increased development time/effort/cost/bugs/rework and the inability to easily adapt to changing customer requirements.

So How do you find a right design pattern ?

To find out which pattern to use. You just have to try to understand the design patterns and it’s purposes. Only then you will be able to pick the right one.

Types of Design Patterns

Three major types of design patterns for application development.

1. Creational Patterns
2. Structural Patterns
3. Behavioral Patterns

1. Creational Design Patterns

Creational design pattern is about class instantiation or in other words object creation.

Further there are different types of creational design pattern:

  • Factory Method
  • Abstract Factory
  • Prototype
  • Singleton
  • Builder
  • Object Pool

2. Structural Design Patterns

This pattern is about organizing different classes and objects to form some other functionality. Structural class-creation patterns use inheritance to compose interfaces.

Some Structural design patterns are :

  • Adapter
  • Bridge
  • Composite
  • Decorator
  • Flyweight
  • Facade
  • Private Class Data
  • Proxy

3. Behavioral Design Patterns

These patterns are about identifying communication pattern between different objects and realize these patterns. These patterns are most specifically
concerned with communication between objects.

Some examples are :

  • Chain of responsibility
  • Command
  • Interpreter
  • Iterator
  • Mediator
  • Null Object
  • Observer
  • State
  • Strategy
  • Memento
  • Visitor
  • Template method

Five(5) Most important design patterns

1. Singleton

This pattern Ensure a class has only one instance, and provide a global point of access to it.

Scenario: Where application needs only one instance of an object. In addition to it, lazy initialization and global access are necessary.

There are several examples of singleton object where only a single instance of a class should exist such as caches, thread pools, db connection pools and registries.

How to make a class Singleton?

  1. Define a private static attribute in the “single instance” class.
  2. Define a public static method/function in the class – this is to be used by clients to access the object outside this class.
  3. Do “lazy initialization” of object (i.e create object on first use) in the accessor function.
  4. Define all constructors to be protected or private.

2. Factory Method

In Factory Pattern you can define an interface for creating an object, but let subclasses decide which class to instantiate. Factory Method lets a class defer instantiation to subclasses.

The new operator is used to instantiate a class.

We should not prefer using new keyword to instantiate a class object every time as it also makes the code tightly coupled with that particular class.
To accomplish this, in Factory method objects are created by calling a factory method instead of calling a constructor.

3. Observer

This pattern defines a on-to-many dependency between object, such that when one object changes its state the other dependant objects are notified.

Model the independent functionality with a “subject” abstraction.

Model the dependent functionality with an “observer” hierarchy.

The Subject broadcasts events to all registered Observers.

The Subject may “push” information at the Observers, or, the Observers may “pull” the information they need from the Subject.

The pattern consists of two actors, the observer who is interested in the updates and the subject who generates the updates.

For Example: when you subscribe to a news feed from a social media website, whenever there is a new post the subscribers would see the new post.

4. Builder

As the name suggests the builder pattern is used to build objects.

Sometimes the object creation can get complex, one object can have multiple sub-objects, To separate the construction of a complex object from its representation so that the same construction process can create different representations.

The builder pattern might seem similar to the ‘abstract factory’ design pattern but one difference is that the builder pattern creates an object step by step whereas the abstract factory pattern returns the object in one go.

5. Adapter

This design pattern allows incompatible classes to work together by converting the interface of one class into another. Adapter lets classes work together that couldn’t otherwise because of incompatible interfaces.

Adapter is meant to change the interface of an existing object.
Facade defines a new interface, whereas Adapter reuses an old interface. Remember that Adapter makes two existing interfaces work together as opposed to defining an entirely new one.

For example : If you have two applications, with one producing out output in XML format whereas the other requiring JSON as input, then you’ll need an adapter between the two to make them work seamlessly.

Summary

In this article, we learnt about Design patterns for application development and its importance, we also saw 3 different categories of design patterns and finally had a look at 5 basic and important design patterns.

I hope you liked it !