std::sort() has complexity O(n*log(n)) and O(1) in space. Your data can be sorted faster, at O(n), I think. The first (and simple) way to do this requires another array. The second, a bit more involved, doesn't require another array - the idea is that what you have is a permutation and any permutation is a product of some cycles. Invert each cycle and you are done.
2012/3/6 Βαγγέλης Μαμαλάκης <[email protected]>: > Thanks very much for your answers. After reading them I think I will use the > normal 4byte ints. > > Another really fast question I have is: > I define a struct with some data and an int n. I then initialise an array > with my struct. the n var is set to the position of each element. so > mystruct[0].n is 0, mystruct[0].n is 1 etc. In the end I have to sort the > elements of the array back to their original positions. I use > std::sort(mystruct, mystruct+k-1, sort_n); which does the job. Would it be > more efficient to use my own custom sorting sinse I know that there are n s > from 0 to some known number? > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
