What sorting algorithm is this?

Question

Update: OK I see it's a bubble sort, but is it less efficient because it doesn't stop when there's no swap on a particular run? It runs until first is null.

Hi, I have a sorting algorithm as follows. My question is, which sorting algorithm is this? I thought it was bubble sort, but it does not do multiple runs. Any idea? Thanks!

//sorting in descending order
struct node
{
    int value;
    node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers

Sort( Node *Head)
{
    node* first,second,temp;
    first= Head;
    while(first!=null)
    {
        second=first->NEXT;
        while(second!=null)
        {
            if(first->value < second->value)
            {
                temp = new node();
                temp->value=first->value;
                first->value=second->value;
                second->value=temp->value;
                delete temp;
            }
            second=second->NEXT;
        }

        first=first->NEXT;
    }
}

Answer 1

Let's make the algorithm clearer:

Sort {
   first = head;
   while (first ≠ NULL) {
      next = first.next
      while (next ≠ NULL) {
         if (first.value < next.value)
            swap first.value and next.value
         advance next
      }
      advance first
   }
}

This is a very inefficient implementation of insertion sort.

---

Example run revealing the insertion sort characteristics:

5 → 2 → 3 → 1 → nil
^   ^
f   n [swap]

2 → 5 → 3 → 1 → nil
^       ^
f       n

2 → 5 → 3 → 1 → nil
^           ^
f           n [swap]

1 → 5 → 3 → 2 → nil
^               ^
f               n

1 → 5 → 3 → 2 → nil   // insert the minimum value 1 to the beginning of the sublist
    ^   ^
    f   n [swap]

1 → 3 → 5 → 2 → nil
    ^       ^
    f       n [swap]

1 → 2 → 5 → 3 → nil  // insert the minimum value 2 to the beginning of the sublist
    ^           ^
    f           n

1 → 2 → 5 → 3 → nil
        ^   ^
        f   n [swap]

1 → 2 → 3 → 5 → nil  // insert the minimum value 3 to the beginning of the sublist
        ^       ^
        f       n

1 → 2 → 3 → 5 → nil  // insert the minimum value 5 to the beginning of the sublist
            ^   ^
            f   n

1 → 2 → 3 → 5 → nil
                ^
                f

Answer 2

This is a kind of a hybrid between a 'classic' bubble sort and a selection sort - but closer to the classic bubble sort.

In the classic bubble sort, the inner loop swaps adjacent pairs as it walks the list/array.

In the classic selection sort, the inner loop keeps track of the largest value it finds in the remaining portion of the list, and swaps it with the first value in the portion of the list that the inner loop is currently considering.

The sort as posted in the question is like the Selection sort in that the swap is always performed with the first value in the sub-list that the inner loop is considering. It's different from the Selection sort (and is similar to the classic Bubble sort) in that it performs a swap whenever it finds a value larger than the current first member of the inner loop's sub-list.

However, it's different than the classic Bubble sort in that it's not swapping adjacent pairs. In the classic Bubble sort, when the inner loop has finished working a round, the largest element of the list has filtered to the bottom of the list, but in this variation, the smallest element has filtered to the top of the inner-loop's sub-list.

I'd label this more a variation of the classic Bubble sort rather than the Selection sort because the performance characteristics of the sort in the question are the same as the classic Bubble sort (O(n^2) comparisons and O(n^2) swaps), while a Selection sort has O(n) swaps.

But, one other difference between the classic Bubble sort and this one is that a classic Bubble sort is stable, while the sort in the question isn't. Consider the following list of items when run through the sort. Only the numbers are used in the comparison - the letters are used just to distinguish between the elements that have the same rank. The diagrams show the swap operations performed (in the interest of brevity, the comparisons aren't shown):

3.a  3.b   3.c   2.a   2.b   1.a
 ^                ^
 +----------------+


2.a  3.b   3.c   3.a   2.b   1.a
 ^                            ^
 +----------------------------+


1.a  3.b   3.c   3.a   2.b   2.a
      ^                 ^
      +-----------------+


1.a  2.b   3.c   3.a   3.b   2.a
            ^                 ^
            +-----------------+


1.a  2.b   2.a   3.a   3.b   3.c

Note that at the end of the sort, the relative position of items 2.a and 2.b have changed, indicating a non-stable sort.