switching the order of a list.

[moriarty]

First I apologize, I have no code to display as I'm just looking for input on the best way to get started.

What I need to do is change the order of a list from descending to ascending and am looking for the best way to do it that does not include a sort.

I admittedly state that I have a long way to go before being comfortable with c++ so please forgive me. :)

I had thought, however, that I had seen list[last] and/or list[first] before somewhere and thought that a loop using these would be good. If I weren't imagining them, or they weren't some other language, or even pseudocode.

Thanks much.

M.

[moriarty]

Then again, I'm assuming this is what I'm looking for (search function ftw)

// reversing vector
#include <iostream>
#include <list>
using namespace std;

int main ()
{
  list<int> mylist;
  list<int>::iterator it;

  for (int i=1; i<10; i++) mylist.push_back(i);

  mylist.reverse();

  cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
    cout << " " << *it;

  cout << endl;

  return 0;
}

[moriarty]

Or is that last code purely a visual affect? Meaning it doesn't permanently change the order.

[Albatross]

Er... pardon, but by definition that does require a sort right there. The code you gave just puts the numbers 1 through 10 in a list and then flips the list around. std::list::revers is not gonna work for you, I'm afraid, unless your numbers are already sorted according to size in the other direction.

You wrote:

What I need to do is change the order of a list from descending to ascending...

Wiktionary contributors wrote:

Sort: Verb: 2: To arrange into some order, especially numerically, alphabetically or chronologically.

:/

-Albatross

[moriarty]

Thanks for replying Albatross and perhaps, but the assignment is clear in saying "to write a function that rearranges the elements of an array from descending to ascending, the function must not incorporate any sorting algorithms, that is no item comparisons should take place."

[Albatross]

No item comparisons should take place. Hmm. Well, it says no sorting algorithms, but I'm going to ignore that and assume they meant comparison sorting algorithms, because they said "that is". There are sorting algorithms that use no comparisons, such as...

http://en.wikipedia.org/wiki/Counting_sort

Not the most efficient for large sets, but it's still awesome. Have fun!

-Albatross

[Duthomhas]

While I commend your use of the STL, the whole point of your assignment is to understand what is going on.

Given an array, say:

char message[] = "!dlrow olleH";

what your instructor wants you to do is change message to read "Hello world!". The length of your array is 12. (Well, technically it is 13, but you probably want to be able to print your array when done... and a c-string ends with a null-character, so just treat it as if it has a length of 12, which is what you would get if you use strlen() to get the string length.)

To reverse your array, there are a number of options available. I recommend you just use integer indices into your array and a loop. When you are done, just cout << message << endl; to see if you got it right.

Hope this helps.

[Albatross]

Duoas, you know he/she copied the code from the std::list::reverse reference, asking if this was potentially a solution, and that the problem was somewhat different from "reverse an array", right?

-Albatross

[Duthomhas]

Oops! It seems I wasn't paying attention at all. :-(

Sorry.

[moriarty]

It's all good, thanks for the tips.

Wat I've decided is that I needed to do something like....

for (i=0; i < length; i++)
temp=list[i]
Now the tricky part where I'm stuck. Getting it to the end of the index
and then:
list[last item] = temp
list[i]=list[last item]
list length-- //(to get to 2nd last item in list)


In other words, advancing from list[i], setting those values to a temporary value, I got. How to advance from the end of the list, to reset those values to list[i] then set the new beginning of the list equal to the temp is the problem. If you get what I mean. :)

[moriarty]

:) Proud of myself as this worked:

void listDir(int list[], int length)
{
 int i;
 int temp;
 int last = 9; 
 for (i = 0; i < last; i++)
 
  {
    temp = list[i];
    list[i] = list[last];
    list[last] = temp;
    
    last = last - 1;
    
}
}

Feels good figuring something out.