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

Algorithm for Z-Buffer Method (a)  Initialize every pixel in the viewport to the smallest value of z, namely z0 the z-value of the rear clipping plane or "back-ground". Store a

Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.

State  in brief about assertion Assertion: A statement which should be true at a designated point in a program.

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

write an algorithm for multiplication of two sparse matrices using Linked Lists

Define the term 'complexity of an algorithm; Complexity of an algorithm is the calculate of analysis of algorithm. Analyzing an algorithm means predicting the resources that th

explain implementation of circular queue insert,delete operations

Question 1 . Give the structure of PL/SQL Blocks and explain Question 2 . Differentiate between PL/SQL functions and procedures Question 3 . Explain the following Par

In this assignment, you are invited to design and implement a software system for catalogue sale. A catalogue is organised in a tree structure. Each node of the catalogue tree repr