/**
* @author Ognjen Savkovic (ognjen.savkovic@unibz.it)
*/
public class ArrayUtility {
public static void main(String[] args) {
}
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
// LAB 1
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
/**
*
* @param A
* @param i
* @param j
* @return return the maximum element of the array A between position i and j.
*/
public static int findMax(int [] A, int i, int j){
int max; // max element in A between i and j
int k; // counter that ranges from i to j
max = A[i]; // assume A[i] is max
for (k=i+1 ; k<=j ; k++)
if(max<A[k]) // new max is improved here
max=A[k];
return max;
}
/**
*
* @param A
* @param i
* @param j
* @return return the position of the maximum element of the array A between position i and j.
*/
public static int findMaxPos(int [] A, int i, int j){
int max; // max element in A between i and j
int k; // counter that ranges from i to j
int pos; // position of max in A
max = A[i]; // assume A[i] is max
pos = i;
for (k=i+1 ; k<=j ; k++)
if(max<A[k]){ // new max is improved here
max=A[k];
pos=k;
}
return pos;
}
/**
*
* @param A
* @param i
* @param j
* @return return the minimum element of the array A between position i and j.
*/
public static int findMin(int [] A, int i, int j){
int min; // min element in A between i and j
int k; // counter that ranges from i to j
min = A[i]; // assume A[i] is min
for (k=i+1 ; k<=j ; k++)
if(min > A[k]) // new min is improved here
min=A[k];
return min;
}
/**
*
* @param A
* @param i
* @param j
* @return return the position of the minimum element of the array A between position i and j.
*/
public static int findMinPos(int [] A, int i, int j){
int min; // min element in A between i and j
int k; // counter that ranges from i to j
int pos=-1; // position of min in A
min = A[i]; // assume A[i] is min
pos=i;
for (k=i+1 ; k<=j ; k++)
if(min>A[k]){ // new min is improved here
min=A[k];
pos=k;
}
return pos;
}
/**
* @param i
* @param j
* swap the elements in position i and j in the array A.
*/
public static void swap(int[] A, int i, int j){
int tmp; // auxiliary variable
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
/**
*
* @param A
* @param i
* @param j
* shift on the right all the elements of the array A starting from position i and until position j
* (i.e., move the element in position k to position k + 1 for all i ≤ k < j).
*/
public static void shiftRight(int[] A, int i, int j){
for (int k=j ; k>i ; k--) // replaces the right element with one the left starting from the end
A[k]=A[k-1];
}
/**
*
* @param A
* @param i
* @param j
* shift on the left all the elements of the array A from position j until position i
* (i.e., move the element in position k to position k − 1 for all i < k ≤ j).
*/
public static void shiftLeft(int[] A, int i, int j){
for (int k=i ; k<j ; k++) // replaces the left element with one the right starting from the beginning
A[k]=A[k+1];
}
/**
* @param size
* @param min
* @param max
* @return creates and returns an array of size of random elements
* with values between min and max (use the Math.random() method of java).
*/
public static int[] createRandomArray(int size, int min, int max){
int [] randomArray; // new random array
randomArray = new int[size];
for(int i=0; i<size; i++)
randomArray[i] = (int)(Math.random() * ((max - min) + 1)) + min; // +1 because Math.random() is in [0,1)
return randomArray;
}
/**
* @param size
* @param min
* @param max
* @return creates bi-dimensional array with rows rows and cols columns
* of random elements with values between min and max (use the Math.random() method of java).
*/
public static int[][] createRandomMatrix(int rows, int cols, int min, int max){
int [][] randomMatrix; // new random matrix
randomMatrix = new int[rows][cols];
for(int i=0; i<rows; i++)
randomMatrix[i] = createRandomArray(cols,min,max);
return randomMatrix;
}
/**
* @param A
* @return return an array that is the copy of A.
*/
public static int[] copyArray(int[] A){
int [] copyOfA; // new array that is copy of A
copyOfA = new int [A.length];
for(int i=0; i<A.length; i++)
copyOfA[i]=A[i];
return copyOfA;
}
/**
* @param A
* @return a bi-dimensional array that is the copy of A.
*/
public static int[][] copyMatrix(int[][] A){
int [][] copyOfA; // new matrix that is copy of A
copyOfA= new int [A.length][A[0].length];
for(int i=0; i<A.length; i++)
for(int j=0; j<A[i].length; j++)
copyOfA[i][j]=A[i][j];
return copyOfA;
}
/**
* @param A
* @param n
* @return the position of the number n in the array A (it returns −1 if n is not present in A).
*/
public static int findElement(int[] A, int n){
for (int i=0; i<A.length ; i++)
if(A[i]==n)
return i;
return -1; // if program reaches here no n is found
}
/**
*
* @param A
* @param n
* @return returns the position of the number q in the sorted array A (returns −1 if q is not present in A).
* The method assumes that the array A is sorted, it need not be correct if A is not sorted.
* Exploit the fact that the array is sorted to find an efficient algorithm.
* (Remember the Google interview questions!)
*/
public static int findInSortedArray(int[] A, int q){
return searchBin(A,0,A.length-1,q);
}
/**
*
* @param A sorted array
* @param lo lower index
* @param hi higher index
* @param q element
* @return -1 if q is not in A, otherwise returns the position of q in A
*/
private static int searchBin(int[] A, int lo, int hi, int q) {
int middle;
if(lo>hi)
return -1; // not found
middle = (lo+hi)/2; // take the middle index
if(A[middle]==q)
return middle; // found !!
else if(A[middle]<q)
return searchBin(A,middle+1,hi,q); // look at upper part
else
return searchBin(A,lo,middle-1,q); // look at lower part
}
/**
*
* @param A
* @param q
* @return returns the first position where the number q occurs in the sorted array A
* (returns −1 if q is not present in A).
* As before, the method assumes that the array A is sorted and need not be correct if A is not sorted.
* Again, exploit the fact that the array is sorted to find an efficient algorithm.
*/
public static int findFirstInSortedArray(int[] A, int q){
return searchBinFirst(A,0,A.length-1,q);
}
private static int searchBinFirst(int[] A, int lo, int hi, int q) {
int middle;
if(lo>hi)
return -1; // not found
middle = (lo+hi)/2; // take the middle index
if(middle==0 || middle==A.length) // found at the beginning or at the end of the array
return middle;
else if(A[middle]==q && A[middle-1]!=q)
return middle; // found first!!
else if(A[middle]<q)
return searchBin(A,middle+1,hi,q); // look at upper part
else
return searchBin(A,lo,middle-1,q); // look at lower part
}
//////////////////////////////////////////////////////////////////////////////////////////////////
// PART 2
/**
*
* @param A
* sorts array A using maxSort algorithm :) by using shiftRight method
*/
public static void maxSortShiftRight(int[] A){
for(int i=0; i<A.length; i++){
int maxPos = ArrayUtility.findMaxPos(A, i, A.length-1); // find the position of max element in the unsorted part
int max = A[maxPos]; // keep the max element
ArrayUtility.shiftRight(A, i, maxPos);
A[i]=max;
}
}
/**
*
* @param A
* sorts array A using maxSort algorithm :) by using Swap method
*/
public static void maxSortSwap(int[] A){
for(int i=0; i<A.length; i++){
int maxPos = ArrayUtility.findMaxPos(A, i, A.length-1); // find the position of max element in the unsorted part
ArrayUtility.swap(A, i, maxPos);
}
}
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
// LAB 2
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////////
// Part 1
// **Bubble Sort:**
//
// for j := 2 to n do // A[1..j-2] sorted and minimum
// for i := n to j do
// if A[i-1] > A[i] then
// swap A[i-1] and A[i]
/**
* implements bubbleSort algorithm
* @param A
*/
public static void bubbleSort(int []A){
for(int j=1 ; j<A.length ; j++ )
for(int i=A.length-1; i>=j ; i--)
if(A[i-1]>A[i])
swap(A,i,i-1);
}
////////////////////////////////////////////////////
// Part 2
// Part 2.1
private static int MAX_M = 10;
private static int ARRAY_LIMITS = 10;
private static long NANOSEC_TO_SEC = 1000000000;
private static int SEC_LIMIT = 5;
public static int findMinMBubbleSort(){
int m=1; // minimal m for which sorting of array 10^m takes >5 sec
for(; m<MAX_M; m++){
int A[]; // random array
long startTime; // start time
long estimatedTime; // current time - start time
A = createRandomArray((int)Math.pow(10,m), -ARRAY_LIMITS,ARRAY_LIMITS);
startTime = System.nanoTime();
bubbleSort(A);
estimatedTime = System.nanoTime() - startTime;
if(estimatedTime > SEC_LIMIT*NANOSEC_TO_SEC){
return m;
}
}
return MAX_M;
}
public static int N_T = 2; // n
public static int MAX_VALUE = 100;
// method should return running times for each array of size n of
// random arrays of sizes 10^i for i=1...m
// plan 2.1
// obtain m [DONE]
//generate T given n and m
//TODO: generate for each i mean value from T
public static long [][] GenerateMatrixTBubbleSort(int n, int m){
long [][] T = new long [m][n]; // matrix that stores running times
int power = 1; // i^10
for(int i=0; i<m; i++){
power = power * 10;
for(int j=0; j<n; j++){
int [] randArray; // random array of size 10^i
long startTime; // start time
long estimatedTime; // current time - start time
randArray = createRandomArray(power, -MAX_VALUE, MAX_VALUE);
startTime = System.nanoTime();
bubbleSort(randArray);
estimatedTime = System.nanoTime() - startTime;
T[i][j] = estimatedTime;
}
}
return T;
}
}