Physical sort vs logical ordering!

[geeloso]

OK, I have a list of objects, each having six data members (one string data type, the remainder double). The list is to be displayed according to the alphabetical order of the string data members; this is the default print format for the list. That I have easily achieved. However, I am required to also display the list by doing a "logical ordering" with respect to one of the double data members; and specifically mandated NOT to "physically sort" the list by that particular double data member.

What does a logical ordering mean in this context vis-a-vis a physical sorting? Any insights please?

[vlad from moscow]

I think that you need simply to output the list in the logical order without physically sorting it.

[geeloso]

Thx vlad for your prompt response. But you are still not answering my question! What is that 'logical order'? If you are not sorting the list, what is the parameter or metric that determines the order by which the list is to be printed?

[JLBorges]

> What does a logical ordering mean in this context vis-a-vis a physical sorting?

It means: perform an indirect sort, and print the results accordingly.
http://en.wikiversity.org/wiki/Sorting_data#Indirect_sort

For instance:

#include <string>
#include <iostream>
#include <functional>
#include <algorithm>
#include <list>
#include <vector>

struct A
{
    std::string str ;
    double number ;

    // ...
};

std::ostream& operator << ( std::ostream& stm, const A& a )
{ return stm << "{'" << a.str << "'," << a.number << '}' ; }

int main()
{
    // const, immutable,
    const std::list<A> seq_in_physical_order { { "abc", 23.67 }, { "def", 11.05 }, { "ghi", 17.32 },
                                               { "jkl", 56.78 }, { "mno", 33.12 }, { "pqr", 40.71 } } ;

    std::vector< std::reference_wrapper< const A > > seq_in_logical_order( seq_in_physical_order.begin(),
                                                                           seq_in_physical_order.end() ) ;
    // perform a logical ordering with respect to the member 'number'
    std::sort( seq_in_logical_order.begin(), seq_in_logical_order.end(),
               [] ( const A& first, const A& second ) { return first.number < second.number ; }  ) ;

    std::cout << "in physical order:\n-----------------\n" ;
    for( const A& a : seq_in_physical_order ) std::cout << a << " @ " << std::addressof(a) << '\n' ;

    std::cout << "\n\n\nin logical order:\n----------------\n" ;
    for( const A& a : seq_in_logical_order ) std::cout << a << " @ " << std::addressof(a) << '\n' ;
    std::cout << '\n' ;

}

http://ideone.com/ENfmE6

[Duthomhas]

I like how JLBorges always uses the STL to maximum efficiency, but I don't know if the OP has enough knowledge under his belt to understand the underlying assumptions and a-priori knowledge. Right now, OP is struggling to understand the concept of using references to sort another collection.

To explain better, suppose you have an array of items, like this:

int a[] = { 3, 1, 4, 2 };

You could actually "move" the elements around by swapping their values. But that would change a[].

