SelectionSort and BubbleSort - how to count number of comparisons and number swapping?

Rob picture Rob · Mar 21, 2013 · Viewed 16.1k times · Source

First of all, I have seen a similar question relating to C++, but I didn't quite understand it - plus my question is about Java.

Basically I have coded two methods that can use SelectionSort and BubbleSort on an array parsed in. While I believe I have the methods working correctly (I have run tests and they all have sorted the numbers in ascending order), I am not sure if I am counting the number of comparisons and number swaps correctly. If someone is able to test my code below and offer some feedback, I will be very grateful.

Note: I can zip up my Java project files and send them to anyone if needed.

BubbleSort method:

public String bubbleSort(int[] numbers)
    {
        System.out.println("******|Bubble Sort|******");
        StringBuilder originalArray = new StringBuilder();

        for(int i = 0; i <= numbers.length - 1; i++)
        {
            originalArray.append(numbers[i] + " ");
        }
        System.out.println("Original array: " + originalArray);
        int temp; // temporary variable

        //Set boolean variable to true, 
        //to allow the first pass.
        boolean pass = true;

        int comparisons = 0;
        int swaps = 0;

        //While a pass can be made, 
        while(pass)
        {
            //Set the boolean value to false, 
            //indicating a number swap could 
            //be made.
            pass = false;

            for(int i = 0; i < numbers.length - 1; i++)
            {
                //increment the number of comparisons by 1.
                comparisons++;
                if(numbers[i] > numbers[i+1])
                {
                    temp = numbers[i];
                    numbers[i] = numbers[i + 1];
                    numbers[i+1] = temp;

                    //increment the amount of swaps made by 1, 
                    //to put numbers in correct order.
                    swaps++;
                    pass = true;
                }
            }
        }

        //Create a StringBuilder object - to hold 
        //the output of sorted numbers.
        StringBuilder sb = new StringBuilder();

        //Loop through the now sorted array - appending 
        //each subsequent number in the array to the 
        //StringBuilder object.
        for(int i = 0; i < numbers.length; i++)
        {
            sb.append(numbers[i] + " ");
        }

        //Return the final results of the sorted array.
        return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
                + "\nSwaps made: " + swaps;
    }

SelectionSort method

public String selectionSort(int[] numbers)
    {
        System.out.println("******|Selection Sort|******");
        StringBuilder originalArray = new StringBuilder();

        int comparisons = 0;
        int swaps = 0;

        for(int i = 0; i <= numbers.length - 1; i++)
        {
            originalArray.append(numbers[i] + " ");
        }
        System.out.println("Original array: " + originalArray);

        //Declare variable to hold first element
        int first;

        //declare temporary variable, to be used in 
        //swapping integers.
        int temp;

        for(int x = numbers.length - 1; x > 0; x--)
        {
            first = 0;
            comparisons++;
            for(int y = 1; y <= x; y++)
            {
                //comparisons++;
                if(numbers[y] > numbers[first])
                {
                    first = y;
                    //comparisons++;
                    swaps++;
                }
                temp = numbers[first];
                numbers[first] = numbers[x];
                numbers[x] = temp;
                //swaps++;
            }
        }

        //Create a StringBuilder object - to hold 
        //the output of sorted numbers.
        StringBuilder sb = new StringBuilder();

        //Loop through the now sorted array - appending 
        //each subsequent number in the array to the 
        //StringBuilder object.
        for(int i = 0; i < numbers.length; i++)
        {
            sb.append(numbers[i] + " ");
        }

        //Return the final results of the sorted array.
        return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
                + "\nSwaps made: " + swaps;
    }

Answer

Jessekiel Ragos picture Jessekiel Ragos · Dec 5, 2014

For BUBBLE SORT:

Key comparisons -> (n*(n-1))/2

Item assignments (swaps) -> 3*(n-1)

For SELECTION SORT:

Key comparisons -> (n*(n-1))/2 (same as bubble)

Item assignments (swaps) -> (n*(n-1))/4

(Note that n is the number of your array size)