Cod sursa(job #114941)

Utilizator algoritmarOvidiu Andrei algoritmar Data 16 decembrie 2007 09:44:45
Problema Litere Scor 0
Compilator c Status done
Runda preONI 2008, Runda 2, Clasele 5-8 Marime 0.72 kb
#include <stdio.h>
#define FIN "litere.in"
#define FOUT "litere.out"
#define N_MAX 10000

char a[N_MAX];
int n,c;
void quick(int prim,int ultim,char a[N_MAX])
{
	int i,j;
	char pivot,x;
	i=prim;j=ultim;
	pivot = a[(prim + ultim) / 2];
	do{
		 while(a[i]<pivot) i++,++c;
		 while(a[j]>pivot) j--,++c;
		 if(i<=j) {
					++c;
					x=a[i];a[i]=a[j];a[j]=x;
					 i++;j--;
				};
	} while(i<=j);

	if(prim<j) quick(prim,j,a);
	if(i<ultim) quick(i,ultim,a);
} 


void quicksort(int n,char a[N_MAX])
{
   quick(0,n-1,a);
}

int main()
{
	FILE * fin,*fout;

	fin = fopen(FIN,"r");
	fout = fopen(FOUT,"w");
	fscanf(fin,"%d %s",&n,a);
	
	quicksort(n,a);
	
	fprintf(fout,"%d\n",c);
	
	return 0;
}