Printing a strings linked list lexicographically, time O(n^2), space O(1), no swap

B

Billy

Hi,

It has to be some stupid high school home task , that can be solved in
rather straightforward manner.
The pain in the @ss is the requirement not to touch the original list,
that is: no swap between the elements is permitted.
O(n^2) is a bunch of time: the list can be even bubble sorted, but I
really fail to figure out how the hell I'm supposed to handle the
sorting without building any additional structures and the requirement
not to modify the original list in any way.

Any help/tip/advice will be appreciated,

Thanks.
 
R

Richard Harter

Hi,

It has to be some stupid high school home task , that can be solved in
rather straightforward manner.
The pain in the @ss is the requirement not to touch the original list,
that is: no swap between the elements is permitted.
O(n^2) is a bunch of time: the list can be even bubble sorted, but I
really fail to figure out how the hell I'm supposed to handle the
sorting without building any additional structures and the requirement
not to modify the original list in any way.

Any help/tip/advice will be appreciated,

Wrong news group. That said, make n passes through the list. In each
pass find the smallest one that is larger than the last one printed.
Try comp.programming next time.
 
D

David T. Ashley

Richard Harter said:
Wrong news group. That said, make n passes through the list. In each
pass find the smallest one that is larger than the last one printed.
Try comp.programming next time.

Also, Billy, although I'm sure you noticed ... making N complete passes
through a list with N elements might be O(N**2).
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top