• 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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Bear Bibeault
  • Junilu Lacar
  • Martin Vashko
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Knute Snortum
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Scott Selikoff
  • salvin francis
  • Piet Souris

Sorting Approach

 
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • 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?
 
Rancher
Posts: 3623
34
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 10858
234
  • Mark post as helpful
  • send pies
  • 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: 66525
251
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 3668
151
  • Likes 1
  • Mark post as helpful
  • send pies
  • 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: 66525
251
  • Mark post as helpful
  • send pies
  • 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: 3668
151
  • Mark post as helpful
  • send pies
  • 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: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks everyone for the help!


#Problem solved
 
Campbell Ritchie
Marshal
Posts: 66525
251
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well done  Please tell us what the solution was.
 
Poop goes in a willow feeder. Wipe with this tiny ad:
Java file APIs (DOC, XLS, PDF, and many more)
https://products.aspose.com/total/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!