I was trying out insertion and selection sort. Here is the code :
#include <iostream>
using namespace std;
void selectionSort(int nos[], int len){
// int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};
for(int i=0;i<len;i++){
int min_value = 0x7fffffff;int temp = nos[i];
int index_of_min_value;
for(int j=i;j<len;j++){
if(nos[j] < min_value){
min_value = nos[j];
index_of_min_value = j;
}
}
nos[i] = min_value;
nos[index_of_min_value] = temp;
}
}
void insertionSort(int nos[], int len){
for(int i=1;i<len;i++){
for(int j=i;j>0;j--){
if(nos[j] > nos[j-1]){
break;
}
int temp = nos[j-1];
nos[j-1] = nos[j];
nos[j] = temp;
}
}
}
void printElementsOfArray(int nos[], int len){
for(int i=0;i<len;i++)
cout << nos[i] << endl;
cout << endl;
}
int main()
{
int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
int len = sizeof(nos1)/sizeof(int);
insertionSort(nos1, len);
printElementsOfArray(nos1, len);
selectionSort(nos2, len);
printElementsOfArray(nos2, len);
return 0;
}
I got the input as expected.
7
9
13
23
24
34
47
64
7
9
13
23
24
34
47
64
But, now i wanted to try out xor swaps instead of temporary variable swaps. (something that i learnt recently : =) ) Below is the updated code for selection sort.
void selectionSort(int nos[], int len){
// int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};
for(int i=0;i<len;i++){
int min_value = 0x7fffffff;
int index_of_min_value;
for(int j=i;j<len;j++){
if(nos[j] < min_value){
min_value = nos[j];
index_of_min_value = j;
}
}
nos[i] ^= nos[index_of_min_value];
nos[index_of_min_value] ^= nos[i];
nos[i] ^= nos[index_of_min_value];
}
Now the output
7
9
13
23
24
34
47
64
7
9
0
23
0
34
47
0
Hmm...interesting! I was puzzled. I knew that was the right code for swapping but what's that.
I printed out the array state after each swap in selection sort.
#include <iostream>
using namespace std;
void printElementsOfArray(int nos[], int len){
for(int i=0;i<len;i++)
cout << nos[i] << " ";
cout << endl;
}
void selectionSort(int nos[], int len){
// int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};
for(int i=0;i<len;i++){
int min_value = 0x7fffffff;
int index_of_min_value;
for(int j=i;j<len;j++){
if(nos[j] < min_value){
min_value = nos[j];
index_of_min_value = j;
}
}
nos[i] ^= nos[index_of_min_value];
nos[index_of_min_value] ^= nos[i];
nos[i] ^= nos[index_of_min_value];
printElementsOfArray(nos, len);
}
}
int main()
{
int nos1[] = {24, 13, 9, 64, 7, 23, 34, 47};
int nos2[] = {24, 13, 9, 64, 7, 23, 34, 47};
int len = sizeof(nos1)/sizeof(int);
insertionSort(nos1, len);
// printElementsOfArray(nos1, len);
selectionSort(nos2, len);
// printElementsOfArray(nos2, len);
return 0;
}
I get the output
// int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};
7 13 9 64 24 23 34 47 ->step 1
7 9 13 64 24 23 34 47 ->step 2
7 9 0 64 24 23 34 47 ->step 3
7 9 0 23 24 64 34 47
7 9 0 23 0 64 34 47
7 9 0 23 0 34 64 47
7 9 0 23 0 34 47 64
7 9 0 23 0 34 47 0
In step 3, we know the problem. XOR swap works on two separate variables but in step 3 we are swapping it with itself. In other words we are doing a^a three times which will always be 0.
Ahh.. The lesson , If you want to use xor swaps, make sure you are not swapping the same place.
Here was a quick fix.
void selectionSort(int nos[], int len){
// int nos[] = {24, 13, 9, 64, 7, 23, 34, 47};
for(int i=0;i<len;i++){
int min_value = 0x7fffffff;
int index_of_min_value;
for(int j=i;j<len;j++){
if(nos[j] < min_value){
min_value = nos[j];
index_of_min_value = j;
}
}
if( i != index_of_min_value){
nos[i] ^= nos[index_of_min_value];
nos[index_of_min_value] ^= nos[i];
nos[i] ^= nos[index_of_min_value];
}
}
}
