Язык С. Нужно уменьшить время работы программы

[fufayka]

Здравствуйте! Помогите, пожалуйста. Нужно уменьшить время выполнения программы, как это можно сделать? заранее спасибо!

#include<stdio.h>

int main()
{
    int n, i, j, t1, t2, t3, lasttime;
    int a[10001] = {0}, b[10001] = {0}, k[100001] = {0}, l[100001] = {0};

    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        k[i] = i;
    }
    for(i = 1; i <= n; i++)
        scanf("%d", &b[i]);

    for(i = 1 ; i <= n - 1; i++) {
       for(j = 1; j <= n - i; j++) {
           if(b[j] > b[j+1]) {
                t1 = a[j];
                t2 = b[j];
                t3 = k[j];
                a[j] = a[j+1];
                b[j] = b[j+1];
                k[j] = k[j+1];
                a[j+1] = t1;
                b[j+1] = t2;
                k[j+1] = t3;
           }
       }
    }

    j = 1;
    l[1] = k[1];
    lasttime = b[1];
    for(i = 2; i <= n; i++){
        if(a[i] >= lasttime) {
           j++;
           l[j] = k[i];
           lasttime = b[i];
         }
    }
    printf("%d\n", j);
    for(i = 1; i <= j; i++){
       printf("%d ", l[i]);
    }
    return 0;
}

[GreenWizard]

    for(i = 1 ; i <= n - 1; i++) {
       for(j = 1; j <= n - i; j++) {
           if(b[j] > b[j+1]) {
                t1 = a[j];
                t2 = b[j];
                t3 = k[j];
                a[j] = a[j+1];
                b[j] = b[j+1];
                k[j] = k[j+1];
                a[j+1] = t1;
                b[j+1] = t2;
                k[j+1] = t3;
           }
       }
    }

замени это на др. алгоритм сортировки... судя по беглому просмотру кода, только это тут может тормозить ощутимо

[digitalis]

Алгоритм достаточно эффективный, несмотря что простой. Улучшить его можно - глянь в Вики "Сортировка пузырьком" . Там если во внутреннем цикле не было ни одной перестановки - финиш, дальше внешний цикл можно не крутить, уже все ОК.
Его можно еще улучшить :

 kc = n-1 ; 
 for(i = 1 ; i <= n - 1; i++)
 {   
       for(j = 1; j <= kc; j++)
      {
           if(b[j] > b[j+1])
             {
                t1 = a[j];
                t2 = b[j];
                t3 = k[j];
                a[j] = a[j+1];
                b[j] = b[j+1];
                k[j] = k[j+1];
                a[j+1] = t1;
                b[j+1] = t2;
                k[j+1] = t3;
                np = 1 ;
             } ;
         else np++ ;
     }
   kc = kc - np ;
 }

смысл: если во внутреннем цикле и были перестановки, но на последних np шагах их не было, то число повторений следующнго внутреннего цикла уже можно уменьшить на np ;

[digitalis]

Маленькое дополнение :

 for(i = 1 ; i <= n - 1; i++)
 {    np := 0 ;
       for(j = 1; j <= kc; j++)