I wrote some sorting code:

// A function to print an int array
void printArray(int arr[], int size) {
// Loop through the array elements
for (int i = 0; i < size; i++) {
 // Print the current element with a space
 cout << arr[i] << " ";
}
// Print a new line at the end
cout << endl;
}


void mikesort(int a[], int n)
{
if (n == 0 || n == 1) return;

for (int i = 0; i < n - 1; i++)
 for (int j = 0; j < n - 1; j++)
  if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}

void testsort(void)
{
int a[] = { 5,4,8,2,1 };
printArray(a, 5);
mikesort(a, 5);
printArray(a, 5);
}

It is like bubble sort but easier to remember. It looks like it works.

Anyone know how to prove if it works or not? Does this algorithm have a name?

Thanks.

The worst case is if a[n-1] must move to a[0]. The inner loop moves the value one position, so you must do that n-1 times. That means the outer loop must have at least n-1 iterations, which it does exactly. In other words, it's correct.

As for a name, I am not aware of a name for it. For fun I checked The Art of Computer Programming Volume 3 by Donald Knuth, and the Bubble sort algorithm there tracks the position of the last changed value in the array to reduce the number of iterations in the inner loop and to detect that sorting is done. Compared to your algorithm, the algorithm in the book is way more advanced 🙂

This is a bubble sort. A poorly optimized bubble sort, but a bubble sort nonetheless.

Why are you writing your own sorting code, and why do you consider “easy to remember” a good property for a sorting algorithm to have?

mike74 said:
It is like bubble sort but easier to remember. It looks like it works. Anyone know how to prove if it works or not? Does this algorithm have a name?

It is a form of bubble sort. Yes, it does look like it works. Yes, it has a name, “bubble sort”.

It was built for an era with specific purposes in mind, and it remains about the only viable option in that specific case: Low memory, with linear access storage. In other words, machines where you can only realistically have a handful of records in memory, AND where you only have a single storage (like a single physical tape) where the cost of seeking/rewinding the tape dominates everything else. Break the restrictions and there are better performers. If you have the memory there are better algorithms that manipulate the index first in memory, then reorganize the tape data directly to their final place. If you have more storage (like a second tape) there are algorithms like merge sort that work more efficiently.

mike74 said:
Anyone know how to prove if it works or not?

There is std::is_sorted. So just to answer that specific question. you could create arrays of random values and sort them, in a loop, a few hundred-thousand times, and check if “is_sorted” is always true afterwards.