我实现了合并排序并将其用作此 codechef 问题的解决方案。这是提交的内容。代码放在下面。
我认为导致执行缓慢的问题是我的 IO 在main
函数中很慢。我知道输入的元素数量,因此必须有一些更快的方式来读取输入,而不是我正在做的方式。
是否有更快的 IO 方法而不是我在main
函数中使用的方法?我听说过使用缓冲区,fgets
但sscanf
我不知道它们是否更快。
任何代码示例都会有所帮助。
#include<stdio.h>
#include<stdlib.h>
void merge_parts(int arr[], int length)
{
int *ans;
int i, j, k;
int temp = length/2;
ans = malloc(sizeof(int) * length);
//This while and next if-else puts the merged array into temporary array ans
for (j = temp, i = k = 0; (i < temp && j < length); k++){
ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
}
if(i >= temp){
while(j < length){
ans[k++] = arr[j++];
}
}
else{
while(i < temp){
ans[k++] = arr[i++];
}
}
//This while loops puts array ans into original array arr
for(i = 0; i < length; i++){
arr[i] = ans[i];
}
free(ans);
}
void merge_sort(int arr[], int length)
{
if(length > 1)
{
merge_sort(&arr[0], (length/2));
merge_sort(&arr[length/2], (length - length/2));
merge_parts(arr, length);
}
}
int main()
{
int length;
int *arr;
scanf("%d", &length);
arr = malloc(sizeof(int) * length);
for(int i = 0; i < length; i++)
scanf("%d", &arr[i]);
merge_sort(arr, length);
for(int i = 0; i < length; i++)
printf("%d ", arr[i]);
free(arr);
return 0;
}
编辑3:
[我删除了 EDIT 和 EDIT2 因为它们不再相关]
我正在使用的 merge_sort 算法
void merge_parts(int arr[], int length)
{
int ans[length];
int i, j, k;
int temp = length/2;
//This while and next if-else puts the merged array into temporary array ans
for (j = temp, i = k = 0; (i < temp && j < length); k++){
ans[k] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
}
if(i >= temp){
while(j < length){
ans[k++] = arr[j++];
}
}
else{
while(i < temp){
ans[k++] = arr[i++];
}
}
//This while loops puts array ans into original array arr
for(i = 0; i < length; i++){
arr[i] = ans[i];
}
}
void merge_sort(int arr[], int length)
{
if(length > 1)
{
merge_sort(&arr[0], (length/2));
merge_sort(&arr[length/2], (length - length/2));
merge_parts(arr, length);
}
}
合并1.c
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#define SORTING_ALGO_CALL merge_sort
char buffer[4096];
int bufcount;
int bufpos;
int get_next_char()
{
if (!bufcount)
{
bufcount = fread(buffer, 1, 4096, stdin);
bufpos = 0;
if (!bufcount){
return EOF;
}
}
bufcount--;
return buffer[bufpos++];
}
int readnum()
{
int res = 0;
char ch;
do
{
ch = get_next_char();
} while (!isdigit(ch) && ch != EOF);
if (ch == EOF){
return 0xbaadbeef; // Don't expect this to happen.
}
do
{
res = (res * 10) + ch - '0';
ch = get_next_char();
} while(isdigit(ch));
return res;
}
int main()
{
clock_t time1, time2;
double time_taken;
//FIRST READ
time1 = clock();
int length = readnum();
while (length < 1)
{
printf("\nYou entered length = %d\n", length);
printf("\nEnter a positive length: ");
length = readnum();
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nReading length = %f\n", time_taken);
time1 = clock();
int *arr;
if ((arr = malloc(sizeof(int) * length)) == NULL)
{
perror("The following error occurred");
exit(-1);
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nAllocating array = %f\n", time_taken);
time1 = clock();
for (int i = 0; i < length; i++){
arr[i] = readnum();
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nReading array = %f\n", time_taken);
time1 = clock();
SORTING_ALGO_CALL(arr, length);
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nSorting array = %f\n", time_taken);
time1 = clock();
/*
for (int i = 0; i < length; i++){
printf("%d ", arr[i]);
}
*/
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nPrinting Sorted array = %f\n", time_taken);
time1 = clock();
free(arr);
//SECOND READ, PRINT
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nFreeing array = %f\n", time_taken);
return 0;
}
合并2.c
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define SORTING_ALGO_CALL merge_sort
int main()
{
clock_t time1, time2;
double time_taken;
//FIRST READ
time1 = clock();
int length;
scanf("%d", &length);
while (length < 1)
{
printf("\nYou entered length = %d\n", length);
printf("\nEnter a positive length: ");
scanf("%d", &length);
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nReading length = %f\n", time_taken);
time1 = clock();
int *arr;
if ((arr = malloc(sizeof(int) * length)) == NULL)
{
perror("The following error occurred");
exit(-1);
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nAllocating array = %f\n", time_taken);
time1 = clock();
for (int i = 0; i < length; i++){
scanf("%d", &arr[i]);
}
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nReading array = %f\n", time_taken);
time1 = clock();
SORTING_ALGO_CALL(arr, length);
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nSorting array = %f\n", time_taken);
time1 = clock();
/*
for (int i = 0; i < length; i++){
printf("%d ", arr[i]);
}
*/
//SECOND READ, PRINT AND NEXT FIRST READ
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nPrinting Sorted array = %f\n", time_taken);
time1 = clock();
free(arr);
//SECOND READ, PRINT
time2 = clock();
time_taken = (double)(time2 - time1) / CLOCKS_PER_SEC;
printf("\nFreeing array = %f\n", time_taken);
return 0;
}
merge1.c 和 merge2.c 都包含合并排序的 2 个函数。
我用于为 2 个文件生成最坏情况(递减顺序)输入的文件。
#include<stdio.h>
int main()
{
int j = 100000;
printf("%d\n", j);
for(int i = j; i > 0; i--)
printf("%d\n", i);
return 0;
}
merge1.c 的计时结果
Reading length = 23.055000
Allocating array = 0.000000
Reading array = 0.010000
Sorting array = 0.020000
Printing Sorted array = 0.000000
Freeing array = 0.000000
merge2.c 的计时结果
Reading length = 22.763000
Allocating array = 0.000000
Reading array = 0.020000
Sorting array = 0.020000
Printing Sorted array = 0.000000
Freeing array = 0.000000