(In JLBorges's example, he uses a std::list -- which is a linked list, so the elements themselves are never actually moved, but the pointers to the previous/next elements are changed -- so in essence, you are still modifying the source data directly.)


An indirect sort creates a list of references to the data, using either 'pointer types' or C++ 'reference types'.

int* p[] = { &a[0], &a[1], &a[2], &a[3] };

Now, you can sort p[] by following the pointers to a[]'s elements. Notice that a[] is not actually modified -- it is the pointers in p[] that are swapped.

// a quick selection sort
for (unsigned n = 0; n < 4; n++)
  {
  unsigned min = n;
  // find the next smallest element
  for (unsigned m = n+1; m < 4; m++)
    {
    // notice how we are comparing a[]'s elements, not p[]'s
    if (*p[m] < *p[min])
      max = m;
    }

  // but here we are swapping p[]'s elements
  int* temp = p[n];
  p[n] = p[min];
  p[min] = temp;
  }

This is an indirect sort. You can print out the sorted version of a[] using p[]:

// Print a[] -- notice that a[] has not changed
for (unsigned n = 0; n < 4; n++)
  cout << a[ n ] << " ";
cout << endl;

// Print the 'sorted a[]'
for (unsigned n = 0; n < 4; n++)
  cout << *p[ n ] << " ";
cout << endl;

JLBorges's example does exactly this, but it uses a lot of C++'s syntactic sugar to make things pretty and easy to write, which is why his code is so much shorter and nicer to read and use. Only it hides the whole pointer/reference thing behind a few layers.

Hope this helps.

[geeloso]

Thx JLBorges and Douas for your responses. I have not fully mastered the STL, so I follow and appreciate Douas' illustration better. Besides, I prefer designing my own codes and algorithms, even if more cumbersome, to using prefabricated templates from the STL. As it turns out, I had essentially done something very similar to Douas' approach; I just didn't know that a logical ordering tacitly meant an indirect sort.

I created a two-dimensional dynamic array (in a function) to store the double data members of the list's objects AND the indices of their relative positions in the list. In the function's selection sort algorithm, anytime I swapped a pair of the double data members, I performed a swap of the corresponding indices. This way, the original positions of the data always follow/track the data members. I copied the final sorted mirror-indices into an array accessible by an object in function 'main' and used this to print out the list sorted according to that double data member. I later called the print function for the original list and confirmed it wasn't changed by the function's logical ordering.

Douas wrote:

Right now, OP is struggling to understand the concept of using references to sort another collection.

Far from it! This original poster understands the concepts of references and pointers; the algorithm I illustrated above shows this. However, I concede that your method is aesthetically and functionally better. Thx again.

[Duthomhas]

It is good to know how things work... but don't discount the power of the STL algorithms. They will often out-perform hand-written loops!

Glad we could be of help!

[JLBorges]

> I prefer designing my own codes and algorithms, even if more cumbersome,
> to using prefabricated templates from the STL.

I personally tend to concur with this view (Koenig and Moo):

Our approach is possible only because C++, and our understanding of it, has had time to mature. That maturity has let us ignore many of the low-level ideas that were the mainstay of earlier C++ programs and programmers.
The ability to ignore details is characteristic of maturing technologies. For example, early automobiles broke down so often that every driver had to be an amateur mechanic. It would have been foolhardy to go for a drive without knowing how to get back home even if something went wrong. Today's drivers don't need detailed engineering knowledge in order to use a car for transportation. They may wish to learn the engineering details for other reasons, but that's another story entirely.

We define abstraction as selective ignorance--concentrating on the ideas that are relevant to the task at hand, and ignoring everything else--and we think that it is the most important idea in modern programming. The key to writing a successful program is knowing which parts of the problem to take into account, and which parts to ignore. Every programming langauge offers tools for creating useful abstractions, and every successful programmer knows how to use those tools.
...
If abstractions are well designed and well chosen, we believe that we can use them even if we don't understand all the details of how they work.

http://www.acceleratedcpp.com/details/preface.html

Yeah, one doesn't have to first learn to be a mechanic before one starts learning how to drive.


> I created a two-dimensional dynamic array to store the double data members of the list's objects
> AND the indices of their relative positions in the list. In the function's selection sort algorithm,
> anytime I swapped a pair of the double data members, I performed a swap of the corresponding indices.

One idea in an indirect sort is that the original sequence need not be changed; another is that one does not have to make copies of the original data and then move them around. We just need to sort an array of indices; once we have an index, the data (the double data member) in the original sequence is accessible via the index.

C++ offers several ways to refer to the objects in the original sequence - reference wrappers, pointers, iterators, and with a sequence that supports random access, indices.

#include <string>
#include <iostream>
#include <functional>
#include <algorithm>
#include <list>
#include <vector>

struct A
{
    int slno ;
    std::string name ;
    double value ;

    // ...
};

std::ostream& operator << ( std::ostream& stm, const A& a )
{ return stm << '{' << a.slno << ",'" << a.name << "'," << a.value << '}' ; }

int main()
{
    // const, immutable,
    const std::vector<A> seq { { 1, "mno", 23.67 }, { 2, "jkl", 11.05 }, { 3, "pqr", 17.32 },
                               { 4, "def", 56.78 }, { 5, "abc", 33.12 }, { 6, "ghi", 40.71 } } ;

    // indirect sort on name using reference wrappers
    std::vector< std::reference_wrapper< const A > > ind_r( std::begin(seq), std::end(seq) ) ;
    std::sort( std::begin(ind_r), std::end(ind_r),
               [] ( const A& first, const A& second ) { return first.name < second.name ; }  ) ;

    // indirect sort on value using pointers
    std::vector< const A* > ind_p ;
    for( const A& a : seq ) ind_p.push_back( std::addressof(a) ) ;
    std::sort( std::begin(ind_p), std::end(ind_p),
               [] ( const A* first, const A* second ) { return first->value < second->value ; }  ) ;

    // indirect sort on name (descending) using iterators
    using iterator = std::vector<A>::const_iterator ;
    std::vector<iterator> ind_i ;
    for( iterator iter = std::begin(seq) ; iter != std::end(seq) ; ++iter ) ind_i.push_back(iter) ;
    std::sort( std::begin(ind_i), std::end(ind_i),
               [] ( iterator first, iterator second ) { return first->name > second->name ; }  ) ;


    // indirect sort on value (descending) using positions in the sequence
    std::vector<std::size_t> ind_n( seq.size() ) ;
    std::iota( std::begin(ind_n), std::end(ind_n), 0 ) ;
    std::sort( std::begin(ind_n), std::end(ind_n),
               [&seq] ( std::size_t a, std::size_t b ) { return seq[a].value > seq[b].value ; }  ) ;

    std::cout << "in physical order:\n----------------\n" ;
    for( const A& a : seq ) std::cout << a << " @ " << std::addressof(a) << '\n' ;
    std::cout << '\n' ;

    std::cout << "\nin logical order (name):\n----------------\n" ;
    for( const A& a : ind_r ) std::cout << a << " @ " << std::addressof(a) << '\n' ;
    std::cout << '\n' ;

    std::cout << "\nin logical order (value):\n----------------\n" ;
    for( const A* p : ind_p ) std::cout << *p << " @ " << p << '\n' ;
    std::cout << '\n' ;

    std::cout << "\nin logical order (name, descending):\n----------------\n" ;
    for( iterator iter : ind_i ) std::cout << *iter << " @ " << std::addressof(*iter) << '\n' ;
    std::cout << '\n' ;

    std::cout << "\nin logical order (value, descending):\n----------------\n" ;
    for( std::size_t i : ind_n ) std::cout << seq[i] << " @ " << std::addressof(seq[i]) << '\n' ;
    std::cout << '\n' ;
}

http://ideone.com/0n7If6