Insertion sort, merge sort and quicksort on doubly-linked list Outline: you will implement insertion sort, mergesort and quicksort on a doubly- linked list. You must use the std::list data structure to hold the elements to be sorted (do not provide your own linked list implementation). In addition to the sorting algorithms, you should provide a main with timing experiments to compare the performance of your sorting algorithms on different inputs (lists in sorted order, in reverse-sorted order, with random elements, or all duplicate elements). You should make use of iterators in your code. For example, in the 'merge' function of mergesort you can use an iterator to the left sub-list and a second iterator the right sub-list, and advance the iterator of

Insertion sort, merge sort and quicksort on doubly-linked list Outline: you will implement insertion sort, mergesort and quicksort on a doubly- linked list. You must use the std::list data structure to hold the elements to be sorted (do not provide your own linked list implementation). In addition to the sorting algorithms, you should provide a main with timing experiments to compare the performance of your sorting algorithms on different inputs (lists in sorted order, in reverse-sorted order, with random elements, or all duplicate elements). You should make use of iterators in your code. For example, in the 'merge' function of mergesort you can use an iterator to the left sub-list and a second iterator the right sub-list, and advance the iterator of

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 18PE

See similar textbooks

Similar questions

What is the biggest advantage of linked list over array? Group of answer choices Unlike array, linked list can dynamically grow and shrink With linked list, it is faster to access a specific element than with array Linked list is easier to implement than array Unlike array, linked list can only hold a fixed number of elements
There are many differences between array and linked list, one of these differences: a. In a linked list insertion and deletion takes more time b. Array supports random access while linked List supports sequential access c. in linked list, elements are stored in contiguous memory location while in array are stored anywhere in the memory d. None of the above
JAVA Help: Mergesort Implement a natural merge sort for linked lists. (This is the method of choice for sorting linked lists because it uses no extra space and is guaranteed to be linearithmic.) During each iteration, natural merge sort works by scanning the list from the left to right identifying naturally sorted sub-lists and merging the sub-lists, and continue scanning further identifying and merging the sub-lists until the end of the list. Repeats the process until the entire list is sorted. Example: Unsorted list M -> E -> R -> G -> E -> S -> O -> R -> T -> E -> X -> A -> M -> P -> L -> E After first iteration: E - > M -> R -> E -> G -> S -> E -> O -> R -> T -> X -> A -> L -> M -> P -> E After second iteration: E -> E -> G -> M -> R -> S -> A -> E -> L -> M -> 0 -> P -> R -> T -> X -> E After third iteration: A -> E -> E -> E -> G…
Python Implement a singly linked list with the following functions: - add_head(e) - add_tail(e) - find_3rd_to_last() - returns element located at third-to-last in the list - reverse() - reveres the linked list, note, this is not just printing elements in reverse order, this is actually reversing the list
Introduction For this assignment, you are to write a program which implements a Sorted List data structure using a circular array-based implementation and a driver program that will test this implementation. The Sorted List ADT is a linear collection of data in which all elements are stored in sorted order. Your implementation has to store a single int value as each element of the list and support the following operations: 1. add(x) – adds the integer x to the list. The resulting list should remain sorted in increasing order. The time complexity of this operation should be 0(N), where N is the size of the list. 2. removefirst() - deletes the first integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 3. removelast() – deletes the last integer from the list and returns its value. The remaining list should remain sorted. Time complexity of this operation should be 0(1). 4. exists(x) – returns true if the…
Answer using C languageIn this project, you will implement a Polynomial ADT using LinkedLists. You will implement the Multiplication, Addition, and Subtractionoperations of polynomials.Your program should be able to read a file of polynomials calledequations.txt and store each equation in a doubly-linked list. Once thefile is read and equations are loaded into the linked lists, the usershould be able to perform mathematical operations on thepolynomials (addition, subtraction, and multiplication). Once the userselect an operation through a menu, the output should be displayedand then the menu should show again. Another option for the user isto store the results of all operations in a file called results.txt. Yourapplication should show an appropriate screen with menu options toinform the user of the available operations to let her/him to choosefrom.Example of input file:2x^7+10x^5-10x^3+2x+1-15x^7-10x^5+90x^2-22x^2 + x - 1Upon user selection, the application should show the output of…
b) Selection sort can also be applied to linked lists because the general algorithm is the same. Write a simple program code to illustrates a selection sort based on array list that takes a series of input numbers from user and print the before and after sorting Ilist. Use the 'arrayListType.h' library in your program.
The function interleave_lists in python takes two parameters, L1 and L2, both lists. Notice that the lists may have different lengths. The function accumulates a new list by appending alternating items from L1 and L2 until one list has been exhausted. The remaining items from the other list are then appended to the end of the new list, and the new list is returned. For example, if L1 = ["hop", "skip", "jump", "rest"] and L2 = ["up", "down"], then the function would return the list: ["hop", "up", "skip", "down", "jump", "rest"]. HINT: Python has a built-in function min() which is helpful here. Initialize accumulator variable newlist to be an empty list Set min_length = min(len(L1), len(L2)), the smaller of the two list lengths Use a for loop to iterate k over range(min_length) to do the first part of this function's work. On each iteration, append to newlist the item from index k in L1, and then append the item from index k in L2 (two appends on each iteration). AFTER the loop…
Python program- implement a singly linked list with following functions: - add_head(e) - add_tail(e) - find_3rd_to_last() - returns element located at third-to-last in the list - reverse() - reveres the linked list, note, this is not just printing elements in reverse order, this is actually reversing the list
C++ ONLY Add the following functions to the linked list. int getSize() -> This function will return the number of elements in the linked-list. This function should work in O(1). For this keep track of a size variable and update it when we insert a new value in the linked-list. int getValue(index) -> This function will return the value present in the input index. If the index is greater or equal to the size of the linked-list return -1. void printReverse() -> This function will print the linked list in reverse order. You don’t need to reverse the linked list. Just need to print it in reverse order. You need to do this recursively. You cannot just take the elements in an array or vector and then print them in reverse order. void swapFirst() -> This function will swap the first two nodes in the linked list. If the linked-list contains less than 2 elements then just do nothing and return. To check your code add the following code in your main function. LinkedList l;…
Circular Lists - All One Problem! A linear list is being maintained circularly in an array c[0…n-1] with front, and rear set up as for circular queues. Draft a formula/algorithm in terms of front, rear, and n for the number of elements in the list. Write an algorithm to delete the k-th element in the list. Write an algorithm to insert an element y immediately after the k-th element. Calculate the time complexity of your algorithms for b) and c).
Create a doubly link list with at least 5 nodes, then perform the following operation on that link list. As you perform the operation, write down the algorithm and c++ code too. Show the operations diagrammatically. Traversal Searching Sorting