Demo entry 6619734

sort

   

Submitted by anonymous on Jun 06, 2017 at 10:02
Language: C. Code size: 2.0 kB.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int n, a[1000000];

int sort(int *a, int n)
{
	// recursion finish
	if (n<=1) return 0;

	// If a is already sorted, then finish the function.
	int i;
	for (i=1; i<n; i++)
	{
		if (a[i-1]>a[i]) break;
	}
	if (i==n) return 0;
	
	// r is the KEY number's index. In this program KEY is selected randomly.
	// When KEY is selected, it will be swapped with a[0].
	// a^=b^=a^=b is a handy sentence to swap two integers a and b when a!=b.
	int r=rand()%n, j=n-1, k=a[r], mode=0; i=0;
	if (r!=0) a[r]^=a[0]^=a[r]^=a[0];


	// This part will firstly find a largest j which makes a[j]<k. 
	// Then swap a[i] and a[j].
	// Next find a largest i which makes a[i]>k, 
	// Then swap a[i] and a[j] again.
	// Do these until i==j.

	// So use a bool mode, 
	// When mode is 1 this function will judge a[i]<k and run i++.
	// When mode is 0 this function will judge a[j]>k and run j--.
	// Once a swap is run, mode will be switched.
	while (i<j)
	{
		if (mode?(a[i]>k):(a[j]<k))
			a[i]^=a[j]^=a[i]^=a[j], mode=!mode;
		else mode?(i++):(j--);
	}

	// sort the left and the right part
	// Here using || is okay because both of sort(a, i) and sort(a+i+1, n-i-1)
	// should be 0 if the function runs normally.
	return sort(a, i) || sort(a+i+1, n-i-1);
}

int main()
{
	// open and read the input file
	FILE *fp=fopen("sort.in", "r");
	fscanf(fp, "%d", &n);
	int i;
	for (i=0; i<n; i++)
		fscanf(fp, "%d", &a[i]);
	fclose(fp);

	// initialize the random numbers
	srand(time(0));

	// sort the numbers
	if (sort(a, n))
	{
		printf("return error\n");
		return 1;
	}

	// output the result
	fp=fopen("sort.out", "w");
	fprintf(fp, "%d", n);
	for (i=0; i<n; i++)
	{
		if (n<24) printf("%d\n", a[i]);
		if (i%8==0) fprintf(fp, "\n");
		fprintf(fp, "%d\t", a[i]);
	}

	// output the total number and the time
	printf("n = %d, time = %.3fs\n", n, 1.0*clock()/CLOCKS_PER_SEC);
	//system("PAUSE");
	return 0;
}

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).