Win a copy of Escape Velocity: Better Metrics for Agile Teams this week in the Agile and Other Processes forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Sorting Approach

 
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good Evening Friends,

I am working on some sorting tasks with lists and I was able to implement a solution but my solution takes too long.
Execution timed out after 5000ms....

Here are the details of the task:

- List with n+1 Elements


- Output should be like this


My approach was simply to create a new list, start from the tail and the head of the old list add each element in the new list and go next to tail+1 and head-1 until all elements are transferred.
As mentioned before, the program works but the approach takes to long.

Does anybody have a better idea to speed up the process?
 
Master Rancher
Posts: 4891
38
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What kind of lists are involved?  Does the code keep a reference to the end/add point on the output list?
 
Saloon Keeper
Posts: 14325
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sounds more like a bug in your code than a problem with your approach. Show us your code.
 
Marshal
Posts: 76483
366
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Don't call that sorting beause you are not using any features of the values to order your new list. Call it reordering because you are using some feature of the original list to reate the ordering of the new list. If you are usingoperators and saying, “tail,” or, “head,” that would suggest to me that you are using linked lists. Did you really mean, “tail + 1,” or, “head − 1”? Surely it should read, “tail − 1,” or, “head + 1”? I presume you have a doubly‑linked list so you can call previous() on a node. I presume you are not using a get() method, which is notoriously slow on linked lists.
As Norm and Stephan imply, that general approach sounds correct.

If you have a singly‑linked list, create a linked list to use as a stack, add alternate nodes to the stack or to an ordinary list, then iterate the stack and intermediate list and interleave the nodes into your final list. Remember that a stack returns its contents in reverse insertion order.
 
Bartender
Posts: 5074
189
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Don't call that sorting beause you are not using any features of the values to order your new list


Hmm, you can certainly do sorting here. If the list has no duplicates, and you don't mind an O(n^n) solution, this is fun:

 
Campbell Ritchie
Marshal
Posts: 76483
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Piet Souris wrote:. . . you can certainly do sorting here. . . .

Yes, of course you can sort the list, but that doesn't seem to be what the OP requires. It says here that sorting a linked list in situ tends to run inlogn complexity. If you are using the method in that link, wouldn't the sort run in nlogn complexity?
 
Piet Souris
Bartender
Posts: 5074
189
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My reply was not meant to be taken seriously.

Besides, it is incorrect, too. It works for the List(1, 2, ..., 31), but fails for the List(1, 2, ..., 32). Not sure how come. Probably that the comparator is based on a changing list.
 
Michael Grünau
Ranch Hand
Posts: 66
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks everyone for the help!


#Problem solved
 
Campbell Ritchie
Marshal
Posts: 76483
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well done  Please tell us what the solution was.
 
Could you hold this kitten for a sec? I need to adjust this tiny ad:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic