Cod sursa(job #416278)

Utilizator feelshiftFeelshift feelshift Data 12 martie 2010 14:00:55
Problema Ordine Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <cstdio>
//#include <cstring>
int l = -1,i,k,ok;
char string[1000001],tmp;

FILE * in = fopen("ordine.in","rt");
FILE * out = fopen("ordine.out","wt");

void quicksort(char array[],int left,int right);

int main()
{
	while(!feof(in))
		fscanf(in,"%c",&string[++l]);
	//fscanf(in,"%s",string);
	//fprintf(out,"Sirul initial este:\n");
	//fprintf(out,"%s\n\n",string);
	fclose(in);
	//l = strlen(string);
	
	quicksort(string,0,l-1);
	
	while(ok != true)
	{
		ok = true;
		
		//fprintf(out,"Prima sortare:\n\n");
		for(i=1;i<l;i++)
			if(string[i] == string[i-1])
				for(k=i+1;k<l;k++)
					if(string[i] != string[k])
					{
						tmp = string[i];
						string[i] = string[k];
						string[k] = tmp;
						ok = false;
						//fprintf(out,"Am schimbat elementul %c cu elementul %c:\n",string[i],string[k]);
						//fprintf(out,"%s\n\n",string);
						break;
					}
	
		//fprintf(out,"A doua sortare:\n\n");
		for(i=l-2;i>1;i--)
			if(string[i] == string[i+1])
				for(k=i-1;k>=1;k--)
					if(string[i] != string[k])
					{
						tmp = string[i];
						string[i] = string[k];
						string[k] = tmp;
						ok = false;
						//fprintf(out,"Am schimbat elementul %c cu elementul %c:\n",string[i],string[k]);
						//fprintf(out,"%s\n\n",string);
						break;
					}
	}
	
	//fprintf(out,"Sirul final este:\n");
	fprintf(out,"%s",string);
	fclose(out);
	
	return (0);
}

void quicksort(char array[],int left,int right)
{
	int i,k,v;
	char tmp;
	
	if(left < right)
	{
		i = left - 1;
		k = right;
		v = array[right];
		
		for(;;)
		{
			while(array[++i] < v);
			while(array[--k] > v);
			
			if(i >= k)
				break;
			
			tmp = array[i];
			array[i] = array[k];
			array[k] = tmp;
		}
		
		tmp = array[i];
		array[i] = array[right];
		array[right] = tmp;
		
		quicksort(array,left,i-1);
		quicksort(array,i+1,right);
	}
}