number of swaps and comparisons in bubble, selection, insertion and quick sorts
I have implemented all the four sorting algorithms in Java. Just for the hell of it, I decided to look at the number of swaps and comparison in each algorithm. For a random array of size 20, here's my results
Bubble Sort: 87 swaps , 87 comparisons
Insertion Sort: 87 swaps, 87 comparisons
Selection Sort: 19 swaps, 29 comparisons
Quick Sort: 11940 swaps, I didn't even know where to count the comparisons from
Why is bubble sort and selection sort identical? I mean looking at the code I can almost see it. The loops are pretty much the same, I just would like someone to point it out for me.
I can see why selection sort has the least number of swaps
Quick sort is mystery to me (damn you recursion). I think that's why the number of swaps is insane. why is my implementation so slow? the other three finishes way before it.
***** The code - let me know if anything's missing *******
Swap is indentical for all three implementation
private void swap(int firstIndex, int secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
Bubble
public void sort() {
for(int out = nElements-1; out > 1; out--) {// outer backwards loop
for(int in = 0; in < out; in++) { // inner forward loop
if(array[in] > array[in+1]) {
swap(in, in + 1);
totalSwaps++;
totalComparisons++;
}
}
}
}
Selection
public void sort() {
for (int i = 0; i < nElements-1; i++) {
int currentMinIndex = i;
for (int j = i + 1; j < nElements; j++)
if (array[j] < array[currentMinIndex]) {
currentMinIndex = j;
totalComparisons++;
}
swap(i, currentMinIndex);
totalSwaps++;
}
}
Insertion
public void sort() {
for(int i = 1; i < nElements; i++) {
for(int j = i; j > 0; j--) {
if(array[j] < array[j-1]) {
swap(j, j - 1);
totalSwaps++;
totalComparisons++;
}
}
}
}
Quick Sort
public void sort() {
sort(this.array, 0, array.length - 1);
}
private void sort(int[] array, int left, int right) {
if(left >= right)
return;
int randomIndex = new Random().nextInt(array.length);
int pivot = array[randomIndex];
// returns the dividing point between the left side and the right side
int index = partition(array, left, right, pivot);
sort(array, left, index - 1);
sort(array, index, right);
}
private int partition(int[] array, int left, int right, int pivot) {
while(left <= right) {
while(array[left] < pivot) // will break when there's an element to the left of the pivot that's greater
left++;
while(array[right] > pivot) // breaks when there's an element to the right of the pivot that's less
right--;
if(left <= right) {
swap(left, right);
left++;
right--;
totalSwaps++;
}
}
return left; // left will be at the partition point
}
Main
import java.util.Random;
public class Sorting {
private static final int maxSize = 50;
private static int[] randomArray() {
int[] array = new int[maxSize];
Random random = new Random();
random.setSeed(0);
for(int i = 0; i < maxSize; i++)
array[i] = random.nextInt(50);
return array;
}
public static void main(String[] args) {
int[] randomArr = randomArray();
BubbleSort bubbleSort = new BubbleSort(randomArr);
bubbleSort.display();
bubbleSort.sort();
bubbleSort.display();
randomArr = randomArray();
SelectionSort selectionSort = new SelectionSort(randomArr);
selectionSort.sort();
selectionSort.display();
randomArr = randomArray();
InsertionSort insertionSort = new InsertionSort(randomArr);
insertionSort.sort();
insertionSort.display();
System.out.println("Bubble Sort: Swaps = " + bubbleSort.totalSwaps + " Comparisons = " + bubbleSort.totalComparisons);
System.out.println("Selection Sort: Swaps = " + selectionSort.totalSwaps + " Comparisons = " + selectionSort.totalComparisons);
System.out.println("Insertion Sort: Swaps = " + insertionSort.totalSwaps + " Comparisons = " + insertionSort.totalComparisons);
randomArr = randomArray();
QuickSort quickSort = new QuickSort(randomArr);
quickSort.sort();
quickSort.display();
System.out.println("Quick Sort: Swaps = " + quickSort.totalSwaps);
}
}
Output
10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20 // original
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // bubble
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // selection
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // insertion
Bubble Sort: Swaps = 87 Comparisons = 87
Selection Sort: Swaps = 19 Comparisons = 29
Insertion Sort: Swaps = 87 Comparisons = 87
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48 // quick
Quick Sort: Swaps = 25283
Answer
As to how to count operations, you could always consider adding a layer of indirection. For example, use a class such as this one to both perform and count operations:
class Instrumentation {
int compares = 0;
int swaps = 0;
boolean compareLess(int left, int right) {
compares++;
return left < right;
}
boolean compareGreater(int left, int right) {
compares++;
return left > right;
}
void swap(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
swaps++;
}
void printResult(String label) {
System.out.print(label);
System.out.print(": Swaps = ");
System.out.print(swaps);
System.out.print(" Comparisons = ");
System.out.println(compares);
}
}
Having modified your code just enough to use that instrumentation class to count operations, I get these results:
Original data:
10 48 29 47 15 3 41 11 19 4 27 27 23 12 45 44 34 25 41 20
BubbleSort: Swaps = 87 Comparisons = 189
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
SelectionSort: Swaps = 19 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
InsertionSort: Swaps = 87 Comparisons = 190
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
QuickSort: Swaps = 3221 Comparisons = 110575
3 4 10 11 12 15 19 20 23 25 27 27 29 34 41 41 44 45 47 48
Now observe that the main characteristic of comparison sorts is that in the worst case, they involve comparing every element to every other element. For 20 elements, that's 20 * 19 / 2 = 190 comparisons, which is basically what your comparison-sort implementations produce in every case (less one for the bubble sort).
That's in fact what you expect for Bubble and Selection sort in every case, but not what you expect for Insertion sort in the average case. And that's because your Insertion sort implementation is flawed: the premise of this sort is that it relies on its intermediate results (putting the first part of the array in order) to reduce the number of comparisons required. The first time the comparison in the inner loop fails, so that no swap is necessary, you ought to break from the (inner) loop because you know that no further swaps will be necessary until the next iteration of the outer one. Implementing that reduces the number of comparisons to 105 for your particular data.
The numbers of swaps among the comparison sorts also makes sense: both Bubble sort and Insertion sort move each element from its initial position to its final one via a series of swaps with adjacent elements. Indeed, your implementations are practically mirror images of each other. I am not prepared to go beyond this hand waving to an actual proof, however.
As for Selection sort, yes, for sorting n elements it always performs (n * (n - 1)) / 2 comparisons, and up to n - 1 swaps (exactly n - 1 of them if you perform and count self-swaps).
And then there's your Quick sort. Clearly it's not very quick -- there's something terribly wrong with it. A little bit more instrumentation tells me that it's descending to far too great a recursion depth (about 400 on average, whereas it should not exceed n even in the worst case). The issue is with your random pivot selection. Instead of choosing a pivot from within the sub-array being sorted, you choose it from the whole array. To fix that, replace
int randomIndex = new Random().nextInt(array.length);
with
int randomIndex = left + new Random().nextInt(right + 1 - left);
That should give you much more favorable counts of both comparisons and swaps, but you won't really notice how much of an advantage Quick sort provides over the others until you start sorting much larger arrays.
There's more you could do to improve your QuickSort implementation, but I don't see any other bona fide errors.