Your algorithm receives a doubly linked list as an input parameter (in the form

Question

Your algorithm receives a doubly linked list as an input parameter (in the form of a
pointer to the head and a pointer to the tail nodes of the list; see DLList lecture 5, slide
28). Each node in the list contains the information: itemCode, name, and price, as
depicted below. The input list is sorted by itemCode.
Your algorithm has to return a doubly linked list with the same items as those in the
input. However, they should now be sorted by price.
For simplicity, please assume that no two items have the same price.

public class ShopNode {
public int itemCode;
public String name;
public double price;
public ShopNode next, prev;
public ShopNode(int i, String s, double d, ShopNode n, ShopNode p) {
itemCode = i; name = s; price = d; next = n; prev = p;
}
public ShopNode(int i, String s, double d) {
this(i, s, d, null, null);
}
}

Remember your submission has to include:
a) Your proposed algorithm
b) Your high-level explanation of how your algorithm works (i.e., do not explain what
each line of code is doing, but rather the main ideas included here)
c) Your algorithm’s time complexity, with a justification
d) Your algorithm’s space complexity, with a justification

Explanation / Answer

The proposed algorithm for sorting the doubly linked list in terms of price is selection sort.

The algorithm works as follows:

It starts with comparing the first node with all the remaining nodes(i.e second node onwards..). Every time if it finds a node with less value, it swaps the contents and continue comparing with next node onwards.Once the comparison is complete the first node contains the minimum value.

After first run the list has two parts one is sorted and another is unsorted.In our case after the first run, the list with the first element is sorted list and list starting from second node onwards is unsortred list.

So now we will repeat the same process for the unsorted list starting from second node onwards. So after the second run the sorted list will contain first and the second node whereas the unsorted list starts from the third node. The process continues till the unsorted list becomes empty.

In the first run there will be n-1 comparisons, in the second run n-2 comparisons and so on....
So the number of comparisons will be (n-1) + (n-2) + (n-3)......1 = ((n-1)n)/2 = (n^2-n)/2. Assuming the swapping of cotents take constant time.

The time complexity is O(n^2) as this n^2 is more influential term as n grows.

No additional space is required for this algorithm as we are swapping the contents of the node.The space(number of nodes) grows as n grows. The linked list with n node will have space = n*(space for one node). Similarly for n+1 nodes the space will be (n+1)*space for one node. So the space complexity is of O(n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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