Sorting algorithm for singly linked lists, Data Structure & Algorithms

Q. Which sorting algorithm can be easily adaptable for singly linked lists? Explain your answer as well.       


Ans:

The simple Insertion sort is simply adaptable to singly linked list. This is the method in which there is an array link of pointers, one for each of the original array. Initially link[i] = i + 1 for 0 < = i < n-1 and link[n-1] = -1. Hence the array can be thought of as a linear link list pointed to by an external pointer first initialized to 0. To insert the kth element the linked list is traversed until the proper position for x[k] is found, or until the end of the list is reached. At that point x[k] can be inserted into the list by simply adjusting the list pointers without shifting any elements in the array. This decreases the time needed for insertion but not the time needed for searching for the proper position. The number of replacements in the link array is O(n).

 


 

 

 

Posted Date: 7/10/2012 5:03:20 AM | Location : United States







Related Discussions:- Sorting algorithm for singly linked lists, Assignment Help, Ask Question on Sorting algorithm for singly linked lists, Get Answer, Expert's Help, Sorting algorithm for singly linked lists Discussions

Write discussion on Sorting algorithm for singly linked lists
Your posts are moderated
Related Questions
an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Ruby implements Range of T Abstract data type Ruby implements Range of T ADT in its Range class. Elements of carrier set are represented in Range instances by recording interna

one to many one to one many to many many to one

Q. Write down an algorithm to insert a node in the beginning of the linked list.                         Ans: /* structure containing a link part and link part

Q1. Define a sparse matrix. Explain different types of sparse matrices? Evaluate the method to calculate address of any element a jk of a matrix stored in memory. Q2. A linear

If a node in a binary tree is not containing left or right child or it is a leaf node then that absence of child node can be represented by the null pointers. The space engaged by

Draw trace table and determine output from the following flowchart using following data: Number = 45, -2, 20.5

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

Implement multiple stacks in a single dimensional array. Write algorithms for various stack operations for them.

What is a Spanning tree of a graph? A Spanning Tree is any tree having of vertices of graph tree and some edges of graph is known as a spanning tree.