Shell Sort

Shell sort adds one more loop outside bubble sort.

It starts by sorting small overlapping subsets, then makes then smaller but by then the array is mostly sorted.

It is an unstable sort.

Shell Sort in C §

m = N;
 
do {
  m = (m + 2) / 3;
 
  for (i = 0; i < m; i++) 
    for (k = i + m; k < N; k += m) 
      for (j = k; (j > 0) && (a[j] < a[j - m]); j -= m) {
        swap (&(a[j]), &(a[j - m])); 
        dump_array(a);     
      }
  }
while (m != 1);

Output: §

16 16 0 14 9 11 10 2 3 4 1 11 8 17 14 5 11 12 15 16
2 16 0 14 9 11 10 16 3 4 1 11 8 17 14 5 11 12 15 16
2 16 0 14 9 11 10 14 3 4 1 11 8 17 16 5 11 12 15 16
2 3 0 14 9 11 10 14 16 4 1 11 8 17 16 5 11 12 15 16
2 3 0 14 9 11 10 14 5 4 1 11 8 17 16 16 11 12 15 16
2 3 0 1 9 11 10 14 5 4 14 11 8 17 16 16 11 12 15 16
2 3 0 1 9 11 10 14 5 4 12 11 8 17 16 16 11 14 15 16
2 3 0 1 9 8 10 14 5 4 12 11 11 17 16 16 11 14 15 16
1 3 0 2 9 8 10 14 5 4 12 11 11 17 16 16 11 14 15 16
1 3 0 2 9 8 4 14 5 10 12 11 11 17 16 16 11 14 15 16
1 3 0 2 9 8 4 14 5 10 12 11 11 17 16 15 11 14 16 16
1 3 0 2 9 8 4 12 5 10 14 11 11 17 16 15 11 14 16 16
1 3 0 2 9 8 4 12 5 10 14 11 11 11 16 15 17 14 16 16
1 3 0 2 9 8 4 12 5 10 11 11 11 14 16 15 17 14 16 16
1 3 0 2 9 8 4 11 5 10 12 11 11 14 16 15 17 14 16 16
1 3 0 2 9 8 4 11 5 10 12 11 11 14 16 15 16 14 16 17
1 3 0 2 9 5 4 11 8 10 12 11 11 14 16 15 16 14 16 17
1 3 0 2 9 5 4 11 8 10 12 11 11 14 14 15 16 16 16 17
1 0 3 2 9 5 4 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 3 2 9 5 4 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 9 5 4 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 5 9 4 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 5 4 9 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 4 5 9 11 8 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 4 5 9 8 11 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 4 5 8 9 11 10 12 11 11 14 14 15 16 16 16 17
0 1 2 3 4 5 8 9 10 11 12 11 11 14 14 15 16 16 16 17
0 1 2 3 4 5 8 9 10 11 11 12 11 14 14 15 16 16 16 17
0 1 2 3 4 5 8 9 10 11 11 11 12 14 14 15 16 16 16 17

Code Example §

/* Basic Shell's sort
 
   Copyright (C) 2020 Embecosm Limited <www.embecosm.com>
   Contributor: Jeremy Bennett <jeremy.bennett@embecosm.com>
   SPDX-License-Identifier: GPL-3.0-or-later */
 
#include <stdlib.h>
#include <stdio.h>
 
#ifndef N
#define N 20
#endif
 
void
populate (int arr[])
{
  for (int i = 0; i < N; i++)
    arr[i] = rand () % N;
}
 
void
swap (int *a, int *b)
{
  int t = *a;
  *a = *b;
  *b = t;
}
 
void
dump_array (int arr[])
{
  for (int i = 0; i < N; i++)
    printf ("%d ", arr[i]);
 
  printf ("\n");
}
 
int
main ()
{
  int a[N];
  int i, j, k, m;
 
  srand (561U);
 
  populate (a);
  dump_array (a);
 
  m = N;
 
  do
    {
      m = (m + 2) / 3;
 
      for (i = 0; i < m; i++)
	for (k = i + m; k < N; k += m)
	  for (j = k; (j > i) && (a[j] < a[j - m]); j -= m)
	    {
	      swap (&(a[j]), &(a[j - m]));
	      dump_array (a);
	    }
    }
  while (m != 1);
 
  return 0;
}
 
/*
Local Variables:
mode: C
c-file-style: "gnu"
End:
*/