Merge Sort<\/p>\n\n\n\n
QuickSort<\/p>\n\n\n\n
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 \u0398(n log n).<\/p>\n\n\n\n
public class QuickSort { \n public static void main(String[] args) { \n int i; \n int[] arr={90,23,101,45,65,23,67,89,34,23}; \n quickSort(arr, 0, 9); \n System.out.println(\"\\n The sorted array is: \\n\"); \n for(i=0;i<10;i++) \n System.out.println(arr[i]); \n }\n \n public static int partition(int a[], int beg, int end) \n { \n \n int left, right, temp, loc, flag; \n loc = left = beg; \n right = end; \n flag = 0; \n while(flag != 1) \n { \n while((a[loc] <= a[right]) && (loc!=right)) \n right--; \n if(loc==right) \n flag = 1; \n else if(a[loc]>a[right])\n { \n temp = a[loc]; \n a[loc] = a[right]; \n a[right] = temp; \n loc = right; \n } \n if(flag!=1) \n { \n while((a[loc] >= a[left]) && (loc!=left)) \n left++; \n if(loc==left) \n flag =1; \n else if (a[loc] <a[left])\n { \n temp = a[loc]; \n a[loc] = a[left]; \n a[left] = temp; \n loc = left; \n } \n } \n } \n return loc; \n } \n static void quickSort(int a[], int beg, int end) \n { \n \n int loc; \n if(beg<end) \n { \n loc = partition(a, beg, end); \n quickSort(a, beg, loc-1); \n quickSort(a, loc+1, end); \n } \n } \n} <\/pre>\n\n\n\n<\/p>\n\n\n\n
Binary Search<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
import java.util.*; \npublic class BinarySearch { \npublic static void main(String[] args) { \n int[] arr = {16, 19, 20, 23, 45, 56, 78, 90, 96, 100}; \n int item, location = -1; \n System.out.println(\"Enter the item which you want to search\"); \n Scanner sc = new Scanner(System.in); \n item = sc.nextInt(); \n location = binarySearch(arr,0,9,item); \n if(location != -1) \n System.out.println(\"the location of the item is \"+location); \n else \n System.out.println(\"Item not found\"); \n } \npublic static int binarySearch(int[] a, int beg, int end, int item) \n{ \n int mid; \n if(end >= beg) \n { \n mid = (beg + end)\/2; \n if(a[mid] == item) \n { \n return mid+1; \n } \n else if(a[mid] < item) \n { \n return binarySearch(a,mid+1,end,item); \n } \n else \n { \n return binarySearch(a,beg,mid-1,item); \n } \n \n } \n return -1; \n} \n} <\/pre>\n\n\n\nClosest Pair<\/p>\n\n\n\n
App.java<\/p>\n\n\n\n
import java.util.Arrays;\nimport java.util.List;\n\npublic class App {\n\n\tpublic static void main(String[] args) {\n\t\t\n\t\tList<Point> points = Arrays.asList(new Point(2, 3),new Point(12, 30),new Point(40, 50),\n\t\t\t\tnew Point(5, 1), new Point(12, 10), new Point(3, 4));\n\t\t\n\t\tAlgorithm algorithm = new Algorithm(points);\n\t\tSystem.out.println( algorithm.solveProblem());\n\t\t\n\t}\n}<\/pre>\n\n\n\nAlgorithm.java<\/p>\n\n\n\n
import java.util.ArrayList;\nimport java.util.Collections;\nimport java.util.List;\n\npublic class Algorithm {\n\n\tprivate List<Point> points;\n\n\tpublic Algorithm(List<Point> points) {\n\t\tthis.points = points;\n\t}\n\t\n\tpublic double solveProblem(){\n\t\t\n\t\tList<Point> sortedXPoints = new ArrayList<>();\n\t\tList<Point> yPoints = new ArrayList<>();\n\t\t\n\t\tfor(Point point : this.points){\n\t\t\tsortedXPoints.add(point);\n\t\t\tyPoints.add(point);\n\t\t}\n\t\t\n\t\tsortByX(sortedXPoints);\n\t\t\n\t\treturn findClosestPoints(sortedXPoints, yPoints, sortedXPoints.size());\n\t}\n\t\n\tpublic double findClosestPoints(List<Point> pointsSortedX, List<Point> pointsY, int numOfPoints){\n\t\t\n\t\tif( numOfPoints <= 3 ) return bruteForceApproach(pointsSortedX);\n\t\t\n\t\tint middleIndex = numOfPoints \/ 2;\n\t\t\n\t\tPoint middlePoint = pointsSortedX.get(middleIndex);\n\t\t\n\t\tList<Point> leftSubPointsY = new ArrayList<>();\n\t\tList<Point> leftSubPointsSortedX = new ArrayList<>();\n\t\tList<Point> rightSubPointsY = new ArrayList<>();\n\t\tList<Point> rightSubPointsSortedX = new ArrayList<>();\n\t\t\n\t\t\/\/ divide the point to left and right subarrays\n\t\tfor(int index=0;index<numOfPoints;++index){\n\t\t\tif( pointsY.get(index).getX() <= middlePoint.getX() ){\n\t\t\t\tleftSubPointsY.add(pointsY.get(index));\n\t\t\t\tleftSubPointsSortedX.add(pointsSortedX.get(index));\n\t\t\t}else{\n\t\t\t\trightSubPointsY.add(pointsY.get(index));\n\t\t\t\trightSubPointsSortedX.add(pointsSortedX.get(index));\n\t\t\t}\n\t\t}\n\t\t\n\t\tdouble sigmaLeft = findClosestPoints(leftSubPointsSortedX, leftSubPointsY, middleIndex);\n\t\tdouble sigmaRight = findClosestPoints(rightSubPointsSortedX, rightSubPointsY, numOfPoints-middleIndex);\n\t\tdouble sigma = Math.min(sigmaLeft, sigmaRight);\n\t\t\n\t\tList<Point> pointsInStrip = new ArrayList<>();\n\t\t\n\t\tfor(int index=0;index<numOfPoints;++index){\n\t\t\tif( Math.abs(pointsY.get(index).getX() - middlePoint.getX()) < sigma ){\n\t\t\t\tpointsInStrip.add(pointsY.get(index));\n\t\t\t}\n\t\t}\n\t\t\n\t\tdouble minDistanceStrip = findMinimumDistanceInStrip(pointsInStrip, sigma);\n\t\n\t\treturn Math.min(sigma, minDistanceStrip);\n\t}\n\n\tpublic double bruteForceApproach(List<Point> points) {\n\t\t\n\t\tdouble minDistance = Double.MAX_VALUE;\n\t\t\n\t\tfor(int i=0;i<points.size();++i){\n\t\t\tfor(int j=i+1;j<points.size();++j){\n\t\t\t\tif( distance(points.get(i), points.get(j)) < minDistance ){\n\t\t\t\t\tminDistance = distance(points.get(i), points.get(j));\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t\n\t\treturn minDistance;\n\t}\n\n\tprivate double findMinimumDistanceInStrip(List<Point> pointsInStrip, double sigma) {\n\t\t\n\t\tdouble minDistance = sigma;\n\t\t\n\t\tfor(int i=0;i<pointsInStrip.size();++i){\n\t\t\tfor(int j=i+1; j<pointsInStrip.size() && (pointsInStrip.get(j).getY() - pointsInStrip.get(i).getY())<minDistance;++j){\t\t\t\t\n\t\t\t\tif( distance(pointsInStrip.get(i), pointsInStrip.get(j)) < minDistance ) {\n\t\t\t\t\tminDistance = distance(pointsInStrip.get(i), pointsInStrip.get(j));\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\t\n\t\treturn minDistance;\n\t}\n\n\tprivate void sortByX(List<Point> points){\n\t\tCollections.sort(points, new XSorter());\n\t}\n\t\n\tprivate double distance(Point point1, Point point2){\n\t\tdouble xDistance = Math.abs( point1.getX() - point2.getX() );\n\t\tdouble yDistance = Math.abs( point1.getY() - point2.getY() );\n\t\treturn Math.sqrt(xDistance*xDistance + yDistance*yDistance);\n\t}\n}<\/pre>\n\n\n\nPoint.java<\/p>\n\n\n\n
\npublic class Point {\n\n\tprivate double x;\n\tprivate double y;\n\n\tpublic Point(double x, double y) {\n\t\tthis.x = x;\n\t\tthis.y = y;\n\t}\n\n\tpublic double getX() {\n\t\treturn x;\n\t}\n\n\tpublic void setX(double x) {\n\t\tthis.x = x;\n\t}\n\n\tpublic double getY() {\n\t\treturn y;\n\t}\n\n\tpublic void setY(double y) {\n\t\tthis.y = y;\n\t}\n\n\t@Override\n\tpublic String toString() {\n\t\treturn \"(\" + this.x + \";\" + this.y + \")\";\n\t}\n}<\/pre>\n\n\n\nXSorter.java<\/p>\n\n\n\n
import java.util.Comparator;\n\npublic class XSorter implements Comparator<Point>{\n\n\t@Override\n\tpublic int compare(Point point, Point otherPoint) {\n\t\treturn Double.compare(point.getX(), otherPoint.getX());\n\t}\n}<\/pre>\n\n\n\n<\/p>\n","protected":false},"excerpt":{"rendered":"
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 \u0398(n log n). Binary Search Binary search is the search technique which works efficiently on the sorted lists. Hence, in order to search an […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/435"}],"collection":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/comments?post=435"}],"version-history":[{"count":12,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/435\/revisions"}],"predecessor-version":[{"id":514,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/435\/revisions\/514"}],"wp:attachment":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/media?parent=435"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}