Sort Linked List in Ascending Order - C#
Join the DZone community and get the full member experience.
Join For FreeSort Linked List in Ascending Order - C#
Efficiency: O(n^2)
Inspired by Selection Sort algorithm
///
/// This method sorts elements in linked list and returns a new sorted linked list
///
/// head node of unsorted linked list
/// number of elements in unsorted linked list
/// head node of new sorted linked list
public static Node SortLinkedList(Node head, int count)
{
// Basic Algorithm Steps
//1. Find Min Node
//2. Remove Min Node and attach it to new Sorted linked list
//3. Repeat "count" number of times
Node _current = head;
Node _previous = _current;
Node _min = _current;
Node _minPrevious = _min;
Node _sortedListHead = null;
Node _sortedListTail = _sortedListHead;
for (int i = 0; i < count; i++)
{
_current = head;
_min = _current;
_minPrevious = _min;
//Find min Node
while (_current != null)
{
if (_current.Data < _min.Data)
{
_min = _current;
_minPrevious = _previous;
}
_previous = _current;
_current = _current.Next;
}
// Remove min Node
if (_min == head)
{
head = head.Next;
}
else if (_min.Next == null) //if tail is min node
{
_minPrevious.Next = null;
}
else
{
_minPrevious.Next = _minPrevious.Next.Next;
}
//Attach min Node to the new sorted linked list
if (_sortedListHead != null)
{
_sortedListTail.Next = _min;
_sortedListTail = _sortedListTail.Next;
}
else
{
_sortedListHead = _min;
_sortedListTail = _sortedListHead;
}
}
return _sortedListHead;
}
Sort (Unix)
Opinions expressed by DZone contributors are their own.
Comments