TSORT : Swapping of 2 numbers using bitwise XOR

general
, ,
1

int main(int argc, char const *argv[])
{
int array[1000000];
int i=0,num,j;
scanf("%d",&num);
while(num–)
{
scanf("%d",&array[i]);
i++;
}
quicksort(array,0,i-1);
for (j = 0; j < i ; ++j)
{
printf("%d\n",array[j]);
}
}

void quicksort(int *array,int lower, int upper)
{
    int i;
    if (lower<upper)
    {
         i=split(array,lower,upper);
         quicksort(array,lower,i-1);
         quicksort(array,i+1,upper);
    }
}

int split(int *array_quicksort,int lower,int upper)
{
    int a=lower+1;
    int b=upper;
    int i,temp;
    i=array_quicksort[lower];
    while(b>=a)
    {
        while(array_quicksort[a]<i)
        {
          a++;
        }
    while(array_quicksort[b]>i)
    {
        b--;
    }
    /*printf("----------check----------\n");
    printf("%d %d\n",array_quicksort[a],array_quicksort[b]);*/
    if (b>a)
    {
        /*temp=array_quicksort[a];
        array_quicksort[a]=array_quicksort[b];
        array_quicksort[b]=temp;*/

        array_quicksort[a]=array_quicksort[a]^array_quicksort[b];
        array_quicksort[b]=array_quicksort[a]^array_quicksort[b];
        array_quicksort[a]=array_quicksort[a]^array_quicksort[b];
    }
    /*printf("----------check----------\n");
    printf("%d %d\n",array_quicksort[a],array_quicksort[b]);*/
}

temp=array_quicksort[lower];
array_quicksort[lower]=array_quicksort[b];
array_quicksort[b]=temp;

/*SECTION 2 */
/*i=array_quicksort[b]^i;
array_quicksort[b]=array_quicksort[b]^i;
i=array_quicksort[b]^i;*/

/*SECTION 3 */
/*array_quicksort[lower]=array_quicksort[b]^array_quicksort[lower];
array_quicksort[b]=array_quicksort[b]^array_quicksort[lower];
array_quicksort[lower]=array_quicksort[b]^array_quicksort[lower];*/
return b;
 }

I was trying to solve the TSORT problem intially I thought Quick sort was the solution to the problem but when I implemented it had shown the Time Limit Exceeded error so I thought to speed up the swapping by implementing it using the bitwise XOR operation I encountered 2 problems ::

Well firstly , it didnt work and I still have a TLE.
Secondly I tried to minimize the run time by using all the possibilities commented in Section 2 and Section 3.Because nothing was clicking me at that moment so i tried all the combinations something what poor programmers often do and yes I am guilty. But although both the snippets seems to be the same but they are giving me different results. I tried to trace the solution but I am not able to because of the looping constructs.

2

Hello, merge sort will pass all the testcases with in timelimit.Even qsort will pass.Here is my solution with qsort() : http://www.codechef.com/viewsolution/4267858

3

So basically what is your question?

If you wan a better algorithm for solving TSORT then here it is:

For problem TSORT Counting sort is the best sorting technique i found.

Here is the Algorithm:

# variables:
#    input -- the array of items to be sorted; key(x) returns the key for item x
#    n -- the length of the input
#    k -- a number such that all keys are in the range 0..k-1
#    count -- an array of numbers, with indexes 0..k-1, initially all zero
#    output -- an array of items, with indexes 0..n-1
#    x -- an individual input item, used within the algorithm
#    total, oldCount, i -- numbers used within the algorithm
 
# calculate the histogram of key frequencies:
for x in input:
    count[key(x)] += 1
 
# calculate the starting index for each key:
total = 0
for i in range(k):   # i = 0, 1, ... k-1
    oldCount = count[i]
    count[i] = total
    total += oldCount
 
# copy to output array, preserving order of inputs with equal keys:
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
 
return output

Take a look at my submission:

http://www.codechef.com/viewsolution/5204230

Let me explain you if you don’t know about counting sort, btw let me tell you that guy at the top of problem scoreboard used counting sort to solve this problem.

Consider constraints as: Input number be <= 10, instead of 10^6.

Then,

Sample Input:
5
1
2
3
1
4

Initialize an array of size 12 (lets say a[12]) and assign 0 to each index either using memset() or using a for loop.

i.e. a[12] should be [0,0,0,0,0,0,0,0,0,0,0,0]

Get the input (say variable inp) from stdin and increment a[inp] by 1.

as input is 1 2 3 1 4,

So your code should work like:

inp=1, a[1]++ , [0,1,0,0,0,0,0,0,0,0,0,0]

inp=2, a[2]++ , [0,1,1,0,0,0,0,0,0,0,0,0]

inp=3, a[3]++ , [0,1,1,1,0,0,0,0,0,0,0,0]

inp=1, a[1]++ , [0,2,1,1,0,0,0,0,0,0,0,0]

inp=4, a[4]++ , [0,2,1,1,1,0,0,0,0,0,0,0]

Thats it,

Now using 2 for loop one to iterate over array a and second for range of values of array a print index,

i.e.

for(i=0;i<size;i++)
{
    for(j=0;j<a[i];j++)
        print(i);
}

Output will be :
2 times 1, 1 time 2, 3 and 4.

Output:
1
1
2
3
4

Code execution time : 0.56 sec using fast input and output

Hope You understood… :slight_smile:

4

@rishabhprsd7 Thankyou so much … I have clearly understood the algorithm …
My initial Question was as u can see in the while looping construct no where im changing the value of i or array_quicksort[lower] but on running both the sections separately I am get different answers why is that?
Also swapping when performed with XOR why is that im not getting a sorted output?