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
(i)  Consider a system using flooding with hop counter. Suppose that the hop counter is originally set to the "diameter" (number of hops in the longest path without traversing any

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

RENDERING, SHADING AND COLOURING By introducing hidden line removal we have already taken one step away from wire-frame drawings towards being able to realistically model and d

Write an algorithm using pseudocode which takes temperatures input over a 100 day period (once per day) and output the number of days when the temperature was below 20C and the num

Using the cohen sutherland. Algorithm. Find the visible portion of the line P(40,80) Q(120,30) inside the window is defined as ABCD A(20,20),B(60,20),C(60,40)and D(20,40)

(a) Discuss the role played by Business Intelligence Systems in giving companies strategic advantage. (b) Explain the term heuristics searching . (c) With the use of an appr


Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Q. Illustrate the result of running BFS and DFS on the directed graph given below using vertex 3 as source.  Show the status of the data structure used at each and every stage.

Speed cameras read the time a vehicle passes a point (A) on road and then reads time it passes a second point (B) on the same road (points A and B are 100 metres apart). Speed of t