Divide and Conquer

Merge Sort

QuickSort

A sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Run time is Θ(n log n).

public class QuickSort {  
  public static void main(String[] args) {  
        int i;  
        int[] arr={90,23,101,45,65,23,67,89,34,23};  
        quickSort(arr, 0, 9);  
        System.out.println("\n The sorted array is: \n");  
        for(i=0;i<10;i++)  
        System.out.println(arr[i]);  
    }
    
    public static int partition(int a[], int beg, int end)  
    {  
          
        int left, right, temp, loc, flag;     
        loc = left = beg;  
        right = end;  
        flag = 0;  
        while(flag != 1)  
        {  
            while((a[loc] <= a[right]) && (loc!=right))  
            right--;  
            if(loc==right)  
              flag = 1;  
            else if(a[loc]>a[right])
            {  
                temp = a[loc];  
                a[loc] = a[right];  
                a[right] = temp;  
                loc = right;  
            }  
            if(flag!=1)  
            {  
                while((a[loc] >= a[left]) && (loc!=left))  
                  left++;  
                if(loc==left)  
                 flag =1;  
                else if (a[loc] <a[left])
                {  
                    temp = a[loc];  
                    a[loc] = a[left];  
                    a[left] = temp;  
                    loc = left;  
                }  
            }  
        }  
        return loc;  
    }  
    static void quickSort(int a[], int beg, int end)  
    {  
          
        int loc;  
        if(beg<end)  
        {  
            loc = partition(a, beg, end);  
            quickSort(a, beg, loc-1);  
            quickSort(a, loc+1, end);  
        }  
    }  
}  

Binary Search

Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an element into some list by using binary search technique, we must ensure that the list is sorted.

import java.util.*;  
public class BinarySearch {  
public static void main(String[] args) {  
    int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100};  
    int item, location = -1;  
    System.out.println("Enter the item which you want to search");  
    Scanner sc = new Scanner(System.in);  
    item = sc.nextInt();  
    location = binarySearch(arr,0,9,item);  
    if(location != -1)  
    System.out.println("the location of the item is "+location);  
    else   
        System.out.println("Item not found");  
    }  
public static int binarySearch(int[] a, int beg, int end, int item)  
{  
    int mid;  
    if(end >= beg)   
    {     
        mid = (beg + end)/2;  
        if(a[mid] == item)  
        {  
            return mid+1;  
        }  
        else if(a[mid] < item)   
        {  
            return binarySearch(a,mid+1,end,item);  
        }  
        else   
        {  
            return binarySearch(a,beg,mid-1,item);  
        }  
      
    }  
    return -1;   
}  
}  

Closest Pair

App.java

import java.util.Arrays;
import java.util.List;

public class App {

	public static void main(String[] args) {
		
		List<Point> points = Arrays.asList(new Point(2, 3),new Point(12, 30),new Point(40, 50),
				new Point(5, 1), new Point(12, 10), new Point(3, 4));
		
		Algorithm algorithm = new Algorithm(points);
		System.out.println( algorithm.solveProblem());
		
	}
}

Algorithm.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Algorithm {

	private List<Point> points;

	public Algorithm(List<Point> points) {
		this.points = points;
	}
	
	public double solveProblem(){
		
		List<Point> sortedXPoints = new ArrayList<>();
		List<Point> yPoints = new ArrayList<>();
		
		for(Point point : this.points){
			sortedXPoints.add(point);
			yPoints.add(point);
		}
		
		sortByX(sortedXPoints);
		
		return findClosestPoints(sortedXPoints, yPoints, sortedXPoints.size());
	}
	
	public double findClosestPoints(List<Point> pointsSortedX, List<Point> pointsY, int numOfPoints){
		
		if( numOfPoints <= 3 ) return bruteForceApproach(pointsSortedX);
		
		int middleIndex = numOfPoints / 2;
		
		Point middlePoint = pointsSortedX.get(middleIndex);
		
		List<Point> leftSubPointsY = new ArrayList<>();
		List<Point> leftSubPointsSortedX = new ArrayList<>();
		List<Point> rightSubPointsY = new ArrayList<>();
		List<Point> rightSubPointsSortedX = new ArrayList<>();
		
		// divide the point to left and right subarrays
		for(int index=0;index<numOfPoints;++index){
			if( pointsY.get(index).getX() <= middlePoint.getX() ){
				leftSubPointsY.add(pointsY.get(index));
				leftSubPointsSortedX.add(pointsSortedX.get(index));
			}else{
				rightSubPointsY.add(pointsY.get(index));
				rightSubPointsSortedX.add(pointsSortedX.get(index));
			}
		}
		
		double sigmaLeft = findClosestPoints(leftSubPointsSortedX, leftSubPointsY, middleIndex);
		double sigmaRight = findClosestPoints(rightSubPointsSortedX, rightSubPointsY, numOfPoints-middleIndex);
		double sigma = Math.min(sigmaLeft, sigmaRight);
		
		List<Point> pointsInStrip = new ArrayList<>();
		
		for(int index=0;index<numOfPoints;++index){
			if( Math.abs(pointsY.get(index).getX() - middlePoint.getX()) < sigma ){
				pointsInStrip.add(pointsY.get(index));
			}
		}
		
		double minDistanceStrip = findMinimumDistanceInStrip(pointsInStrip, sigma);
	
		return Math.min(sigma, minDistanceStrip);
	}

	public double bruteForceApproach(List<Point> points) {
		
		double minDistance = Double.MAX_VALUE;
		
		for(int i=0;i<points.size();++i){
			for(int j=i+1;j<points.size();++j){
				if( distance(points.get(i), points.get(j)) < minDistance ){
					minDistance = distance(points.get(i), points.get(j));
				}
			}
		}
		
		return minDistance;
	}

	private double findMinimumDistanceInStrip(List<Point> pointsInStrip, double sigma) {
		
		double minDistance = sigma;
		
		for(int i=0;i<pointsInStrip.size();++i){
			for(int j=i+1; j<pointsInStrip.size() && (pointsInStrip.get(j).getY() - pointsInStrip.get(i).getY())<minDistance;++j){				
				if( distance(pointsInStrip.get(i), pointsInStrip.get(j)) < minDistance ) {
					minDistance = distance(pointsInStrip.get(i), pointsInStrip.get(j));
				}
			}
		}
		
		return minDistance;
	}

	private void sortByX(List<Point> points){
		Collections.sort(points, new XSorter());
	}
	
	private double distance(Point point1, Point point2){
		double xDistance = Math.abs( point1.getX() - point2.getX() );
		double yDistance = Math.abs( point1.getY() - point2.getY() );
		return Math.sqrt(xDistance*xDistance + yDistance*yDistance);
	}
}

Point.java


public class Point {

	private double x;
	private double y;

	public Point(double x, double y) {
		this.x = x;
		this.y = y;
	}

	public double getX() {
		return x;
	}

	public void setX(double x) {
		this.x = x;
	}

	public double getY() {
		return y;
	}

	public void setY(double y) {
		this.y = y;
	}

	@Override
	public String toString() {
		return "(" + this.x + ";" + this.y + ")";
	}
}

XSorter.java

import java.util.Comparator;

public class XSorter implements Comparator<Point>{

	@Override
	public int compare(Point point, Point otherPoint) {
		return Double.compare(point.getX(), otherPoint.getX());
	}
}