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
Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

null(nil) = true                     // nil refer for empty tree null(fork(e, T, T'))= false   //  e : element , T and T are two sub tree leaf(fork(e, nil, nil)) = true leaf(

data structure for multiqueue

Any binary search tree must contain following properties to be called as a red-black tree. 1. Each node of a tree should be either red or black. 2. The root node is always bl

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Give the example of bubble sort algorithm For example List: - 7 4 5 3 1. 7 and 4 are compared 2. Since 4 3. The content of 7 is now stored in the variable which was h

A Binary Search Tree is binary tree which is either empty or a node having a key value, left child & right child. By analyzing the above definition, we notice that BST comes int


In what ways we can get the context sensitive F1 help on a field?' Data element documentation. Data element additional text in screen painter. Using the process on help r