How to sort a linked list using bubble-sort?

问题:

I am trying to use bubble-sort in order to sort a linked list. I use curr and trail in order to traverse thru the list. curr is supposed to be one step ahead of trail always. This is my code so far:

void linked_list::sort ()
{
  int i,j=0;
  int counter=0;
  node *curr=head;
  node *trail=head;
  node *temp=NULL;

  while (curr !=NULL)
  {
    curr=curr->next;    //couting the number of items I have in my list. 
    counter++;          //this works fine.
  }

  curr=head->next;          // reseting the curr value for the 2nd position.

  for (i=0; i<counter; i++)
  {
    while (curr != NULL)
    {
      if (trail->data > curr->data)
      {
        temp=curr->next;      //bubble sort for the pointers.
        curr->next=trail;
        trail->next=temp;

        temp=curr;         //reseting trail and curr. curr gets back to be infront.
        curr=trail;     
        trail=temp;

        if (j==0)   //i'm using j to determine the start of the loop so i won't loose the head pointer.
        {
          head=trail;
        }

      }
      j++;
      trail=curr;
      curr=curr->next;   //traversing thru the list. nested loop.
    }

    trail=head;
    curr=trail->next;
    curr->next=trail->next->next;  //traversing thru the list. outer loop.
    j=0;
  }
}

What am I missing here?

回答1:

You're missing several things; the most important being linked lists are not arrays, and as such you cannot easily do certain algorithms with both interchangeably. With that please consider the following:

• List length is determined by reaching the last node, but you don't need it for this algorithm. There should be no reason to scan the list just to find a count that you don't need in the first place. Your "finished" state is reached when the last segment of the bubble sort reaches a single node (i.e. it has no next to goto).
• The secret to linked list (or any other node-pointer pattern) is the manipulation of the pointers. To that end, you can greatly utilize something you already use for manipulating your nodes: pointers, but not just any pointers. pointers to pointers.
• Never underestimate the power of a sheet of paper and a pencil to draw out how you want your algorithm to work. Especially for something like this:

Now take a look at the following considerably different approach. There is something within that is paramount to understanding the overall algorithm, but I'll save it for after the code :

void ll_bubblesort(struct node **pp)
{
    // p always points to the head of the list
    struct node *p = *pp;
    *pp = nullptr;

    while (p)
    {
        struct node **lhs = &p;
        struct node **rhs = &p->next;
        bool swapped = false;

        // keep going until qq holds the address of a null pointer
        while (*rhs)
        {
            // if the left side is greater than the right side
            if ((*rhs)->data < (*lhs)->data)
            {
                // swap linked node ptrs, then swap *back* their next ptrs
                std::swap(*lhs, *rhs);
                std::swap((*lhs)->next, (*rhs)->next);
                lhs = &(*lhs)->next;
                swapped = true;
            }
            else
            {   // no swap. advance both pointer-pointers
                lhs = rhs;
                rhs = &(*rhs)->next;
            }
        }

        // link last node to the sorted segment
        *rhs = *pp;

        // if we swapped, detach the final node, terminate the list, and continue.
        if (swapped)
        {
            // take the last node off the list and push it into the result.
            *pp = *lhs;
            *lhs = nullptr;
        }

        // otherwise we're done. since no swaps happened the list is sorted.
        // set the output parameter and terminate the loop.
        else
        { 
            *pp = p;
            break;
        }
    }
}

This is radically different than you probably expected. The purpose of this simple exercise is to establish that we're evaluating data, but we're actually sorting pointers. Notice that except for p, which is always the head of the list, we use no additional pointers to nodes. Instead we use pointers-to-pointers to manipulate the pointers buried in the list.

To demonstrate how this algorithm works I've written a small test app that makes a random list of integers, then turns the above loose on said list. I've also written a simple print-utility to print the list from any node to the end.

void ll_print(struct node *lst)
{
    while (lst)
    {
        std::cout << lst->data << ' ';
        lst = lst->next;
    }
    std::cout << std::endl;
}

int main()
{
    std::random_device rd;
    std::default_random_engine rng(rd());
    std::uniform_int_distribution<int> dist(1,99);

    // fill basic linked list
    struct node *head = nullptr, **pp = &head;
    for (int i=0;i<20; ++i)
    {
        *pp = new node(dist(rng));
        pp = &(*pp)->next;
    }
    *pp = NULL;

    // print prior to sort.
    ll_print(head);
    ll_bubblesort(&head);
    ll_print(head);
    return 0;
}

I've also modified the original algorithm to include printing after each pass that swaps something:

    *pp = *lhs;
    *lhs = nullptr;
    ll_print(p);

Sample Output

6 39 13 80 26 5 9 86 8 82 97 43 24 5 41 70 60 72 26 95 
6 13 39 26 5 9 80 8 82 86 43 24 5 41 70 60 72 26 95 
6 13 26 5 9 39 8 80 82 43 24 5 41 70 60 72 26 86 
6 13 5 9 26 8 39 80 43 24 5 41 70 60 72 26 82 
6 5 9 13 8 26 39 43 24 5 41 70 60 72 26 80 
5 6 9 8 13 26 39 24 5 41 43 60 70 26 72 
5 6 8 9 13 26 24 5 39 41 43 60 26 70 
5 6 8 9 13 24 5 26 39 41 43 26 60 
5 6 8 9 13 5 24 26 39 41 26 43 
5 6 8 9 5 13 24 26 39 26 41 
5 6 8 5 9 13 24 26 26 39 
5 6 5 8 9 13 24 26 26 
5 5 6 8 9 13 24 26 
5 5 6 8 9 13 24 26 26 39 41 43 60 70 72 80 82 86 95 97

