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());
}
}