Question

Write a JAVA Program:

Compare the performance of bubble sort and selection sort over several arrays.

- Write two methods that sort arrays of doubles. One method should use selection sort, and the other should use bubble sort.

- In each of the sort methods, add code that counts the total number of comparisons and total number of swaps performed while sorting the entire array (be careful; don't count each pass through the array separately)

- Each time an array is sorted, print out the name of the algorithm used (selection or bubble), the number of comparisons, and the number of swaps. You may print these out from within the sort function; you do not need to figure out how to pass these values back to main()

- In main(), create several arrays and run the sort algorithms for each of them. Include one array that is already sorted, one that is sorted in descending order, one that has no obvious order, and one or two other ones that use whatever patterns you think are interesting.

Answer 1

Hi Dear,

Please find my basic implementation.

import java.util.Random;

public class SortComparisons

{
    public static void selectionSort(int arr[])
    {
        int n = arr.length;

        int comparison = 0;

        int swaps = 0;
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++) {
                comparison++;
                if (arr[j] < arr[min_idx])
                    min_idx = j;
            }

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;

            swaps++;
        }

        System.out.println("Selection Sort: ");
        System.out.println("\tComparisons : " + comparison);

        System.out.println("\tSwaps : " + swaps);
    }

    // function to sort array a using bubble sort

    public static void bubble_sort(int a[])
    {
        int i, j, x;
        int comparison = 0;
        int swaps = 0;


        for( i = 0 ; i < a.length - 1 ; i++)
        {
            for( j = 0 ; j < a.length - i - 1 ; ++j)
            {
                // increment the comparison count
                comparison++;

                if (a[ j + 1 ] < a[ j ])
                {
                    // increment the swap count
                    swaps++;
                    // swap the j and j + 1 th element of a

                    x = a[j];

                    a[ j ] = a[ j + 1 ];

                    a[ j + 1 ] = x;

                }

            }

        }


        System.out.println("Bubble Sort: ");
        System.out.println("\tComparisons : " + comparison);
        System.out.println("\tSwaps : " + swaps);

    }



    public static void main(String args[])

    {

        //Create test array

        int[] test = new int[100];
        int[] test1 = new int[100];

        Random rand = new Random();

        for(int i=0; i<test.length; i++) {
            int r = rand.nextInt(1000);//0 - 999
            test[i] =  r;
            test1[i] =  r;
        }


        //Sort it - Students replace this with your sort (bubble, merge, or quick)

        bubble_sort(test);

        selectionSort(test1);
    }

}

Output:

Bubble Sort:

Comparisons : 4950

Swaps : 2337

Selection Sort:

Comparisons : 4950

Swaps : 99

Process finished with exit code 0

Please DONT forgot to rate my answer. We are working hard for you Guys!!

Answer 2

import java.util.Random; 
public class SortComparisons { 
public static void selectionSort(int arr[]) 
{ 
int n = arr.length;
 int comparison = 0;
  int swaps = 0; 
  for (int i = 0; i < n-1; i++) { 
   int min_idx = i;
    for (int j = i+1; j < n; j++) {
     comparison++;
      if (arr[j] < arr[min_idx]) 
      min_idx = j; 
      } // 
       int temp = arr[min_idx]; 
       arr[min_idx] = arr[i]; 
       arr[i] = temp; 
       swaps++; 
       } 
   System.out.println("Selection Sort: ");
   System.out.println("\tComparisons : " + comparison); 
   System.out.println("\tSwaps : " + swaps); } 
public static void bubble_sort(int a[]) { 
int i, j, x; 
int comparison = 0; 
int swaps = 0; 
for( i = 0 ; i < a.length - 1 ; i++) { 
for( j = 0 ; j < a.length - i - 1 ; ++j) { 
comparison++; 
if (a[ j + 1 ] < a[ j ]) { 
 swaps++;  
 x = a[j]; 
 a[ j ] = a[ j + 1 ]; 
 a[ j + 1 ] = x; 
 } 
 }
} 
System.out.println("Bubble Sort: "); 
System.out.println("\tComparisons : " + comparison); 
System.out.println("\tSwaps : " + swaps); 
} 
public static void main(String args[]) { 
 int[] test = new int[100]; 
 int[] test1 = new int[100]; 
 Random rand = new Random(); 
 for(int i=0; i<test.length; i++) { 
 int r = rand.nextInt(1000);//0 - 999 
 test[i] = r; 
 test1[i] = r; 
}  
bubble_sort(test); 
selectionSort(test1); 
} 
}