Describe how a self-reorganizing list could be implemented, such that frequently

Question

Describe how a self-reorganizing list could be implemented, such that frequently accessed items are moved to the front of a list in 0(1) time. Given a list of one million unsorted integers stored in an array, when is it more efficient to sort the data to increase the efficiency of searching. When is it better to simply do a search of the unsorted list? What is the name of each search algorithm? What is the name of the most efficient sorting algorithm? What is the order of magnitude to each algorithm. What is an integrator? Be specific. What is meant by the term serialization, as it pertains to Java; again, be specific.

Explanation / Answer

1) self-organizing list can be implemented using the move to the front as follows:
Consider a list of items. When an element is accessed in the list, delete that element from its position. Now insert that element at the beginning of the list. To do this, let the root/head pointer point to the deleted value and let this value point to the actual head of the list.

2)Given a large set of integers, which have to be searched, the following two factors can be considered.
In case of a binary search( an efficient search algorithm), it requires that the elements are to be sorted prior to the search. In case of large set of elements, sorting is best done using merge sort algorithm.
In case of linear search, the data can be searched simply without sorting them.

There are four searching algorithms, linear search, binary search, interpolation search and hash table.

The most efficient sorting algorithm is Quick sort. It is cache efficient.

The order of magnitudes of sorting algorithms are as follows:
algorithm best average worst
quicksort   O(nlogn) O(nlogn) O(n^2)
mergesort O(nlogn) O(nlogn) O(nlogn)
heapsort O(nlogn) O(nlogn) O(nlogn)
bubblesort O(n) O(n^2) O(n^2)
insertionsort O(n) O(n^2) O(n^2)
selectionsort O(n^2) O(n^2) O(n^2)

3)An iterator is an object that represents a stream of data. Unlike a sequence, an iterator can (usually) only provide the next item. The for-in statement uses iterators to control the loop, and iterators can also be used in many other contexts. Common form of iterator is pointer.

Java serialization is a mechanism where an object can be represented as a sequence of bytes that includes the object's data as well as information about the object's type and the types of data stored in the object.

After a serialized object has been written into a file, it can be read from the file and deserialized that is, the type information and bytes that represent the object and its data can be used to recreate the object in memory.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.