Is there a way to calculate the progress of a sorting algorithm?

Question

I'm trying to make a subjective sort based on shell sort. I'm referring to the original (Donald Shell's) algorithm. I already made all the logic, where it is exactly the same as the shell sort, but instead of the computer calculate what is greater, the user determines subjectively what is greater. But the problem is that I would like to display a percentage or something to the user know how far in the sorting it is already. That's why I want to find a way to know it.

I tried asking here(What is the formula to get the number of passes in a shell sort?), but maybe I didn't express myself well last time and they closed the question. I tried first associating the progress with the number of passes in the array in the shell sort. But lately, I noticed it is not a fixed number. So if you have an idea of how it is the best way to display the progress of the sorting, I will really appreciate it.

I did this formula displaying it by color based on the number of passes, it is the closest I could get, but it doesn't match perfectly the maximum range for the color list. (Code in Dart/Flutter)

List<Color> colors = [
    Color(0xFFFF0000),//red
    Color(0xFFFF5500),
    Color(0xFFFFAA00),
    Color(0xFFFFFF00),//yellow
    Color(0xFFAAFF00),
    Color(0xFF00FF00),
    Color(0xFF00FF00),//green
  ];
[...]
style: TextStyle(
    color: colors[(((pass - 1) * (colors.length - 1)) / sqrt(a.length).ceil()).floor()]
),
[...]

It doesn't need to be this way I tried to do, so please if you have an idea how to display the progress of the sorting please share it.

EDIT: I think I found the answer!! At least for shell sort, it is working based on the number os passes through the array. Just changing the sqrt(a.length).ceil() with (log(a.length) / log(2)).floor() This line:

color: colors[(((pass - 1) * (colors.length - 1)) / (log(a.length) / log(2)).floor()).floor()]),

Answer 1

How far along you are in many types of sorts usually depends on the initial order of the elements to be sorted. For shellsort you have the individual passes further complicating the determination process.

As an example and to illustrate the problem, take insertion sort:

• It is the fastest sort of all in one specific set of circumstances, namely to sort a vector that is already sorted in the intended direction - requiring n-1 comparisons.
• It is one of the slowest in the opposite circumstance, sorting a vector that is already sorted but in the opposite direction - requiring (n*(n-1))/2 comparisons

Assuming that n=100, the best case is 99 and the worst 4950 comparisons. That's a factor of 1:50 in the number of comparisons required. So when you've done 50 comparisons, you're 50% through the best case or 1% through the worst.

Shellsort does not have as good a case for already sorted data as insertion sort but it is nonetheless very good. The opposite case - the worst case for insertion sort - is actually not the worst case for shellsort and it is much faster than insertion sort's. Shellsort's worst case is also much better than insertion sorts worst. Which means that for a given n you will know exactly the best and worst cases for insertion sort and you will know that shellsort will be somewhat slower at the best case and significantly faster than the worst - if that helps in your quest.

But however you look at it, you won't be able to reliably predict how far along in a (shell)sort you are unless you know how many comparisons are required for the specific data and you only know that after you have sorted it.

Maybe you should use a progress bar like Microsoft uses in Windows: it starts off really quickly but then suddenly realizes that it is halfway along and maybe it should slow down so as not to reach the end even though a lot of sorting remains. The last few millimeters of its travel may take many minutes in some circumstances.