## 10810 - Ultra-QuickSort

Moderator: Board moderators

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:
harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

### 10810 confuse

can any one explain why the output for
5 9 1 0 5 4
is 6
it seems to be 5 for me using mergesort

here is my code

#include<stdio.h>
#include<stdlib.h>
#define Max 500000
#define MaxValue 999999999

long long int A[Max+2],temp[Max+2],R[Max+2],swap,s,n,inf = MaxValue+1;

void merge(long long int numbers[],long long int temp[],long long int left,long long int mid,long long int right)
{
long long int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;

swap++;

}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
void m_sort(long long int numbers[], long long int temp[], long long int left, int right)
{
long long int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}

void mergeSort(long long numbers[], long long int temp[], long long int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}

int main()
{
long long int i;

while(1)
{
scanf("%lld",&n);
if(!n)break;
i=0;
while(i<n)
{
scanf("%lld",&A);
i++;
}
s=swap=0;
mergeSort(A,temp,n);
//qsort(&a,n,sizeof(a),sort);
printf("%lld\n",swap);
//printf("%d\n",s);
}

return 0;
}

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
9 1 0 5 4
9 0 1 5 4
0 9 1 5 4
0 1 9 5 4
0 1 9 4 5
0 1 4 9 5
0 1 4 5 9

There are 7 states and 6 steps. It's easy to see that this is the optimal solution.

In fact, it's also easy to see that what we should find is the number of inversions in the sequence (inversion is a situation when a > a[i + k]). In your sequence, there are 6 inversions (9 1, 9 0, 9 5, 9 4, 1 0, 5 4), hence the result.

I don't know what do you count with your mergesort - my algorithm is also based on divide and conquer and it gives correct answers.
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
swap++;
is not enough. Imagine, for example, an extreme (non-balanced) case of say:

100 101 102 103 104 105 106 107 1

and your partition is magically given as:
100 101 102 103 104 105 106 107
and
1

then you would return the number of swaps as 1.
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
if anyone gets WA after using long long, try this case:

Input
5
5
2
3
4
1
Output
7
nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:
filigabriel wrote:
technobug wrote:How fast is your D+C algorithm? What is its idea?
My original program runs in 1.150 seconds

Main idea was already posted by Eduard I've managed for optimization, and now runs in 0.771. Showing that scanf is slow.
um...scanf is slow? so any replacements?
im still a noobie so dont know about the algos talked about here
method i used was that when every number was enetered, it would count the number of numbers bigger than it before it and print the sum
takes 10.2 secs mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
You can use functions fread() and read() to grab large blocks of input into your own buffers, then parse manually it. This way you'll avoid the overhead of calling scanf() millions times.
It will approximately save you 0.500-0.600 sec. on this problem.
dpitts
New poster
Posts: 31
Joined: Tue Jun 17, 2003 10:10 pm

### 10810 UltraQuick Sort (Speed)

I have a working solution in ~1.3 seconds, but someone has it in .174? Did they know judges output, or can someone help me with a faster algorithm?

My current algorithm builds a tree based on the bits in the numbers. Each node in the tree has a left (zero) and right (one) child, and a count of how many numbers are to the right (one) side.
Each row in the tree represents that bit (starting with the MSB).

If you traverse left (there was a zero), then anything that had a one there was greater than the current number, and thus needed that many swaps. If you traverse right (there was a one), then you need to add one to the count.

This results in a complexity of O(N) I believe. however, each iteration has high constant time. Is there a faster O(N) algorithm? Or even an O(nlogn) that beats out for N <= 500000?

Yes, I know I should be proud enough of an AC answer, but I would like to know how to get a fast answer too mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
dpitts wrote:I have a working solution in ~1.3 seconds, but someone has it in .174?
That's me.
I don't know any O(n) solution. My program is based on merge-sort, which is Theta(n log n). With some optimizations, it runs .434 seconds.
My .172 sec. submission has a hardcoded answer to the toughest test case (I don't know the judge's data, I just spent some submissions to figure out that number.)
Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

### Re: AC

gvcormac wrote: There's a straightforward solution using quicksort. Just count the
number of inversions you have to do when you arrange the elements
I has already gotten AC with merge sort but now i'm trying to solve this problem using quicksort. However, i'm a little bit confused with cormack's hint . How can I count the number of inversions? I tried it with this idea but I get incorrect answers when the numbers are already sorted.

