5
\$\begingroup\$

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;
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ All of those sound inefficient to me; 34 seconds to sort 1000 integers might be reasonable for hardware made in 1984. \$\endgroup\$ – oals Nov 2 '14 at 21:30
  • \$\begingroup\$ That is true. I am wondering if the fact that the function are all generic has anything to do with it the time \$\endgroup\$ – DacorieS Nov 2 '14 at 21:33
  • 1
    \$\begingroup\$ Your numbers seem very off. Since the algorithms are O(N^2), they should take less than a second to sort 1000 integers (1,000,000 iterations). Taking 34 seconds makes it sound as if you were sorting on the order of 100,000 integers (10,000,000,000 iterations). Your code probably seems inefficient because you are printing to standard out in the inner loop. Try timing your code after taking out all the printing. \$\endgroup\$ – irrelephant Nov 2 '14 at 22:42
  • \$\begingroup\$ @irrelephant if that is the case then is there anything you see wrong with my implementation? i tested it with array of 100 integers ,it take's less than one second to run. \$\endgroup\$ – DacorieS Nov 2 '14 at 22:55
  • \$\begingroup\$ See the edit -- have you taken out the Show()s before timing? \$\endgroup\$ – irrelephant Nov 2 '14 at 22:56
5
\$\begingroup\$

Show() is probably slowing it down. It transforms your implementation into \$O(n^3)\$ 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.

\$\endgroup\$
  • \$\begingroup\$ Very detail explanation. Show is increasing the runtime \$\endgroup\$ – DacorieS Nov 3 '14 at 15:19
4
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ I just made the suggested edits. The problem was the show, it increase the complexity drastically.i get the same result as you when i rerun it. The shell sort has a better run time than the other two algorithm \$\endgroup\$ – DacorieS Nov 3 '14 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.