Number of swaps and comparisons in bubbling, selecting, inserting, and quicksorting
I have implemented all four sorting algorithms in Java. Just for the sake of it, I decided to look at the number of exchanges and comparisons in each algorithm. For a random array of size 20, here is my result
Bubbling sort: 87 exchanges, 87 comparisons
Insertion sort: 87 swaps, 87 comparisons
Select sorting: 19 swaps, 29 comparisons
Quick Sort: 11940 swap, I don’t even know where to compare it
Why is bubbling sort the same as selection sorting? I mean looking at the code I can almost see it. The cycle is pretty much the same, I just wish someone pointed it out for me.
I understand why the selection sort has the fewest number of exchanges
Quick sort is a mystery to me (damn recursion). I think that’s why there are so many swaps. Why is my implementation so slow? The other three were finished earlier than it.
Code – Please let me know if anything is missing: *******
Swap is the same for all three implementations
private void swap(int firstIndex, int secondIndex) {
int temp = array[firstIndex];
array[firstIndex] = array[secondIndex];
array[secondIndex] = temp;
}
Bubbles
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++;
}
}
}
}
Select
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++;
}
}
Insert
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
}
Primary
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
Solution
As for how operations are calculated, you can always consider adding an indirect layer. For example, use a class like this to 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);
}
}
After modifying your code to use that instrumentation class to evaluate operations, I got 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 the main characteristic of observing comparison sortings is that, in the worst case, they involve comparing each element with all the others. For 20 elements, this is 20 * 19/2 = 190 comparisons, which is basically what your comparison sort implementation produces in each case (less bubbling sorting).
In fact, this is exactly what you expect from bubbling sort and selection sort in each case, but not what you expect from insertion sort in general. That’s because your implementation of insert sorting is flawed: the premise of this sort is that it relies on its intermediate result (the first part of the array in order) to reduce the number of comparisons required. The comparison in the first inner loop fails, so no swap is needed, and you should break from the (inner) loop because you know that no further swap is needed until the next iteration of the outer loop. Implementations reduce the number of comparisons for your specific data to 105.
It also makes sense to compare the number of swaps between sorts: both bubbling sort and insertion sort move each element from its initial position to its final position through a series of swaps with neighboring elements. In effect, your implementations are actually mirrors of each other. However, I’m not prepared to go beyond the actual evidence of this wave.
As for choosing sorting, yes, for sorting n elements, it always performs (n * (n – 1)))/2 comparisons, up to n – 1 swap (exactly n – 1 of them, if you perform and calculate the self-swap).
Then there’s the quick sort. Apparently it’s not very fast – it has something very wrong. More instruments tell me that the recursion depth drops to far too much (about 400 on average, while it shouldn’t exceed n even in the worst case). The problem is your random pivot selection. Instead of selecting a pivot from the subarray being sorted, select it from the entire array. To resolve this issue, replace
int randomIndex = new Random().nextInt(array.length);
with
int randomIndex = left + new Random().nextInt(right + 1 - left);
This should give you more favorable comparisons and swap counts, but you won’t really notice how much advantage quicksort has over other sortings until you start sorting larger arrays.
There are more things you can do to improve your QuickSort implementation, but I don’t see any other well-intentioned bugs.