· Bubble sort
· Selection sort
· Insertion sort
· Merge sort
· Quick sort
Performance tests must be performed and studied in order to chose the correct one when the time comes. It is not the time to test when the job needs to be done.
99
N Time: 00:00:00:0002
99
N-quare Time: 00:00:20:20446
99
BubbleSort based Time: 00:00:26:26496
99
SelectionSort based Time: 00:00:04:4924
99
InsertionSort based Time: 00:00:02:2467
99
MergeSort based Time: 00:00:00:0014
99
QuickSort based Time: 00:00:00:0008
Aiming for your dream job will require you to understand the methodology, code, and operational characteristics or these algorithms. So, spend lots of time analyzing and studying these algorithms and run the code for performance analysis. This will be one of your greatest assets and skills that will get you your dream job and will allow you to keep your dream job for a long time.
public class BiggestDifference {
public static void main(String[] args){
final int SIZE=10000;
int myArray[]= new int[SIZE];
initialize(myArray);
long time=System.currentTimeMillis();
System.out.println(diffItN(myArray));
System.out.printf("N Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
time=System.currentTimeMillis();
System.out.println(diffItNN(myArray));
System.out.printf("N-quare Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
time=System.currentTimeMillis();
System.out.println(diffItNLogN(myArray,"bubble"));
System.out.printf("BubbleSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
initialize(myArray);
time=System.currentTimeMillis();
System.out.println(diffItNLogN(myArray,"selection"));
System.out.printf("SelectionSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
initialize(myArray);
time=System.currentTimeMillis();
System.out.println(diffItNLogN(myArray,"insertion"));
System.out.printf("InsertionSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
initialize(myArray);
time=System.currentTimeMillis();
System.out.println(diffItNLogN(myArray,"merge"));
System.out.printf("MergeSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
initialize(myArray);
time=System.currentTimeMillis();
System.out.println(diffItNLogN(myArray,"quick"));
System.out.printf("QuickSort based Time: %20s\n\n",(getTime(System.currentTimeMillis()-time)));
}
private static void initialize(int a[]){
java.util.Random ran=new java.util.Random();
for(int i=0;i<a.length;i++){
a[i]=ran.nextInt(100);
}
}
private static int diffItN(int a[]){
int largest=a[0];
int smallest=a[0];
for(int i=1;i<a.length;i++){
if(a[i]>largest)
largest=a[i];
if(a[i]<smallest)
smallest=a[i];
}
return largest-smallest;
}
private static int diffItNN(int a[]){
int difference = 0,diff=0;
for(int n1:a){
for (int n2:a){
difference = n1 - n2;
if(difference > diff)
diff = difference;
}
}
return diff;
}
private static int diffItNLogN(int a[],String s){
switch(s){
case "bubble":
bubbleSort(a);
break;
case "selection":
selectionSort(a);
break;
case "insertion":
insertionSort(a);
break;
case "merge":
mergeSort(a);
break;
case "quick":
quickSort(a,0,a.length-1);
break;
}
return (a[0]>a[a.length-1])?a[0]-a[a.length-1]:a[a.length-1]-a[0];
}
private static void bubbleSort( int [ ] num ) {
int j;
boolean flag = true;
int temp;
while ( flag ){
flag= false;
for( j=0; j < num.length -1; j++ ) {
if ( num[ j ] < num[j+1] ) {
temp = num[ j ];
num[ j ] = num[ j+1 ];
num[ j+1 ] = temp;
flag = true;
}
}
}
}
private static void selectionSort ( int []num ){
int i, j, first, temp;
for ( i = num.length - 1; i > 0; i-- ) {
first = 0;
for(j = 1; j <= i; j ++){
if( num[ j ] < num[ first ] )
first = j;
}
temp = num[ first ];
num[ first ] = num[ i ];
num[ i ] = temp;
}
}
private static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
}
System.out.println();
}
private static void mergeSort(int [ ] a){
int[] tmp = new int[a.length];
mergeSort(a, tmp, 0, a.length - 1);
}
private static void mergeSort(int [ ] a, int [ ] tmp, int left, int right){
if( left < right ){
int center = (left + right) / 2;
mergeSort(a, tmp, left, center);
mergeSort(a, tmp, center + 1, right);
merge(a, tmp, left, center + 1, right);
}
}
private static void merge(int[ ] a, int[ ] tmp, int left, int right, int rightEnd ){
int leftEnd = right - 1;
int k = left;
int num = rightEnd - left + 1;
while(left <= leftEnd && right <= rightEnd)
if(a[left]<a[right])
tmp[k++] = a[left++];
else
tmp[k++] = a[right++];
while(left <= leftEnd)
tmp[k++] = a[left++];
while(right <= rightEnd)
tmp[k++] = a[right++];
for(int i = 0; i < num; i++, rightEnd--)
a[rightEnd] = tmp[rightEnd];
}
private static void quickSort(int a[], int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = a[lowerIndex+(higherIndex-lowerIndex)/2];
while (i <= j) {
while (a[i] < pivot) {
i++;
}
while (a[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(a,i, j);
i++;
j--;
}
}
if (lowerIndex < j)
quickSort(a,lowerIndex, j);
if (i < higherIndex)
quickSort(a,i, higherIndex);
}
private static void exchangeNumbers(int a[],int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static String getTime(long millis){
long second = (millis / 1000) % 60;
long minute = (millis / (1000 * 60)) % 60;
long hour = (millis / (1000 * 60 * 60)) % 24;
return String.format("%02d:%02d:%02d:%04d", hour, minute, second, millis);
}
}
No comments:
Post a Comment