Complex Sort Algorithm

[H1tchh1ker]

Here is the situation, you have an object that can reference a number of 'input' memory locations and a number of 'output' memory locations, the object will take the input/s and then do some processes and fill the output/s, input and output memory location can be used by any number of objects.

Each object will have a enum-type usage for each memory location. Each memory location can be used in any number of objects. Objects may use the same memory locations but with different usages.

If one object takes a particular memory location as an input and with a particular usage and another object takes the same memory location with the same usage but as an output. The latter described object should come first and then the other one (The data needs to be written to the memory location before the data is read).

Take those two objects again but say there is one more object that again takes the same memory location, but with a different usage, this object can be before or after both of them, but not between (Once the data in the memory location has been accessed by all the objects that need it the memory location maybe used in another way to store something different).

There is no original unsorted list, as objects are added and deleted unpredictably, starting with a blank list. The list needs to be sorted every 'frame' as a number of adds and deletes many have occurred in that frame.

After they are sorted each frame the objects are processed/run in the sorted order.

I need to write a sort algorithm (In C++) of some kind that will do this quickly as in each 'frame' needs to be done in far less than a tenth of a millisecond and on average each frame will contain maybe 20 adds and deletes, and while loading several 100's (but performance is not a problem while doing initial loading/adding).

A normal number of objects would be 3000.

Finally the large number of impossible sets of objects to sort will never occur.

What I'm looking for is a little help, or pointer in the right direction...

Thanks in advance.

Also, if my explanation is terrible please ask me to clarify and sorry its so long.

[keskiverto]

Sounds like a graph, but I'm no expert.

On beginning of a 'frame', are there "sources"? At the end of a 'frame', are there "sinks"? In other words, is there valid data in any memory location before any object has run and must the last objects leave meaningful data to some memory locations?

[H1tchh1ker]

The last object doesn't have to leave meaningful data and there may or may not be valid data contain in the memory locations at the start of a frame.

[H1tchh1ker]

If you want to know what it is, its part of an interface to directx and this algorithm would allow the software to run anything possible with directx (but at a high level) without the code needing to understanding of techniques... e.g. deferred rendering is a good example the engine has no code particularly for deferred rendering, but will be capable of it after writing this algorithm.

[pome90]

HI!! I have to do a implementation of an algorithm for my thesis but i have never studied informatic and this is my first time that i use this type of language. So i am here for to ask help because i wrote the code but when i want to print, the screen is blank! This is the code:

#include <algorithm>
#include <stdio.h>
#include <limits.h>
 
// Number of vertices in the graph
#define V 5
#define T 10


 int src= 0;    
     
 int etichetta( int dist[],bool spt[])
 {
     
   for ( int i=0 ; i <= V; i++) //inizializzazione di dist
  {
     spt[i]= false;  
     dist[i]= INT_MAX;
     dist[src]=0;
     }
     int S=0,G = V;
     int min = dist[src];
     int min_index;
     while ( S <= V)
     {
     for ( int i =0; i <= V; i++)
     {
         if ( dist[i] <= min && spt[i]== false)
              {
                   min_index =dist[i];
                   S += i;
                   G -= i ;
                   spt[i]= true;
                   }
     }
     }
        return min_index;
  }                                  



int printSolution(int dist[], int n)
{
   printf("Vertex   Distance from Source\n");
   for (int i = 0; i < V; i++)
      printf("%d \t\t %d\n", i, dist[i]);
}

void dijkstra( int C[T],int adj[V][V])

{
     int dist[V];   
     int t[V];
     for(int i=0; i<V; i++)
     {
             t[i]=0;
             }
   
     
     int pred[V];
   
    
     for(int i=0; i< V; i++)
    {
            pred[i]=0;
    
            }
        
    
     
     bool spt[V];
     int p;
     int c = etichetta(dist,spt);
     int a= pred[c];       
     t[c]=t[src]+t[a]+ adj[a][c];
                  if(t[c]<=T)
                  {
                             p=t[c];
                             }
     for(int i=0; i<=V; i++)
     {
              if( adj[c][i]!= 0 && dist[i]> dist[c] + C[p])
              {
                  
                  spt[i]= true;
                  pred[i]=c;
                  dist[i] = dist[c] + C[p];
                  }   
     }
                  
 printSolution(dist,V);

}    
     
     
        
     
 
 
// driver program to test above function
int main()
{
   /* Let us create the example graph discussed above */
   int adj[V][V] = {{0, 4, 3, 1, 0},
                     {0, 0, 2, 0, 0},
                     {0, 0, 0, 0, 3},
                     {0, 0, 4, 0, 2},
                     {0, 1, 0, 0, 0},
                      };
                      
   int C[T]= {1,2,3,4,1,2,8,1,1,1};     
                             
            
   
   dijkstra(C,adj);        
   fflush(stdin);getchar();
    
 
    return 0;
}

this is mine algorithm that it's very similar to dijkstra algorithm so please helpe me !! thank u so much and sorry for my english!