# 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.