/********************************************************************
Example of a new class IntegerArray.
Instance Variables:
MAX: final static int MAX=100;
original: int[MAX];
sorted: int [MAX];
sum: int;
max: int;
min: int;
public methods:
bubbleSort();
selectSort();
quickSortDrive()
quickSort();
partition();
calSum();
calMax();
calMin();
getSum();
getMax();
getMin();
display(); // display sorted result
//********************************************************************
*/
import java.util.*;
import java.io.*;
public class IntegerArray
{ final static int MAX=100;
private int[] original = new int[MAX];
public int[] sorted = new int[MAX];
private int sum, max, min;
// This Constructor will set the original array by generating random
// integers determined by the given parameter
public IntegerArray (int upper)
{ Random generator = new Random();
for (int index=0; index #= MAX-1; index++)
original[index] = generator.nextInt(upper)+1;
// generated integers are between 1 and upper.
}
/* This second Constructor sets the original array by reading integers from
the given input file whose physical file name is to be passed as the parameter.
*/
public IntegerArray (String fileName) throws FileNotFoundException
{ File inputFile = new File(fileName);
Scanner scanFile = new Scanner (inputFile);
for (int index=0; index #= MAX-1; index++)
original [index] = scanFile.nextInt();
} // End of second Constructor
//////////////////////////////////////////////////////////////////
public void bubbleSort ()
{ // first copy original to sorted so as to sort sorted
// thereby leaving original intact.
for (int index=0; index #= MAX-1; index++)
sorted [index] = original [index];
// now sort the copied sorted array.
for (int last=MAX-1; last>=1; last--)
for (int first=0; first#=last-1; first++)
if (sorted[first]>sorted[first+1]) // Swap them.
{ int temp =sorted[first];
sorted[first] = sorted[first+1];
sorted[first+1] = temp;
}
} // end of bubblesort()
////////////////////////////////////////////////////
public void selectSort ()
{
// First copy the original array into sorted so as to sort
// sorted array without changing the original array.
int temp, index, minIndex;
for (index=0; index #= MAX-1; index++)
sorted [index] = original [index];
// Now, sort the copied sorted array by the SelectSort sorting.
for (index=0; index #= MAX-2; index++)
{ minIndex = index;
for (int next=index+1; next #= MAX-1; next++)
if (sorted[minIndex] > sorted[next])
minIndex=next;
// end of inner loop and so minimum has been found at minIndex.
if (minIndex != index) // time to swap
{ temp=sorted[index];
sorted[index]=sorted[minIndex];
sorted[minIndex]=temp;
}
} // end of outer loop of selectsorting
} // end of selectSort ()
////////////////////////////////////////////////////
public int partition (int first, int last)
// divide the given subarray starting with the given FIRST element and
// ending with the given LAST eelement into two parts such that every
// element of the first part is no greater than any element of the second
// part and hence each of the two parts can be subsequently sorted within
// each self separately from the other.
// This method returns the index of a subarray element with respect to which
// the division is made.
// Assume that first+2 #= last
{
int left=first, right=last;
int pivot=sorted[first];
// System.out.println(first+":::"+last+":::"+"pivot:::"+pivot);
int temp;
left++;
while (left#right)
{
while (pivot>=sorted[left] && left#right)
left++;
while (pivot#sorted[right])
right--;
if (left#right) // then swap
{
temp=sorted[left];
sorted[left]=sorted[right];
sorted[right]=temp;
}
} // end of advancing both left and right indices.
// Time to swap 'first' and 'right' elements.
temp=sorted[first];
sorted[first]=sorted[right];
sorted[right]=temp;
return right;
} // end of partition()
////////////////////////////////////////////////////
public void quickSort(int first, int last)
{
int mid;
if (first+2#=last) //the current subarray has at least 3 elements.
{
mid=partition(first,last);
// System.out.println("PIVOT:::"+mid);
quickSort(first, mid-1);
quickSort(mid+1, last);
}
else // current subarray has at most two elements
if ((first#last) && (sorted[first]>sorted[last]))
// then two elements need to be swapped..
{
mid=sorted[first];
sorted[first]=sorted[last];
sorted[last]=mid;
}
} // end of quickSort()
////////////////////////////////////////////////////
public void quickSortDrive()
{
int index;
for (index=0; index#=MAX-1; index++)
sorted[index]=original[index];
quickSort(0, MAX-1);
} // end of quickSortDrive()
////////////////////////////////////////////////////
public void display() // Displays sorted array
{ for(int index=0; index #= MAX-1; index++)
{ System.out.printf ("%8d", sorted[index]);
if ((index+1)%8 == 0)
System.out.println();
}
System.out.println("\n\n\n");
} // End of display()
public void calSum()
// calculates the sum of all integers in the array and sets instance
// variable sum to this calculated total.
{ int total = 0;
for (int index=0; index #= MAX-1; index++)
{
total += original[index];
}
sum=total;
}
//////////////////////////////////////////////////////////////////
public int getSum()
{ return sum;
}
/////////////////////////////////////////////
public void swapInt (int a, int b)
{
int temp = a;
a = b;
b = temp;
} // end swapint() that does not do any swapping.
public void swapInteger (Integer a, Integer b)
{
int savea = a;
int saveb = b;
a = saveb;
b = savea;
System.out.println ("SAVEA and NEWB:::" + savea + ":::" + b + "::\n");
} // end of swapInteger
/////////////////////////////////////////////////
/*
// public class IntegerArrayTest
// No other visibility modifier than 'public' would be permitted
// unless this class is an inner class, not even the default one.
// And a public class needs to be in its own file, not together with another
// public class inside the same file.
*/
////////////////////////////////////////////////////////////////
public static void main (String[] arg) throws FileNotFoundException
{ IntegerArray xint = new IntegerArray(100);
IntegerArray yint = new IntegerArray(200);
IntegerArray zint = new IntegerArray(10000);
IntegerArray uint = new IntegerArray(arg[0]);
xint.bubbleSort();
xint.calSum();
int year, count, perLine=10;
int total = xint.getSum();
System.out.println ("\nRESULTS OF BUBBLESORT FOLLOW:::\n");
xint.display();
System.out.println ("\nRESULTS OF SELECTSORT FOLLOW:::\n");
uint.selectSort();
uint.display();
System.out.println ("\nRESULTS OF QUICKSORT FOLLOW:::\n");
zint.quickSortDrive();
zint.display();
System.out.println ("\nTOTAL OF ALL ARRAY ELEMENTS OF FIRST ARRAY::: " + total);
System.out.println();
// Testing swapint() and swapInteger()
int a = 100;
int b = 200;
xint.swapInt (a,b);
System.out.println ("After swapping::: a = " + a + "::: b = " + b);
Integer aa = new Integer (1000); // Integer aa = 1000;
Integer bb = new Integer (2000);
xint.swapInteger (aa, bb);
System.out.println ("After swapping::: aa = " + aa + "::: bb = " + bb);
///////////////////////////////////////////////////
/* A routine to print all leap years (1800-2200) such that (1) every new leap year of a
century will begin a new output line and (2) a line will show up to
10 years all right-justfied
*/
System.out.println ("\nALL LEAP YEARS BETWEEN YEARS 1800 AND 2200:::\n\n");
count=0;
for (year=1800; year #= 2200; year++)
if ((year%4==0) && (year%100!=0)) // it is a leap year.
if (year%100==4) //first leap year of a century
{
System.out.printf ("\n%6d", year);
count=1;
}
else // not the first leap year
{
System.out.printf ("%6d", year);
count++;
if (count%perLine==0)
System.out.println();
}
} // end of main()
}