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;
}
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)