Hi, Try not reinventing the wheel - if something got into std, it's probably better than thing you'd write. Only thing is you can consider different method than std::sort, as this is not considered to be stable.
You can use stable_sort [1] in case you need to have comparable sorting times regardless of data content. Have a look in here as well [2], there is a quick overview of sorting algorithms. Best, D. [1] http://www.cplusplus.com/reference/algorithm/stable_sort/ [2] http://stackoverflow.com/questions/1753278/what-is-the-fastest-sorting-algorithm-in-c 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? > > 2012/3/6 Axel Freyn <[email protected]> > >> I agree it is possible in C++. However you have to accept that your code >> will run slow on almost all processors: most processors do not have >> hardware support for 3byte integers, so you have to implement ALL >> operations in software. You could write something like: >> class int3{ >> char d[3]; >> public: >> int3(int x){ >> assert(x<(1l<<24)); >> d[0]=x%256; >> d[1]=(x/265)%256; >> d[2]=(x/256/256)%256; >> } >> friend int3 operator +(int3, int3); >> }; >> int3 operator +(int3 x, int3 y){ >> int3 z; >> for(int i =0;i <3;i++) >> z.d[i]=x.d[i]+y.d[i]; >> return z; >> } >> However, I'm skipping some important parts: >> - how to treat overflow, if one of the three summations gives a result > >> 128 (C++ does not guarantee what will happen then, you have to check the >> values before adding them and the do the overflow- handling yourself.) >> - some test code ;) >> - for std::sort you can either define " bool operator<", or you define a >> functor class doing that comparison, and pass that functor to std::sort >> >> Axel >> Am 06.03.2012 06:56 schrieb "Neal Zane" <[email protected]>: >> >> I am thinking putting those guys in 256 buckets each holding 16 bit >>> shorts and some arrangements would make each bucket sortable using sort(). >>> On Mar 5, 2012 3:14 PM, "Βαγγέλης Μαμαλάκης" <[email protected]> wrote: >>> >>>> Well I a writing a program for a competition and I am initializing some >>>> arrays whose values will be less than 1million so I am trying to save >>>> memory. I am also curious. >>>> Would it be possible to give me some example code or psedocode. >>>> Thanks for your interest. >>>> On Mar 6, 2012 12:44 AM, "Damian Walczak" <[email protected]> >>>> wrote: >>>> >>>>> Hi >>>>> >>>>> On Mon, Mar 5, 2012 at 8:27 PM, Sidhartha Mani >>>>> <[email protected]>wrote: >>>>> >>>>>> You could >>>>>> use 3 char vars to hold your values, but i believe, the size of char >>>>>> differs on different architectures. >>>>>> >>>>> >>>>> AFAIR size of char is always 1 byte in C/C++ and it doesn't matter >>>>> what architecture you are using. >>>>> >>>>> the implementation of this though. I think std::sort() only works and >>>>>> is meant for abstract data structures like vectors and such, not on >>>>>> elementary ones like int. >>>>>> >>>>> >>>>> You can use std::sort for sorting arrays, example is even on wikipedia >>>>> [1] >>>>> If you write your own class, it's enough to write proper comparison >>>>> function and use second version of std::sort [2] >>>>> >>>>> >>>>> If I may ask - why do you need 3-byte 'int' ? >>>>> >>>>> Best, >>>>> D. >>>>> >>>>> [1] >>>>> http://en.wikipedia.org/wiki/Sort_(C%2B%2B)<http://en.wikipedia.org/wiki/Sort_%28C%2B%2B%29> >>>>> [2] http://www.cplusplus.com/reference/algorithm/sort/ >>>>> >>>>> >>>>> >>>>>> Sidhartha >>>>>> >>>>>> >>>>>> >>>>>> On 06-Mar-2012, at 12:42 AM, bugos <[email protected]> wrote: >>>>>> >>>>>> > Hello, >>>>>> > is there a way to define my own data type, which will be idetical to >>>>>> > an int, but just 3 bytes size? i must be able to use it as an int >>>>>> and >>>>>> > even use std::sort() with it. >>>>>> > >>>>>> > -- >>>>>> > 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. >>>>>> > >>>>>> >>>>>> -- >>>>>> 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. >>>>>> >>>>>> >>>>> -- >>>>> 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. >>>>> >>>> -- >>>> 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. >>>> >>> -- >>> 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. >>> >> -- >> 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. >> > > -- > 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. > -- 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.
