Блог

 /* SORTING SINGLY LINKED LIST USING QUICK SORT ALGORITHM */

/*Function to get the pivot node*/

node *partition(node *start, node *end)
{
    if (start == NULL || start->next == NULL)   //If one node or no node is present
    {
        return start;
    }

    node *pivot, *cur, *pre, *temp;
    pivot = pre = start;
    cur = start->next;

    while (1)
    {
        if (cur == end)
        {
            break;  //while loop breaks
        }
        else if (cur->data < pivot->data) 
        {
            temp = cur;
            pre->next = cur->next;
            cur = cur->next;    //Here swapping is done basically
            temp->next = pre;
            head = temp;
        }
        else
        {
            pre = cur;
            cur = cur->next;
        }
    }
    return pivot; //pivot node returned to PartitionNode in quick sort function
}
 

 /*quicksort recursive ; what conditions do I need to apply here so the it can work properly
recursion call is not working as expected; please I ask you correct this it's been 2 days now stuck on same problem */ 

void *quicksort(node *head, node *tail)
{
    node *start = head;
    node *PartitionNode = partition(start, tail->next); //partition function called to get pivot node
    node *list2 = PartitionNode->next;

    while (start != PartitionNode amp;amp; list2 != tail)  //not working and so much confusing please help
    {
        while (start->next != PartitionNode)
        {
            quicksort(start, PartitionNode);
            node *PartitionNode = partition(start, PartitionNode);
        }

        while (list2 != tail) //list2 start will PartitionNode->next
        {
            quicksort(PartitionNode->next, tail->next);
            node *PartitionNode = partition(PartitionNode->next, tail->next);
        }
    }
}
 

     node *partition(node *start, node *end) //pivot is first element of linked list
    {
    node *pivot_prev = start;
    node *current = start;
    int pivot = start->data;
    start = start->next;
    while (start != end->next)
    {
    if (start->data < pivot)
    {
        pivot_prev = current;
        int temp = current->data;
        current->data = start->data;
        start->data = temp;
        current = current->next;
     }
     start = start->next;
     }
     return pivot_prev; //current not will not be returned as current not is already at its right place
      }

    void quicksort(node *start, node *end)
    {
    if (start == end)
    {
    return;
    }
    node *prev = partition(start, end);
   

    quicksort(start, prev);
    quicksort(prev->next, end);
    }