Code: Select all

``````
#include <stdio.h>

int a;
long long cont;

int particion(int a[],int p, int r)
{
int j,t,i=p-1,x=a[r];

for(j=p; j<=r-1;++j)
{
if( a[j]<=x )
{
++i;
t=a[i];
a[i]=a[j];
a[j]=t;
++cont;
}
}

t=a[i+1];
a[i+1]=a[r];
a[r]=t;
++cont;

return i+1;
}

void quick(int a[],int p, int r)
{
int q;

if(p<r)
{
q=particion(a,p,r);
quick(a,p,q-1);
quick(a,q+1,r);
}
}

int main()
{
int i,n;

while(1)
{
scanf("%i",&n);

if(n==0)
return 0;

for(i=1; i<=n; ++i)
scanf("%i",&a[i]);

cont=0;
quick(a,1,n);
printf("%lli\n",cont);
}
}
``````
Thx in advance Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Plz help me!! misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
Antonio Ocampo wrote:Plz help me!! When swapping two non-adjacent numbers the number of inversions doesn't have to decrease by 1.

E.g., in the array 8 1 2 3 0 if you swap 8 and 0, the number of inversions decreases by 4.

BTW, I find it easier to make mergesort count the number of inversions.
kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

### 10810 - Ultra-QuickSort , TLE

Hi,
I tried to use binary tree and count the number of swaps needed but getting TLE......
below is my code...anyone pls help me !!

Code: Select all

``````#include <iostream>
using namespace std;

struct node
{
int val;
struct node *left;
struct node *right;
};

long long cnt;
struct node *root;

void right_subtree ( struct node *p )
{
struct node *q;
q = p -> right;
if ( q == NULL ) return;
else
{
cnt ++;
if ( q -> left != NULL )
right_subtree( q -> left );
if ( q -> right != NULL )
right_subtree( q -> right );
}
return;
}

struct node *addtree ( struct node *p , int x )
{
struct node* q;
if ( p == NULL )
{
p = new node();
p -> val = x;
p -> left = p -> right = NULL;
}

else if ( x < p -> val )
{
cnt ++;
right_subtree(p);
p -> left = addtree ( p -> left , x );
}
else
p -> right = addtree ( p -> right , x );

return p;
}

int main ()
{
int n;
while ( scanf ( "%d" , &n ) == 1 && n )
{
root = NULL;
cnt = 0;
for ( int i = 0 ; i < n ; i ++ )
{
int x;
scanf ( "%d" , &x );
root = addtree ( root , x );
}
printf ( "%lld\n" , cnt );
//if ( cnt%2 ) printf ( "Marcelo\n" );
//else printf ( "Carlos\n" );
}
return 0;
}
``````
thanks again !!
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 10810 - Ultra-QuickSort

I was trying to solve this problem using fread (just to test how it works)... but getting WA, I got AC in 0.188 using scanf and when I'm using fread, how much memory should I read at once... I tried 20MB but it fails this is the parsing routine I am using:

Code: Select all

``````int main()
{
int i, n, f = 1;
p = strtok(buffer," \n");
while(p)
{
if(f)
{
n = atoi(p);
i = f = res = 0;
}
else if(i<n)
{
a[i++] = atoi(p);
}
if(i==n)
{
solve(0,n-1);
printf("%lld\n",res);
f = 1;
}
p = strtok(0," \n");
}
return 0;
}
``````
You should not always say what you know, but you should always know what you say.
mehrab
New poster
Posts: 10
Joined: Sat Jul 03, 2010 3:04 pm

### Re: 10810 - Ultra-QuickSort

Can anyone help me ... i'm getting runtime error for this problem...
can anyone tell me what mistake i have done?

Code: Select all

``````#include <stdio.h>

long long int number;

long long int bubble_sort(long long int *a,long long int cas)

{
long long int i,j,temp;
int flag=1;
long long int count=0;

for(i=0;( (i<cas-1) && flag) ;i++)
{
flag=0;
for(j=0;j<cas-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
flag=1;
count++;
}
}
}

return (count);
}

int main()
{
long long int count1,cas,i;

while(scanf("%lld",&cas)==1)
{
if(cas==0)
break;

for(i=0;i<cas;i++)
{
scanf("%lld",&number[i]);
}

count1=bubble_sort(&number,cas);
printf("%lld\n",count1);
}
return 0;
}

``````