To develop a faster sorting method, we use a divide-and-conquer approach to algorithm design that every programmer needs to understand. This nomenclature refers to the idea that one way to solve a problem is to divide it into independent parts, conquer them independently, and then use the solutions for the parts to develop a solution for the full problem. To sort an array with this strategy, we divide it into two halves, sort the two halves independently, and then merge the results to sort the full array. This method is known as mergesort.
This is a program :
import jeliot.io.*;
public class mergeSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,7,15,1,3,10};
System.out.println("\n\n RoseIndia\n\n");
System.out.println(" Merge Sort\n\n");
System.out.println("Values Before the sort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
mergeSort_srt(array,0, array.length-1);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
System.out.println("PAUSE");
}
public static void mergeSort_srt(int array[],int lo, int n){
int low = lo;
int high = n;
if (low >= high) {
return;
}
int middle = (low + high) / 2;
mergeSort_srt(array, low, middle);
mergeSort_srt(array, middle + 1, high);
int end_low = middle;
int start_high = middle + 1;
while ((lo <= end_low) && (start_high <= high)) {
if (array[low] < array[start_high]) {
low++;
} else {
int Temp = array[start_high];
for (int k = start_high- 1; k >= low; k--) {
array[k+1] = array[k];
}
array[low] = Temp;
low++;
end_low++;
start_high++;
}
}
}
}
Quicksort is a divide-and-conquer method for sorting. It works by partitioning an array of elements into two parts, then sorting the parts independently. As we shall see, the precise position of the partition depends on the initial order of the elements in the input file. The crux of the method is the partitioning process, which rearranges the array to make the following three conditions hold:
The element a[i] is in its final place in the array for i.
None of the elements a[left], ..., a[i-1] is greater than a[i].
None of the elements in a[i+1], ..., a[right] is less than a[i].
This is a program :
import jeliot.io.*;
public class QuickSort{
public static void main(String a[]){
int i;
int array[] = {12,9,4,29,7,1,3,10};
System.out.println("Values Before the sort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" ");
System.out.println();
quickSort(array,0,7);
System.out.print("Values after the sort:\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
System.out.println("PAUSE");
}
public static int partition(int arr[], int left, int right) {
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
return i;
}
public static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
}
public class Vektor {
int []elemen= new int [100];
int banyak;
public void beri_nilaiBanyak(){
banyak=3;
for(int i=0; iB.banyak)
banyak=A.banyak;
else
banyak=B.banyak;
for(int i=0; i
elemen[i]=A.elemen[i]+B.elemen[i];
}
public void perkalian_vektor(float k, Vektor A){
banyak=A.banyak;
for(int i=0; i
elemen[i]+=k*A.elemen[i];
}
public static void main() {
Vektor X = new Vektor();
Vektor Y = new Vektor();
Vektor Z = new Vektor();
Z.beri_nilaiBanyak();
Z.masukan(X,Y);
Z.penjumlahan_vektor(X,Y);
System.out.print("\n Hasil penjumlahan 2 Vektor \n" + Z);
Z.perkalian_vektor(3,X);
System.out.print("\n Hasil perkalian skalar dengan Vektor \n" + Z);
}
}
which is an example of the general problem-solving method known as binary search.
Correctness proof. First, we have to convince ourselves that the method is correct: that it always leads us to the hidden number. We do so by establishing the following facts:
The interval always contains the hidden number.
The interval sizes are the powers of two, decreasing from N.
The first of these facts is enforced by the code; the second follows by noting that if the interval size (hi-lo) is a power of two, then the next interval size is (hi-lo)/2, which is the next smaller power of two. These facts are the basis of an induction proof that the method operates as intended. Eventually, the interval size becomes 1, so we are guaranteed to find the number.
Running time analysis. Since the size of the interval decreases by a factor of 2 at each iteration (and the base case is reached when N = 1), the running time of binary search is lg N.
Linear-logarithm chasm. The alternative to using binary search is to guess 0, then 1, then 2, then 3, and so forth, until hitting the hidden number. We refer to such an algorithm as a brute-force algorithm: it seems to get the job done, but without much regard to the cost (which might prevent it from actu- ally getting the job done for large problems). In this case, the running time of the brute-force algorithm is sensitive to the input value, but could be as much as N and has expected value N/2 if the input value is chosen at random. Meanwhile, binary search is guaranteed to use no more than lg N steps.
Binary representation. If you look back to Program 1.3.7, you will recognize that binary search is nearly the same computation as converting a number to binary! Each guess determines one bit of the answer. In our example, the information that the number is between 0 and 127 says that the number of bits in its binary representation is 7, the answer to the first question (is the number less than 64?) tells us the value of the leading bit, the answer to the second question tells us the value of the next bit, and so forth. For example, if the number is 77, the sequence of answers no yes yes no no yes no immediately yields 1001101, the binary representation of 77.
Inverting a function. As an example of the utility of binary search in scientific computing, we revisit a problem that we consider the problem of inverting an increasing function. To fix ideas, we refer to the Gaussian distribution Φ when describing the method. Given a value y, our task is to find a value x such that Φ(x) = y. In this situation, we use real numbers as the endpoints of our interval, not integers, but we use the same essential method as for guessing a hidden integer: we halve the size of the interval at each step, keeping x in the interval, until the interval is sufficiently small that we know the value of x to within a desired precision δ. We start with an interval (lo, hi) known to contain x and use the following recursive strategy:
Compute m = lo + (hi - lo) / 2
Base case: If (hi - lo) is less than δ, then returm m as an estimate of x
Recursive step: otherwise, test whether Φ(m) < y. If so look for x in (lo, m); if not look for x in (m, hi)
The key to this method is the idea that the function is increasing - for any values a and b, knowing that Φ(a) < Φ(b) tells us that a < b, and vice versa. In this context, binary search is often called bisection search because we bisect the interval at each stage.
Binary search in a sorted array. During much of the last century people would use a publication known as a phone book to look up a person's phone number. Entries appears in order, sorted by a key that identifies it (the person's name) n both cases). A brute-force solution would be to start at the beginning, examine each entry one at a time, and continue until you find the name. No one uses that method: instead, you open the book to some interior page and look for the name on that page. If it is there, you are done; otherwise, you eliminate either the part of the book before the current page or the part of the book after the current page from consideration and repeat.
Exception filter. We now use binary search to solve the existence problem: is a given key in a sorted database of keys? For example, when checking the spelling of a word, you need only know whether your word is in the dictionary and are not interested in the definition. In a computer search, we keep the information in an array, sorted in order of the key. The binary search code in BinarySearch.java differs from our other applications in two details. First, the file size N need not be a power of two. Second, it has to allow the possibility that the item sought is not in the array. The client program implements an exception filter: it reads a sorted list of strings from a file (which we refer to as the whitelist) and an arbitrary sequence of strings from standard input and prints those in the sequence that are not in the whitelist.
Binary search. Justify why the following modified version of binarySearch() works. Prove that if the key is in the array, it correctly returns the smallest index i such that a[i] = key; if the key is not in the array, it returns -i where i is the smallest index such that a[i] > key
// precondition array a in ascending order
public static int binarySearch(long[] a, long key) {
