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
Implementing abstract data types A course in data structures and algorithms is hence a course in implementing abstract data types. It may seem that we are paying a lot of atten

This method is the reverse of FIFO and assumes that each issue of stock is made from latest items received in the enterprises .Thus if the last lot to be received is not sufficient

i want to write code for unification algorithm with for pattern matching between two expression with out representing an expression as alist

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

Preconditions assertion A precondition is an assertion which should be true at the initiation of an operation. For instance, a square root operation can't accept a negative a

What is the difference between a grounded header link list and a circular header link list? A header linked list is a linked list which always having a special node, known as t

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Linked lists are among the most common and easiest data structures. They may be used to implement various other common abstract data types, including queues, stacks, symbolic expre

What is algorithm's Optimality? Optimality  is  about  the  complexity  of  the  problem  that  algorithm  solves.  What  is  the  minimum amount  of  effort  any  algorithm  w

Determine about the logic gates Many electronic circuits operate using binary logic gates. Logic gates essentially process signals that represent true or false or equivalent i.