Self-sorted data structure with random access.

Question

I need to implement self-sorted data structure with random access. Any ideas?

Answer 1

Self sorting is a little bit to ambigious. First of all

What kind of data structure?

There are a lot of different data structures out there, such as:

• Linked list
• Double linked list
• Binary tree
• Hash set / map
• Stack
• Heap

And many more and each of them behave differently than others and have their benefits of course.

Now, not all of them could or should be self-sorting, such as the Stack, it would be weird if that one were self-sorting.

However, the Linked List and the Binary Tree could be self sorting, and for this you could sort it in different ways and on different times.

For Linked Lists

I would preffere Insertion sort for this, you can read various good articles about this on both wikis and other places. I like the pasted link though. Look at it and try to understand the concept.

If you want to sort after it is inserted, i.e. on random times, well then you can just implement a sorting algororithm different than insertion sort maybe, bubblesort or maybe quicksort, I would avoid bubblesort though, it's a lot slower! But easier to gasp the mind around.

Random Access

Random is always something thats being discusses around so have a read about how to perform good randomization and you will be on your way, if you have a linked list and have a "getAt"-method, you could just randomize an index between 0 and n and get the item at that index.

Answer 2

Maintaining a sorted list and accessing it arbitrarily requires at least O(lgN) / operation. So, look for AVL, red-black trees, treaps or any other similar data structure and enrich them to support random indexing. I suggest treaps since they are the easiest to understand/implement.

One way to enrich the treap tree is to keep in each node the count of nodes in the subtree rooted at that node. You'll have to update the count when you modify the tree (eg: insertion/deletion).

Answer 3

I'm not too much involved lately with data structures implementation. Probably this answer is not an answer at all... you should see "Introduction to algorithms" written by Thomas Cormen. That book has many "recipes" with explanations about the inner workings of many data structures. On the other hand you have to take into account how much time do you want to spend writing an algorithm, the size of the input and the if there is an actual necessity of an special kind of datastructure.

Answer 4

ya we can implement the self sorted data structure with random acces i did it i crested a algo for that it works .i think it will sort amd i devloped it right now the algo is already devloped myself and i will be come very soon this kind of data structure [email protected]

Answer 5

A self sorted data structure can be binary search trees. If you want a self sorted data structure and a self balanced one. AVL tree is the way to go. Retrieval time will be O(lgn) for random access.