3
\$\begingroup\$

This is supposed to be efficient code, but it's taking much longer than what a normal insertion sort would take. I can't identify what's the problem with this insertion sort. Is there an implementation problem?

// function to sort a singly linked list using insertion sort
    void insertionSort(element_t **head_ref)
{
    // Initialize sorted linked list
    element_t *sorted = NULL;

    // Traverse the given linked list and insert every
    // node to sorted
    element_t *current = *head_ref;
    while (current != NULL)
    {
        // Store next for next iteration
        element_t *next = current->next;

        // insert current in sorted linked list
        sortedInsert(&sorted, current);

        // Update current
        current = next;
    }

    // Update head_ref to point to sorted linked list
    *head_ref = sorted;
}


/* function to insert a new_node in a list. Note that this
  function expects a pointer to head_ref as this can modify the
  head of the input linked list (similar to push())*/
void sortedInsert(element_t** head_ref, element_t* new_node)
{
    element_t* current;
    /* Special case for the head end */
    if (*head_ref == NULL || (*head_ref)->val >= new_node->val)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
    }
    else
    {
        /* Locate the node before the point of insertion */
        current = *head_ref;
        while (current->next!=NULL &&
               current->next->val < new_node->val)
        {
            current = current->next;
        }
        new_node->next = current->next;




current->next = new_node;
    }
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Can you provide a minimum working example, especially with the kind of data you're using as input? Also, it would be nice to know what you mean by "much longer", and "usual". \$\endgroup\$
    – ChatterOne
    Aug 8 '16 at 8:31
0
\$\begingroup\$

Code performs as expected.

Insertion sort has an expected O(n2) performance and OP's code has about 0.25*n2 compares per length n of a linked list.

By adding a counti to sortedInsert() and providing various length lists with random data to insertionSort(), the below graph was determined.

void sortedInsert(element_t** head_ref, element_t* new_node) {
  element_t* current;
  if (*head_ref == NULL || (*head_ref)->val >= new_node->val) {

    counti++;  // *****

    new_node->next = *head_ref;
    *head_ref = new_node;
  } else {
    current = *head_ref;

    counti++;  // *****

    while (current->next != NULL && current->next->val < new_node->val) {

      counti++;  // *****

      current = current->next;
    }
    new_node->next = current->next;
    current->next = new_node;
  }
}

Compare Count vs. List Length

No functional implementation problem found.

Lots of review-able issues (format, lack of supporting code, etc.), but OP did not ask for that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.