CS 100: Section Assignment S9
Solutions
public class SearchNSort
{
// Yields the index of the first occurence of x in the array a.
// Yields -1 if no array value equals x.
public static int LinSearchBook(int[]a,int x)
{
int n = a.length;
for (int k=0;k<n;k++)
{
if (a[k]==x)
{
return k;
}
}
return -1;
}
// Yields the index of the first occurence of x in the array a.
// Yields -1 if no array value equals x.
public static int LinSearch(int[]a,int x)
{
int n = a.length;
int k=0;
while (k< a.length && x!=a[k])
k++;
if (k==a.length)
return -1;
else
return k;
}
// Yields -1 if no array value equals x.
public static int BinSearch(int[] a,int x)
{
int n = a.length;
int L = 0;
int R = n-1;
int m;
//
while (L<=R)
{
m = (L+R)/2; // The midpoint index.
if (x==a[m])
return m;
if (x>a[m])
// x is not in a[0..m]
L = m+1;
else
// x is not in a[m..n-1]
R = m-1;
}
return -1;
}
// Insertion sort for integers.
// Permutes the values in a so that a[0]<=a[1]<=...<=a[n-1]
// where n = a.length
public static void sort(int[] a)
{
int n = a.length;
int temp; // For swapping array elements
int j;
for (int k=1;k<n;k++)
{
// a[0..k-1] is sorted. Now sort a[0..k] by
// "pushing" it left as long as
// it is smaller than its "left neighbor".
j=k;
while(j>=1 && a[j]<a[j-1])
{
temp = a[j-1]; a[j-1] = a[j]; a[j] = temp;
j=j-1;
}
}
}
// Insertion sort for strings.
// Permutes the values in a so that a[0]<=a[1]<=...<=a[n-1]
// where n = a.length
public static void sort(String[] a)
{
int n = a.length;
String temp; // For swapping array elements.
int j;
for (int k=1;k<n;k++)
{
// a[0..k-1] is sorted. Now sort a[0..k] by
// "pushing" it left as long as
// it is smaller than its "left neighbor".
j=k;
while(j>=1 && a[j].compareTo(a[j-1])<0)
{
temp = a[j-1]; a[j-1] = a[j]; a[j] = temp;
j=j-1;
}
}
}
// Merge sort for integers.
// Permutes the values in a so that a[0]<=a[1]<=...<=a[n-1]
// where n = a.length
public static void MergeSort(int[] a)
{
int n = a.length;
if (n==1)
// Nothing to do
return;
else
{
// Split the array in half
int m = n/2;
int[] aLeft = new int[m];
int[] aRight = new int[m];
for(int i=0;i<m;i++)
{
aLeft[i] = a[i];
aRight[i] = a[i+m];
}
// Sort the left and right halves
MergeSort(aLeft);
MergeSort(aRight);
// Merge the results
int iLeft=0;
int iRight=0;
for (int k=0;k<n;k++)
if (iLeft==m) { a[k] = aRight[iRight]; iRight++;}
else if (iRight==m) { a[k] = aLeft[iLeft]; iLeft++; }
else if (aLeft[iLeft] <= aRight[iRight]) { a[k] = aLeft[iLeft]; iLeft++;}
else { a[k] = aRight[iRight]; iRight++;}
}
}
// Print the values of a reasonably short integer array.
public static void print(int[] a)
{
int n = a.length;
System.out.println("\n");
for(int k=0;k<n;k++)
System.out.print(" " + a[k]);
System.out.println("\n ");
}
// Print the values of a reasonably short string array.
public static void print(String[] a)
{
int n = a.length;
System.out.println("\n");
for(int k=0;k<n;k++)
System.out.print(" " + a[k]);
System.out.println("\n ");
}
// Yields a reference to an array that is a copy of a.
public static int[] copy(int[]a)
{
int n = a.length;
int[] b = new int[n];
for(int i=0;i<n;i++)
b[i] = a[i];
return b;
}
// Yields the index of the last occurence of x in the array a.
// Yields -1 if no array value equals x.
public static int LinSearch1(int[]a,int x)
{
int n = a.length;
int k=n-1;
while (k>=0 && x!=a[k])
k--;
if (k<0)
return -1;
else
return k;
}
}
import java.io.*;
public class S9A
{
public static void main(String args[])
{
TokenReader in = new TokenReader(System.in);
int[] w = {30,20,90,10,50,60,40,80,70};
SearchNSort.print(w);
SearchNSort.sort(w);
SearchNSort.print(w);
int m = w.length/2;
System.out.println("The median value is " + w[m]);
in.waitUntilEnter();
}
}
/* Output
30 20 90 10 50 60 40 80 70
10 20 30 40 50 60 70 80 90
The median value is 50
*/
import java.io.*;
public class S9B
{
public static void main(String args[])
{
TokenReader in = new TokenReader(System.in);
int[] x = {10, 30, 40, 70};
int[] y = {15, 60};
int[] z = {20, 30, 50, 80, 90};
int n = x.length + y.length + z.length;
int[] a = new int[n];
// 3way merge
int ix=0; int iy=0; int iz=0;
for (int k=0;k< n;k++)
{
if (ix==x.length)
// x-array exhausted
{
if (iy==y.length) {a[k] = z[iz]; iz++;}
else if (iz==z.length) {a[k] = y[iy]; iy++;}
else if (y[iy]<=z[iz]) {a[k] = y[iy]; iy++;}
else {a[k] = z[iz]; iz++;}
}
else if (iy==y.length)
// y-array exhausted
{
if (ix==x.length) {a[k] = z[iz]; iz++;}
else if (iz==z.length) {a[k] = x[ix]; ix++;}
else if (x[ix]<=z[iz]) {a[k] = x[iy]; ix++;}
else {a[k] = z[iz]; iz++;}
}
else if (iz==z.length)
// z-array exhausted
{
if (ix==x.length) {a[k] = y[iy]; iy++;}
else if (iy==y.length) {a[k] = x[iy]; ix++;}
else if (x[ix]<=y[iy]) {a[k] = x[ix]; ix++;}
else {a[k] = y[iy]; iy++;}
}
else
// All three arrays are around
{
if (x[ix]<=y[iy] && x[ix]<=z[iz]) {a[k] = x[ix]; ix++;}
else if (y[iy]<=x[ix] && y[iy]<=z[iz]) {a[k] = y[iy]; iy++;}
else {a[k] = z[iz]; iz++;}
}
}
SearchNSort.print(x);
SearchNSort.print(y);
SearchNSort.print(z);
SearchNSort.print(a);
in.waitUntilEnter();
}
}
/* Output
10 30 40 70
15 60
20 30 50 80 90
10 15 20 30 30 40 50 60 40 80 90
*/
import java.io.*;
public class S9CD
{
public static void main(String args[])
{
TokenReader in = new TokenReader(System.in);
int[] a = {1,2,3,4,5};
SearchNSort.print(a);
int[] acopy;
acopy = SearchNSort.copy(a);
SearchNSort.print(acopy);
int[] x = {10,20,30,10,10,50,20};
SearchNSort.print(x);
int idx = SearchNSort.LinSearch1(x,10);
System.out.println("The last occurence of 10 is in x["+idx+"]");
in.waitUntilEnter();
}
}
/* output
1 2 3 4 5
1 2 3 4 5
10 20 30 10 10 50 20
The last occurence of 10 is in x[4]
*/