Problem

I am testing various sorting algorithms. Right now I am testing shell sort, insertion sort and selection sort. I ran all three algorithms on a randomly-generated list of 1000 integers. The selection sort took 41 seconds, insertion sort took 34 seconds and shell sort sort took over 3 minutes. What can I do to improve my implementation?

```
public class SortAlgorithm
{
public void InsertionSort<T>(T[] a) where T : IComparable
{
for (int i = 0; i < a.Length; i++)
{ // Exchange a[i] with smallest entry in a[i+1...N).
int min = i; // index of minimal entr.
for (int j = i + 1; j < a.Length; j++)
{
if (Less(a[j], a[min]))
{
min = j;
}
else if (a.Length < j + 1)
{
a[j + 1] = a[j];
a[j] = a[min];
}
}
Show(a);
Exch(a, i, min);
}
}
public void ShellSort<T>(T[] a) where T : IComparable
{ // Sort a[] into increasing order.
int N = a.Length;
int h = 1;
while (h < N / 3)
{
h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ..
}
while (h >= 1)
{ // h-sort the array.
for (int i = h; i < N; i++)
{ // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
for (int j = i; j >= h && Less(a[j], a[j - h]); j -= h)
Exch(a, j, j - h);
Show(a);
}
h = h / 3;
}
}
public void SelectionSort<T>(T[] a) where T : IComparable
{ // Sort a[] into increasing order.
int n = a.Length; // array length
for (int i = 0; i < n; i++)
{ // Exchange a[i] with smallest entry in a[i+1...N).
int min = i; // index of minimal entr.
for (int j = i + 1; j < n; j++)
if (Less(a[j], a[min])) min = j;
Exch(a, i, min);
Show(a);
}
}
private static void Exch<T>(T[] a, int i, int j) where T : IComparable
{
T t = a[i];
a[i] = a[j];
a[j] = t;
}
public void Show<T>(T[] a) where T : IComparable
{ // Print the array, on a single line.
foreach (T t in a)
{
Console.Write(t + " ");
}
Console.WriteLine();
}
private static bool Less(IComparable v, IComparable w)
{
return v.CompareTo(w) < 0;
}
public bool IsSorted(IComparable[] a)
{ // Test whether the array entries are in order.
for (int i = 1; i < a.Length; i++)
if (Less(a[i], a[i - 1])) return false;
return true;
}
}
```

Solution

`Show()`

is probably slowing it down. It transforms your implementation into O(n3)

and even worse increases the algorithm’s time by (n*[time taken to access and write to console stream]) in the last loop. Preparing your string and printing once to the console would increase the speed, even better, printing when the list is sorted. Requesting and using resources (e.g. streams) during an expensive operation will increase execution time. You are using `Console.Write`

<– probably accessing the raw stream would be even faster if needs be.

You should prefer the generic `IComparable<T>`

to `IComparable`

:

```
public static void InsertionSort<T>(T[] a) where T : IComparable<T>
public static void ShellSort<T>(T[] a) where T : IComparable<T>
public static void SelectionSort<T>(T[] a) where T : IComparable<T>
```

Note that we don’t need a constraint on `T`

for `Exch`

:

```
private static void Exch<T>(T[] a, int i, int j)
```

While we’re at it, `Swap`

or `Exchange`

would be a better name for `Exch`

.

We also don’t need a constraint for `Show`

, which can be written more simply as

```
public static void Show<T>(T[] a)
{
Console.WriteLine(string.Join(" ", a));
}
```

Finally, we have

```
private static bool Less<T>(T v, T w) where T : IComparable<T>
public static bool IsSorted<T>(T[] a) where T : IComparable<T>
```

On my machine, these changes reduced the running time of `ShellSort`

(*not* calling `Show`

) on an array of 1,000,000 random ints from ~2.6s to ~1s (Mono 3.10.0, Debug x86).