Another Sample

62 28 7 24 89 20 94 26 27 21 28 76 60 51 99 20 94 48 81 36 
28 7 24 62 20 89 26 27 21 28 76 60 51 94 20 94 48 81 36 
7 24 28 20 62 26 27 21 28 76 60 51 89 20 94 48 81 36 
7 24 20 28 26 27 21 28 62 60 51 76 20 89 48 81 36 
7 20 24 26 27 21 28 28 60 51 62 20 76 48 81 36 
7 20 24 26 21 27 28 28 51 60 20 62 48 76 36 
7 20 24 21 26 27 28 28 51 20 60 48 62 36 
7 20 21 24 26 27 28 28 20 51 48 60 36 
7 20 21 24 26 27 28 20 28 48 51 36 
7 20 21 24 26 27 20 28 28 48 36 
7 20 21 24 26 20 27 28 28 36 
7 20 21 24 20 26 27 28 28 
7 20 21 20 24 26 27 28 
7 20 20 21 24 26 27 
7 20 20 21 24 26 27 28 28 36 48 51 60 62 76 81 89 94 94 99 

Notice how as soon as we have an already-sorted segment left in our ever-decreasing source list, we're done.

Summary

I strongly advise walking through the above algorithm with a debugger to understand better how it works. In fact, I advise that with most algorithms anyway, but algorithms that perform pointer-to-pointer actions can be a little daunting until you understand how powerful that really are. This is not the only way to do this task, but is an intuitive approach if you think about how linked lists are managed, and how all you're really doing is changing values stored in pointers in predictable places.

回答2:

Basically, here is a revised sort. You mostly had the right idea. Mainly you messed up the swapping of pointers for the nodes. Here is a revised algorithm that is slightly simpler. On the outer loop is a for the number of elements in the list. Then the inner loop is the pushing of values to the end of the list progressively. We track two pointers trail and curr. And we compare curr and curr->next.

void linked_list::sort ()
{
  int count = 0, i;
  node *start = head;
  node *curr = NULL;
  node *trail = NULL;
  node *temp = NULL;

  while(start != NULL) { //grab count
    count++;
    start = start->next;
  }

  for(i = 0; i<count; ++i) { //for every element in the list

    curr = trail = head; //set curr and trail at the start node

    while (curr->next != NULL) { //for the rest of the elements in the list
      if (curr->data > curr->next->data) { //compare curr and curr->next

        temp = curr->next; //swap pointers for curr and curr->next
        curr->next = curr->next->next;
        temp->next = curr;

        //now we need to setup pointers for trail and possibly head
        if(curr == head) //this is the case of the first element swapping to preserve the head pointer
          head = trail = temp;
        else //setup trail correctly
          trail->next = temp;
        curr = temp; //update curr to be temp since the positions changed
      }
      //advance pointers
      trail = curr;
      curr = curr->next;
    }
  }
}

回答3:

I think this is what you looking for:

void BubbledSort_linked_list(struct Node **head)
{
    Node * curr = *head;
    Node * next;
    int temp;

    while (curr && curr->next)
    {

        Node * next = curr->next;
        while (next)
        {
            if (curr->data > next->data)
            {
                std::swap(next->data, curr->data);
            }
            next = next->next;
        }
        curr = curr->next;
    }
}

回答4:

Bubble sort using array can be easily modified to bubble sort using linked list

// Using array
    for(int i=0;i<ar.length;i++){
        for(int j=0;j<ar.length-1;j++){
            if(ar[j]>ar[j+1]){
                int temp = ar[j];
                ar[j]=ar[j+1];
                ar[j+1] = temp;
            }
        }
    }

// Using linkedlist
    void bubblesortlinkedlist(Node head){
        Node i= head,j=head;
        while(i!=null){
            while(j.next!=null){
                if(j.data>j.next.data){
                    int temp = j.data;
                    j.data = j.next.data;
                    j.next.data = temp;
                }
                j=j.next;
            }
            j=head;
            i=i.next;
        }
    }

回答5:

Here is the Java Implementation of Bubble Sort on Linked List:

• Time Complexity: O(n^2)
• Space Complexity: O(1) - Bubble sort is In-Place sorting algorithm

class Solution
{
    public ListNode bubbleSortList(ListNode head)
    {
        boolean isSwapped = true;

        for(ListNode current = head, tail = null; isSwapped && head != tail; tail = current, current = head)
        {
            for(isSwapped = false; current.next != tail; current = current.next) 
            { 
                if (current.val > current.next.val) 
                {  
                    swap(current, current.next); 
                    isSwapped = true; 
                }
            }
        }
        return head;
    }

    private void swap(ListNode x, ListNode y)
    {
        if(x != y)
        {
            int temp = x.val;
            x.val = y.val;
            y.val = temp;    
        }
    }
}