Optymalizacja algorytmu

Witam,

Od ładnych paru godzin próbuję zoptymalizować poniższy algorytm:

 for (i=0;i<m-1;i++)
  {
     if (x[i+1]<x[a])
      {
       b=x[a];
       x[a]=x[i];
       x[i]=b;
      }
    }
 for (i=0;i<n-1;i++)
    {
     if (y[i+1]<y[a])
      {
       b=y[a];
       y[a]=y[i];
       y[i]=b;
      } 

Czy można w/w pętle zapisać w inny sposób lub dokonać ich optymalizacji do prostszego kodu?
Byłbym wdzięczy za pomoc, a już w ogóle byłbym zachwycony pomocą w postaci kodu. :)

Pozdrawiam!

Ale co to w ogóle jest? Na oko to wygląda jak dwie pętle przesuwające element ekstremalny na koniec tablicy. Chcesz to zoptymalizować -> przyspieszyć, czy uprościć zapis? Uprościć za bardzo sie go nie da, ot ew można tam użyć std::swap(). A przyspieszyć też tego nie przyspieszysz bo wybranie maxa z tablicy nieposortowanej ma O(n)

Jest to fragment rozwiązania zadania z olimpiady informatycznej.

Cała treść zadania wraz z przykładowym rozwiązaniem znajduje się pod tym linkiem - http://kondel.ko.funpic.de/?pid=38

Natomiast poniżej podaję dalszą część programu:

/******************************/
/*     Autor: Konrad Ortyl    */
/*  http://www.kondel.prv.pl  */
/******************************/

#include <iostream.h>
#include <stdio.h>

int m,n,i,a,b,a1,b1,suma=0,wynik=0; /*zmienne*/
int *x,*y; /*tablice*/

int main(void)
{
 cin >> m >> n; 	/*wczytanie m,n*/
 x= new int [m];	/*inicjalizacja tablicy x*/
 y= new int [n];	/*inicjalizacja tablicy y*/
 x[m-1]=0; y[n-1]=0;    /*ostatnim elementom wartosc na 0*/

 for (i=0;i<m-1;i++) scanf("%d", &x[i]); /*wczytanie x1,x2,...,xm-1*/
 for (i=0;i<n-1;i++) scanf("%d", &y[i]); /*wczytanie x1,x2,...,xn-1*/

 /*sortowanie tablic*/
 for (i=0;i<m-2;i++)
  {
   for (a=i+1;a<m-1;a++)
    {
     if (x[i]<x[a])
      {
       b=x[a];
       x[a]=x[i];
       x[i]=b;
      };
    };
  };
 for (i=0;i<n-2;i++)
  {
   for (a=i+1;a<n-1;a++)
    {
     if (y[i]<y[a])
      {
       b=y[a];
       y[a]=y[i];
       y[i]=b;
      };
    };
  };

 /*liczenie*/
 a=1; b=1; /*liczba kawalkow pionowych i poziomych*/
 a1=0; b1=0;
 for (i=0;i<m+n-2;i++)
 {
  if (x[a1]>=y[b1]) {suma=x[a1]*b;  a1++; a++; wynik+=suma; continue;};
  if (x[a1]< y[b1]) {suma=y[b1]*a;  b1++; b++; wynik+=suma; continue;};
 };
 
 cout << wynik;
 delete [] x;
 delete [] y;
 return 0;
};
 

To rozwiazanie to jakaś masakra. I pod względem algorytmicznym i pod względem programistycznym. Nie patrzyłem w ogóle na treść zadania, ale sam kod można zoptymalizować choćby tak:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

bool desc (int i,int j) { return (i>j); }

int main()
{
    int m,n,i,a,b,a1,b1,suma=0,wynik=0;
    int *x,*y;
    cin >> m >> n;
    x= new int [m];
    y= new int [n];
    x[m-1]=0;
    y[n-1]=0;
    for (i=0; i<m-1; i++)
        scanf("%d", &x[i]);
    for (i=0; i<n-1; i++)
        scanf("%d", &y[i]);
    sort(x,x+m-1,desc);
    sort(y,y+n-1,desc);
    a=1;
    b=1;
    a1=0;
    b1=0;
    for (i=0; i<m+n-2; i++)
    {
        if (x[a1]>=y[b1])
        {
            suma=x[a1]*b;
            a1++;
            a++;
            wynik+=suma;
            continue;
        }
        if (x[a1]< y[b1])
        {
            suma=y[b1]*a;
            b1++;
            b++;
            wynik+=suma;
            continue;
        }
    }
    cout << wynik;
    delete [] x;
    delete [] y;
    return 0;
}

Masz w ten sposób O(nlogn) a nie O(n^2). Ale znając życie to można to pewnie zrobić w jakimś O(n) jak się pomyśli ;]

Jeśli to coś pomoże, moja Czekolada:

#include <cstdio>
#include <cstdlib>

const int VERTICAL   = 0;
const int HORIZONTAL = 1;

const int NO_MORE    = -1;

int T[2][1024];

int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    n--;
    m--;

    long long int row_cost = 0;
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &T[VERTICAL][i]);
        row_cost += T[VERTICAL][i];
    }

    long long int column_cost = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &T[HORIZONTAL][i]);
        column_cost += T[HORIZONTAL][i];
    }

    qsort(T[VERTICAL], m, sizeof(int), compare);
    qsort(T[HORIZONTAL], n, sizeof(int), compare);

    m--; n--;
    long long int ret = 0;
    while(m >= 0 || n >= 0)
    {
        //printf("n %d m %d\n", n, m);
        if(m < 0) // zostala jedna kolumna
        {
            // utnij wszystkie wiersze
            ret += column_cost;
            m = n = NO_MORE;

        }
        else if(n < 0) // zostal jeden wiersz
        {
            // utnij wszystkie kolumny
            ret += row_cost;
            n = m = NO_MORE;
        }
        else
        {
            // sprawdz co korzystniej uciac
            if(T[VERTICAL][m] > T[HORIZONTAL][n])
            {
                ret += column_cost + T[VERTICAL][m];
                row_cost -= T[VERTICAL][m];
                m--;
            }
            else
            {
                ret += row_cost + T[HORIZONTAL][n];
                column_cost -= T[HORIZONTAL][n];
                n--;
            }
        }
    }
    printf("%lld", ret);
}