What sorting algorithm?

Question

Update: OK. I see that this is a bubble, but it is less effective because it does not stop when there is no exchange for a specific run? It starts up to the first null value.

Hi, I have a sorting algorithm as follows. My question is which sorting algorithm is this? I thought it was a bubble, but it does not perform several runs. Any ideas? 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

Make the algorithm more understandable:

 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.

---

Sample run showing insertion sorting characteristics:

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

Answer 2

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

In classic bubble sorting, the inner loop changes adjacent pairs as it goes through the list / array.

In the classic sort selection, the inner loop keeps track of the largest value that it finds in the rest of the list and swaps it with the first value in the part of the list that the inner loop considers.

The sorting posted in the question is similar to the sorting of the selection in that the swap is always performed with the first value in the sub-list considered by the inner loop. It differs from selection sorting (and is similar to classic Bubble sorting) in that it swaps when it finds a value greater than the current first element of the inner subdirectory of the inner loop.

However, it differs from the classic Bubble type in that it does not replace adjacent pairs. In the classic Bubble sort, when the inner loop has finished work on the round, the largest list item is filtered at the bottom of the list, but in this embodiment, the smallest item is filtered at the top of the substring of the inner loop -list.

I would call it a variation of the classic Bubble sort rather than a sort sort, because the sorting performance characteristics in question are the same as the classic Bubble sort ( O(n^2) comparisons and O(n^2) swaps), while how selection sorting has O(n) swaps.

But, another difference between the classic Bubble type and this is that the classic Bubble sort is stable, but the sort in question is not. When viewing a sort, consider the following list of items. In comparison, only numbers are used - letters are used only to distinguish elements with the same rank. The diagrams show swap operations (not shown for the sake of brevity):

 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 sorting, the relative position of 2.a and 2.b has changed, indicating an unstable view.

Answer 3

This is pretty much a bubble. Bubble sorting is done in a linked list where the values ​​are swapped. The node!=null checks are to confirm whether the end is reached or not.

Answer 4

Sort Insert

It is very similar to sorting bubbles, except that instead of breaking adjacent pairs of elements, you move the smallest element to the top of the list, and then the next smallest element to the second position, etc.

Answer 5

Similar to sorting selections . In sorting sort, we find the value min in the list and swap with the first element and repeat the same for the other elements in the list. But there we do not exchange after finding the min element, instead, every time we find an element smaller than the first element (in the first pass), we replace it with the 1st element.