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
Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Implement a linear-expected-time algorithm for selecting the k th smallest element Algorithm description 1. If |S| = 1, then k = 1 and return the element in S as the an

Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Explain Optimal Binary Search Trees One of the principal application of Binary Search Tree is to execute the operation of searching. If probabilities of searching for elements

The assignment aims at consolidating your knowledge on data mining techniques and developing practical skills through solving a problem of transcription factor binding sites recogn

differentiate between indexing and hashing in file organization

write a program that find,search&replace a text string

The Linked list is a chain of structures wherein each structure contains data in addition to pointer, which stores the address (link) of the next logical structure in the list.

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most important types of trees which are used to model yes/no, on/off, higher/lower, i.e.,

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know