Swapping Numbers in Sorting Algorithms
In this post, I will demonstrate an interesting observation about swapping numbers in sorting algorithms.
When we start learning sorting algorithms (comparison sort), we will definitely need to swap two numbers inside of a sorting algorithm. And a common approach taught by our teacher is:
int temp = array[i];
array[i] = array[min];
array[min] = temp;
However, with time, we may find a better approach to swap two numbers which takes up less memory space without explicitly defining a temporary variable ’temp'.
array[i] = array[i] + array[min];
array[min] = array[i] - array[min];
array[i] = array[i] - array[min];
This approach looks quite fancy and we may think it is more suitable for replacing the code segment of swapping two numbers inside of some comparison sorting algorithms. Hence, we may do that:
public class SelectionSort {
public static void main(String[] args) {
int[] myArr = {3, 6, 1, 88, -1, 5, 6, 7};
selection(myArr);
for (int num : myArr) System.out.print(num + " ");
}
private static void selection(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[min]) min = j;
}
// Replaced Code Segment
array[i] = array[i] + array[min];
array[min] = array[i] - array[min];
array[i] = array[i] - array[min];
}
}
}
However, the code above prints the sorted array as ‘-1 1 3 5 0 6 7 88’. What happened to sorted myArr[4]? Why does my ‘6’ become ‘0’? If we replace the logic of swapping two digits back to the original version, the selection sort works well.
By analyzing each iteration, we spot the problem.
Iteration 1 Swapping: 3 and -1
-1 6 1 88 3 5 6 7
Iteration 2 Swapping: 6 and 1
-1 1 6 88 3 5 6 7
Iteration 3 Swapping: 6 and 3
-1 1 3 88 6 5 6 7
Iteration 4 Swapping: 88 and 5
-1 1 3 5 6 88 6 7
Iteration 5 Swapping: 6 and 6
-1 1 3 5 0 88 6 7
Iteration 6 Swapping: 88 and 6
-1 1 3 5 0 6 88 7
Iteration 7 Swapping: 88 and 7
-1 1 3 5 0 6 7 88
In iteration 5, when we are swapping ‘6’ and ‘6’, the problem occurs. But why? If we look at the code of selection sort, we observe that in this iteration, we cannot find another smaller number so min = i = 4 (min remains as the default value ‘i’). If we simulate the process, array[4] will become 0 because:
array[min] = array[i] - array[min]; // Equal to
array[min] = array[min] - array[min] // Equal to
array[min] = 0
Conclusion
Hence, when we are going to swap two numbers which technically have the same memory address (There is only one value, but sometimes we need to logically swapping it with itself in comparison sorting algorithms). We cannot use this addition/subtraction approach to execute this operation, instead we had better to use the traditional way which defines an extra temporary variable.