Robert Wessel writes:

On Tue, 26 Feb 2019 10:58:09 +0100, "Pascal J. Bourguignon"
wrote:

Robert Wessel writes:

bubble sort is very easy to write, it's just not fast.


Insertion sort is even easier to write. And it's usually twice as
fast as bubble sort.

Bubble sort is the fastest, on a vector already sorted. It's O(n) with
the best constants in this best case.


I've heard that assertion multiple time, but have not seen much
evidence to back it up. In some tests I've run over the years, bubble
sort and insertion sort on already sorted datasets tend to have
performance very nearly the same, if not identical, subject to
implementation vagaries. If there is an advantage, it's very small.

bubblesort still uses less comparisons:
------------------------------------------------------------
#include stdio.h

int a[]={1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19};

int bubblesort(int *a, int n)
{
int count=0;
int i, j;

for (j = 0; count++,jn; j++)
{
int swapped = 0;
i = 0;
while (count++,in-1)
{
if (count++,a[i] a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
swapped = 1;
}
i++;
}

if (!swapped)
break;

n--;
}
return count;
}

int insertionsort(int *a, int n)
{
int count=0;
int i, j;

for (j = 1; count++,jn; j++)
{
i = j;
while ((count++,i0) && (count++,a[i] a[i-1]))
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
i--;
}
}
return count;
}

int main()
{
printf("bubblesort = %5d comparisons\n",bubblesort(a, sizeof(a)/sizeof(a[0])));
printf("insertionsort = %5d comparisons\n",insertionsort(a, sizeof(a)/sizeof(a[0])));
return 0;
}
------------------------------------------------------------

-*- mode: compilation; default-directory: "~/" -*-
Compilation started at Tue Feb 26 19:22:01

SRC="/Users/pjb/s.c" ; EXE="s" ; gcc -I. -L. -g3 -ggdb3 -o ${EXE} ${SRC} && ./${EXE} && echo status = $?
bubblesort = 38 comparisons
insertionsort = 55 comparisons
status = 0

Compilation finished at Tue Feb 26 19:22:05

--
__Pascal J. Bourguignon__
http://www.informatimago.com