Trying to come up with a good algorithm for an insertions sort.. singly linked list..
Function will accept the head node to a list.. locate the highest and second highest nodes of a list (in this case based on the "priority" attribute.) Just want to know from people who have already ventured into this realm if I am on the road to success... Kinda having second thoughts on how to perform the actual swapping of nodes..
Code:
//Insertion Sort
void priority_sort(Node* head_ptr)
{
Node *higher, *lower, *current, *temp;
unsigned int elimination;
bool sorted = true;
temp = head_ptr;
if(head_ptr && head_ptr->next)
{
//Test for Sorted (Ascending Order)
while(temp && sorted)
{
current = temp;
temp = temp->next;
if(current->priority > temp->priority)
sorted = false;
}
if(!sorted)
{
current = head_ptr;
temp = head_ptr->next;
higher = NULL;
//Locate Highest & 2nd Highest
while(temp)
{
lower = NULL;
if(current->priority > temp->priority && temp->priority < elimination)
if(higher)
lower = higher;
higher = current;
elimination = lower->priority;
}
//Swap Highest and 2nd Highest Nodes
if(lower)
{
temp = lower;
higher = lower;
lower = temp;
}
//Handle case of last iteration
if(!lower && higher)
{
temp = head_ptr;
head_ptr = higher;
higher = temp;
}
}
}
}