Sort an array in pairs????

[dorito200]

Hey yall,

So for class, I got a new assignment and cannot figure it out for the life of me. The assignment is to write a function to sort an array of numbers but in pairs. The arrays are made up of scores, like this {4 10, 25 30, 99 100, 58 60}, and should be sorted by the second number. I have come up with a selection sort function but it barely works so I won't even bother posting it here. I am still pretty new to c++ so any tips or info would help! Thanks!

[zapshe]

Are you using std::pair<int, int> ?

If so, you can just use any sorting algorithm you want to use, but make sure to give it arr[i].second so it can sort with that number instead of the first number:

void sort(std::pair<int, int> a[])
{
	for (...)
	{
		for (...)
		{
			//compare a[i].second with a[j].second
		}
	}
}

int main()
{
	std::pair<int, int> a[5];

	//Fill the array with random numbers

	for (int i = 0; i < 5; i++)
	{
		a[i].first = randomInt;
		a[i].second = randomInt;
	}

        sort(a);
}

[jonnin]

you don't have to use pairs or containers, you can do it in a flat C array.
just index by 2, and swap 2 units. Since you know they are sequential, you can use memcpy or some other pointer hax to swap faster (eg here, its 32 bit ints, assuming int is 32 bit on your compiler, then you can cast out a pointer to 64 bit int and swap those in one go for example).
play with your sort, see if you can do for(i = 0; i < size; i+=2) type loop where it compares only the first of the pair and swaps 2 as one item. It should be only minor modification to the simple N*N sort algorithms. It would be a lot more tricky for the better algorithms.. I admit that this may be brain warping for shellsort.

you can do it the other way too, cast the array to 64 bit int pointer of 1/2 the current size, change the comparison to only look at the upper half... but some of this kind of foolishness only works on integers or simple types...

[JLBorges]

> assuming int is 32 bit on your compiler, then you can cast out a pointer to 64 bit int and swap those in one go

This would engender undefined behaviour:

If a program attempts to access the stored value of an object through a glvalue whose type is not similar to one of the following types the behavior is undefined:
. the dynamic type of the object,
. a type that is the signed or unsigned type corresponding to the dynamic type of the object, or
. a char, unsigned char, or std​::​byte type.
http://www.eel.is/c++draft/expr.prop#basic.lval-11

similar types: http://www.eel.is/c++draft/conv.qual#2

With C++20, we can write:

#include <iostream>
#include <utility>
#include <algorithm>
#include <ranges>
#include <format>

int main()
{
    std::pair<int,int> scores[] { {4,10}, {25,30}, {99,100}, {58,60} } ;
    std::ranges::sort( scores, std::less<>{}, &std::pair<int,int>::second ) ;
    for( auto [a, b] : scores ) std::cout << std::format( "{: 4}{: 6}\n", a, b ) ;
}

And let the optimiser do all the low level tricks it wants (like vpinsrd, vpunpcklqdq)

[jonnin]

you are saying that this:
int32_t arr[4] = {1,2,3,4};
uint64_t * ap = (uint64_t*)(arr);
std::swap(ap[0],ap[1]);
does not *safely* yield
{3,4,1,2} ??
Why? its known that arrays store the bytes back to back. Its known that the cast is going to reshape how the memory is accessed.
if the data were modified, it could go very wrong, esp if the data were signed. But no data modification is happening here, only movement of bytes, just grouped differently. Yes, I read the links, and appreciate them, but I am not good enough at reading the specs to see if that is in there because it could blow up if the data were modified, or if I am missing something the compiler could do wrong here..? Do some compilers pad arrays like struct?
//edit typos

the point wasn't to optimize or play computer. It was in case the OP was stuck with a flat array.

[JLBorges]

> Do some compilers pad arrays like struct?

No, there is no padding between the object representations of array elements.
But for types other than narrow char types, every bit in the object representation
may not participate in the value representation

For the objects of type char, signed char, and unsigned char (unless they are oversize bit fields), every bit of the object representation is required to participate in the value representation and each possible bit pattern represents a distinct value (no padding, trap bits, or multiple representations allowed).
https://en.cppreference.com/w/cpp/language/object#Object%20representation_and_value_representation

As far as integers in typical implementations are concerned, the above is just theory.
A commonly encountered problem in real life is one of alignment; the 64-bit integer may have stricter alignment requirements.

For example:

#include <iostream>
#include <cstdint>
#include <type_traits>

int main()
{
    struct A
    {
        std::int32_t i = 23 ;
        std::int32_t arr[31] {} ;
    };
    
    A a ;
    const bool aligned_correctly_for_64_bit_int = std::uintptr_t(a.arr) % std::alignment_of<std::uint64_t>::value == 0 ;
    std::cout << std::boolalpha << "safe to access as 64 bit int? " << aligned_correctly_for_64_bit_int  << '\n' ;
}

http://coliru.stacked-crooked.com/a/6d75a583a49e1f50

[jonnin]

ah, OK. I realised that part, that it was a hack & only usable on a few types. Thank you!