Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Description

I think many many people have seen this youtube video "15 Sorting Algorithms in 6 Minutes"
When I saw it, I decided: "I can do that better" and I tried to get things done with the tools at my disposal back then. Windows Forms and C#. I added a functionality to allow the pausing of sorting in any point of time. Therefore I reasoned, my algoritms need to move step by step, and Implemented accordingly.

Since then much has changed and yesterday I revisited my code from then, and it was gruesome.

Not just bad, but horrible. So i went ahead and refactored what I could, removed superfluous stuff, decoupled implementations and algorithms, renamed methods to be more C#-ish, and realized, I have become a -programmer by heart.

My method names got camelCased, there's no properties, and my Interface wasn't prefixed with I at the start.

Well, that aside, I finally arrived at something, where I am facing difficulties reducing the coupling. Where I am unsure what the best practice is, so here goes.

Code

Windows Forms oh how I love it, here come the FormDesigner.cs and the Form.cs ;)

namespace SortVisualizations
{
    partial class MainWindow
    {
        /// <summary>
        /// Erforderliche Designervariable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Verwendete Ressourcen bereinigen.
        /// </summary>
        /// <param name="disposing">True, wenn verwaltete Ressourcen gelöscht werden sollen; andernfalls False.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Vom Windows Form-Designer generierter Code

        /// <summary>
        /// Erforderliche Methode für die Designerunterstützung.
        /// Der Inhalt der Methode darf nicht mit dem Code-Editor geändert werden.
        /// </summary>
        private void InitializeComponent()
        {
            this.components = new System.ComponentModel.Container();
            this.triggerExit = new System.Windows.Forms.Button();
            this.clock = new System.Windows.Forms.Timer(this.components);
            this.triggerFill = new System.Windows.Forms.Button();
            this.inputArrayLength = new System.Windows.Forms.NumericUpDown();
            this.triggerToggleSorting = new System.Windows.Forms.Button();
            this.dropDownSortAlgorithms = new System.Windows.Forms.ComboBox();
            this.labelInputArrayLength = new System.Windows.Forms.Label();
            this.labelDropDownAlgorithms = new System.Windows.Forms.Label();
            this.paintArea = new System.Windows.Forms.Panel();
            ((System.ComponentModel.ISupportInitialize)(this.inputArrayLength)).BeginInit();
            this.SuspendLayout();
            // 
            // triggerExit
            // 
            this.triggerExit.Cursor = System.Windows.Forms.Cursors.Default;
            this.triggerExit.Location = new System.Drawing.Point(981, 603);
            this.triggerExit.Name = "triggerExit";
            this.triggerExit.Size = new System.Drawing.Size(188, 82);
            this.triggerExit.TabIndex = 0;
            this.triggerExit.Text = "Beenden";
            this.triggerExit.UseVisualStyleBackColor = true;
            this.triggerExit.Click += new System.EventHandler(this.triggerExit_Click);
            // 
            // clock
            // 
            this.clock.Interval = 10;
            this.clock.Tick += new System.EventHandler(this.clock_Tick);
            // 
            // triggerFill
            // 
            this.triggerFill.Location = new System.Drawing.Point(981, 90);
            this.triggerFill.Name = "triggerFill";
            this.triggerFill.Size = new System.Drawing.Size(188, 74);
            this.triggerFill.TabIndex = 2;
            this.triggerFill.Text = "Array befuellen";
            this.triggerFill.UseVisualStyleBackColor = true;
            this.triggerFill.Click += new System.EventHandler(this.triggerFill_Click);
            // 
            // inputArrayLength
            // 
            this.inputArrayLength.Increment = new decimal(new int[] {
            10,
            0,
            0,
            0});
            this.inputArrayLength.Location = new System.Drawing.Point(981, 47);
            this.inputArrayLength.Maximum = new decimal(new int[] {
            10000,
            0,
            0,
            0});
            this.inputArrayLength.Name = "inputArrayLength";
            this.inputArrayLength.Size = new System.Drawing.Size(187, 20);
            this.inputArrayLength.TabIndex = 3;
            this.inputArrayLength.TextAlign = System.Windows.Forms.HorizontalAlignment.Center;
            this.inputArrayLength.Value = new decimal(new int[] {
            10,
            0,
            0,
            0});
            this.inputArrayLength.ValueChanged += new System.EventHandler(this.ArrayLengthChange);
            // 
            // triggerToggleSorting
            // 
            this.triggerToggleSorting.Cursor = System.Windows.Forms.Cursors.Default;
            this.triggerToggleSorting.Location = new System.Drawing.Point(981, 499);
            this.triggerToggleSorting.Name = "triggerToggleSorting";
            this.triggerToggleSorting.Size = new System.Drawing.Size(188, 82);
            this.triggerToggleSorting.TabIndex = 5;
            this.triggerToggleSorting.Text = "Sortiere";
            this.triggerToggleSorting.UseVisualStyleBackColor = true;
            this.triggerToggleSorting.Click += new System.EventHandler(this.triggerToggleSorting_Click);
            // 
            // dropDownSortAlgorithms
            // 
            this.dropDownSortAlgorithms.AllowDrop = true;
            this.dropDownSortAlgorithms.FormattingEnabled = true;
            this.dropDownSortAlgorithms.Location = new System.Drawing.Point(980, 472);
            this.dropDownSortAlgorithms.Name = "dropDownSortAlgorithms";
            this.dropDownSortAlgorithms.Size = new System.Drawing.Size(189, 21);
            this.dropDownSortAlgorithms.TabIndex = 6;
            // 
            // labelInputArrayLength
            // 
            this.labelInputArrayLength.AutoSize = true;
            this.labelInputArrayLength.Location = new System.Drawing.Point(981, 12);
            this.labelInputArrayLength.Name = "labelInputArrayLength";
            this.labelInputArrayLength.Size = new System.Drawing.Size(185, 13);
            this.labelInputArrayLength.TabIndex = 4;
            this.labelInputArrayLength.Text = "Arraygröße des zu sortierenden Arrays";
            // 
            // labelDropDownAlgorithms
            // 
            this.labelDropDownAlgorithms.AutoSize = true;
            this.labelDropDownAlgorithms.Location = new System.Drawing.Point(981, 437);
            this.labelDropDownAlgorithms.Name = "labelDropDownAlgorithms";
            this.labelDropDownAlgorithms.Size = new System.Drawing.Size(170, 13);
            this.labelDropDownAlgorithms.TabIndex = 7;
            this.labelDropDownAlgorithms.Text = "Anzuwendender Sortieralgorithmus";
            // 
            // paintArea
            // 
            this.paintArea.BackColor = System.Drawing.Color.White;
            this.paintArea.Location = new System.Drawing.Point(13, 13);
            this.paintArea.Name = "paintArea";
            this.paintArea.Size = new System.Drawing.Size(946, 672);
            this.paintArea.TabIndex = 8;
            // 
            // MainWindow
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(1181, 697);
            this.ControlBox = false;
            this.Controls.Add(this.paintArea);
            this.Controls.Add(this.labelDropDownAlgorithms);
            this.Controls.Add(this.dropDownSortAlgorithms);
            this.Controls.Add(this.triggerToggleSorting);
            this.Controls.Add(this.labelInputArrayLength);
            this.Controls.Add(this.inputArrayLength);
            this.Controls.Add(this.triggerFill);
            this.Controls.Add(this.triggerExit);
            this.MaximizeBox = false;
            this.MinimizeBox = false;
            this.Name = "MainWindow";
            this.ShowIcon = false;
            this.Text = "Sortieralgorithmen Visualisiert";
            ((System.ComponentModel.ISupportInitialize)(this.inputArrayLength)).EndInit();
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.Button triggerExit;
        private System.Windows.Forms.Timer clock;
        private System.Windows.Forms.Button triggerFill;
        private System.Windows.Forms.NumericUpDown inputArrayLength;
        private System.Windows.Forms.Button triggerToggleSorting;
        private System.Windows.Forms.ComboBox dropDownSortAlgorithms;
        private System.Windows.Forms.Label labelInputArrayLength;
        private System.Windows.Forms.Label labelDropDownAlgorithms;
        public System.Windows.Forms.Panel paintArea;
    }
}

namespace SortVisualizations
{
    public partial class MainWindow : Form
    {
        private const int STANDARD_ARRAY_SIZE = 10;
        private static ImplementationFactory algos = ImplementationFactory.Instance();

        private bool isSorting;
        private int[] arrayToSort;
        private IAlgoImplementation stepAlgorithm;

        private Stopwatch sw;

        public MainWindow()
        {
            InitializeComponent();
            init();
        }

        private void init()
        {
            this.arrayToSort = new int[STANDARD_ARRAY_SIZE];
            dropDownSortAlgorithms.SelectedValueChanged += selectAlgo;

            IEnumerator algoEnumerator = Enum.GetValues(typeof(Algorithm)).GetEnumerator();
            while (algoEnumerator.MoveNext())
            {
                dropDownSortAlgorithms.Items.Add(algoEnumerator.Current);
            }
            SelectAlgo(Algorithm.BUBBLESORT);

            clock.Start();
            sw = new Stopwatch();

            generateRandomArrayElements();
            isSorting = false;
        }

        private void getStepAlgorithm(Algorithm selected)
        {
            this.stepAlgorithm = algos.GetAlgoImplementationFor(selected, this, ref arrayToSort);
        }

        internal void SelectAlgo(Algorithm algo)
        {
            dropDownSortAlgorithms.SelectedItem = algo;
            getStepAlgorithm(algo);
        }

        public void SwapIndexes(int i, int p, ref int[] arrayToSort)
        {
            int temp;

            Control panelI = this.paintArea.Controls[i];
            Control panelP = this.paintArea.Controls[p];

            temp = arrayToSort[p];
            arrayToSort[p] = arrayToSort[i];
            arrayToSort[i] = temp;

            panelI.Height = (int)(paintArea.Height * arrayToSort[i] / arrayToSort.Length);
            panelP.Height = (int)(paintArea.Height * arrayToSort[p] / arrayToSort.Length);

            panelI.Top = paintArea.Height - panelI.Height;
            panelP.Top = paintArea.Height - panelP.Height;
        }


        public static void CreateAlert(string p)
        {
            MessageBox.Show(p);
        }

        private void ArrayLengthChange(object sender, EventArgs e)
        {
            NumericUpDown uiArrayItemCountUpDown = sender as NumericUpDown;
            if ((int)uiArrayItemCountUpDown.Value <= 0){
                CreateAlert("Die Anzahl der Elemente kann nicht 0 oder weniger sein");
                uiArrayItemCountUpDown.Value = 1;
            }
            else
            {
                this.arrayToSort = new int[(int)uiArrayItemCountUpDown.Value];
                generateRandomArrayElements();
            }
        }

        private void generateRandomArrayElements()
        {
            Random rnd = new Random();

            for (int i = 0; i < arrayToSort.Length; i++)
            {
                arrayToSort[i] = rnd.Next(1, arrayToSort.Length + 1);
            }

            selectAlgo(dropDownSortAlgorithms, null);
            uiInitializePaintArea();
            sw.Stop();
            sw.Reset();
        }

        #region event handlers

        private void selectAlgo(object sender, EventArgs e)
        {
            ComboBox uiComboBox = sender as ComboBox;
            getStepAlgorithm((Algorithm)uiComboBox.SelectedItem);
        }

        private void clock_Tick(object sender, EventArgs e)
        {
            if (isSorting)
            {
                stepAlgorithm.Step();
                if (stepAlgorithm.IsFinished())
                {
                    triggerToggleSorting_Click(null, null);
                    CreateAlert(String.Format("Alle Elemente sind sortiert\nDauer: {0}", sw.Elapsed));
                }
            }
        }

        private void triggerToggleSorting_Click(object sender, EventArgs e)
        {
            isSorting = !isSorting;
            if (isSorting)
            {
                triggerToggleSorting.Text = "Pause";
                sw.Start();
            }
            else
            {
                triggerToggleSorting.Text = "Sortiere";
                sw.Stop();
            }
        }

        private void triggerExit_Click(object sender, EventArgs e)
        {
            Application.Exit();
        }

        private void triggerFill_Click(object sender, EventArgs e)
        {
            generateRandomArrayElements();
        }
        #endregion

        #region ui modification methods
        private void uiInitializePaintArea()
        {
            if (arrayToSort.Length + 1 != paintArea.Controls.Count)
                uiCreateRepresentingPanels();

            for (int i = 0; i < arrayToSort.Length; i++)
            {
                //Should be able to match paintArea.Items[i] with arrayToSort[i]
                Control rectangle = paintArea.Controls.Find(String.Format("_{0}", i), true).First();

                //We do not need to adjust the width, as it always stays the same.
                rectangle.Height = (int)(paintArea.Height * arrayToSort[i] / arrayToSort.Length);
                rectangle.Top = (paintArea.Height - rectangle.Height);
            }

            paintArea.Update();
            paintArea.PerformLayout();
        }

        private void uiCreateRepresentingPanels()
        {
            paintArea.Controls.Clear();

            // the width stays the same for all rectangles
            int width = (int)(paintArea.Width / arrayToSort.Length);

            if (width == 0)
                width = 1;

            for (int i = 0; i < arrayToSort.Length; i++)
            {
                Panel rectangle = new Panel();
                rectangle.Name = String.Format("_{0}", i);
                rectangle.Width = width;
                rectangle.Height = (int)(paintArea.Height * arrayToSort[i] / arrayToSort.Length);
                rectangle.Left = width * i;
                rectangle.Top = (paintArea.Height - rectangle.Height);

                rectangle.BackColor = Color.Green;

                paintArea.Controls.Add(rectangle);
            }
        }

        internal void uiAssumeSorted(int index)
        {
            this.paintArea.Controls[index].BackColor = Color.Blue;
        }

        public void uiDeclarePivot(int index)
        {
            this.paintArea.Controls[index].BackColor = Color.Red;
        }

        public void uiRemovePivot(int index)
        {
            this.paintArea.Controls[index].BackColor = Color.Green;
        }
        #endregion
    }
}

I tried to Hide my Algorithm implementations behind an interface, and use this Factory to instantiate them:

class ImplementationFactory
{
    private static ImplementationFactory _instance;
    private Dictionary<Algorithm, IAlgoImplementation> mapping = new Dictionary<Algorithm, IAlgoImplementation>();

    private ImplementationFactory()
    {
        mapping.Add(Algorithm.BUBBLESORT, new BubbleSort());
        mapping.Add(Algorithm.COCKTAILSHAKER, new Cocktailshaker());
    }

    public static ImplementationFactory Instance()
    {
        if (_instance == null)
            _instance = new ImplementationFactory();

        return _instance;
    }

    public IAlgoImplementation GetAlgoImplementationFor(Algorithm algo, MainWindow owner, ref int[] array)
    {
        IAlgoImplementation impl;
        if (!mapping.TryGetValue(algo, out impl))
        {
            MainWindow.CreateAlert("Falling back to default algorithm!");
            owner.SelectAlgo(Algorithm.BUBBLESORT);
            if (!mapping.TryGetValue(Algorithm.BUBBLESORT, out impl))
            {
                throw new NotSupportedException();
            }
        }

        impl.Initialize(owner, ref array);
        return impl;
    }
}

And A few things on the Algorithms:

public enum Algorithm
{
    BUBBLESORT, COCKTAILSHAKER
}

As well as the interface to unify them all:

interface IAlgoImplementation
{
    void Initialize(MainWindow owner, ref int[] array);
    void Step();
    bool IsFinished();
}

Additionally for full runnability, here's the Bubblesort Algorithm Implementation. The Implementations may be part of another review, but I'd prefer to leave them out of this one.

class BubbleSort : IAlgoImplementation
{
    private bool isFinished;
    private bool hasSwapped;

    private int current;
    private int assumeSortedFrom;

    private int[] array;

    private MainWindow owner;

    public BubbleSort()
    {

    }

    public void Initialize(MainWindow owner, ref int[] array)
    {
        this.isFinished = false;
        this.owner = owner;
        this.array = array;
        this.current = 0;
        this.assumeSortedFrom = array.Length;
    }

    public void Step()
    {
        owner.uiRemovePivot(current);
        if (current + 1 == assumeSortedFrom)
        {
            assumeSortedFrom = current;
            owner.uiAssumeSorted(current);
            current = 0;
            owner.uiDeclarePivot(current);
            if (!hasSwapped)
            {
                isFinished = true;
            }
            else
            {
                hasSwapped = false;
            }
        }
        else
        {
            if (array[current] > array[current + 1])
            {
                owner.SwapIndexes(current, current + 1, ref array);
                hasSwapped = true;
            }

            current++;
            owner.uiDeclarePivot(current);
        }
    }

    public bool IsFinished()
    {
        return isFinished;
    }
}

Questions / Notes:

A few things I want to talk about, before you do:

  1. Yes, that is hungarian notation there. I decided to prefix all UI-related methods, whereever reasonably possible with a ui. Please don't judge me on that.
  2. Constants. I know this code could still use the extraction of a few constants. (String messages, mainly). These are duly noted and scheduled for purging.
  3. Designer-Code and Comments. Well these are mostly german and auto-generated. I provided this mostly for the possibility of copying and then running it. If you want to rant, go on, but don't expect too many upvotes.

Especially concerned I am about:

  1. Responsibilites of Classes: Did I pack too much into the MainWindow.cs?
  2. Decoupling: I feel that this is all still waay to tightly coupled. How could I reduce that?
  3. Ref-Passing the array: I got the gut-feeling I tinker with that thing too often and in the wrong places.
  4. As always, everything else you want to mention ;)
share|improve this question

1 Answer 1

up vote 6 down vote accepted

Naming

Methodnames in C# should be PascalCase
Some examples from your sources

private void init()
private void getStepAlgorithm(Algorithm selected)
private void generateRandomArrayElements()
private void uiInitializePaintArea()

As I read clock I thought, why is he showing a clock for a algorithm. I needed to check the declaration hidden inside the designer file to see it is a timer.
You should just name it timer.

private void getStepAlgorithm(Algorithm selected)
{
    this.stepAlgorithm = algos.GetAlgoImplementationFor(selected, this, ref arrayToSort);
}

Reading the methodname getStepAlgorithm let a reader assume that he is getting an algorithm but what the code does is assigning an algorithm to a class field. So a better name would be AssignAlgorithm

Decoupling

Communication between parent, here MainWindow, and child, here an inplementation of the IAlgoImplementation interface, should be by calling methods and setting of properties. From child to parent it should be done by events. The implementation of the IAlgoImplementation should know nothing of its parent. Also the factory should know nothing of the MainWindow.

 public void SwapIndexes(int i, int p, ref int[] arrayToSort)

This method of the MainWindow class is violating separations of concerns, because it is called from the BubbleSort implementation of the IAlgoImplementation interface.

Refactoring
First we should change the name of interface IAlgoImplementation to interface ISortAlgorithm to make the name more meaningful. The same we do to the void Step() method and rename it to void PerformSortStep(). We add a property to hold the array to be sorted and add events for performing a sortstep, swapping values and for finishing the sorting.

interface ISortAlgorithm
{
    int[] ArrayToSort { set; }

    void PerformSortStep();

    event EventHandler<SortStepPerformedEventArgs> SortStepPerformed;
    event EventHandler<SwapPerformedEventArgs> SwapPerformed;
    event EventHandler SortFinished;
}

public class SortStepPerformedEventArgs : EventArgs
{
    public int CurrentIndex { get; private set; }
    public PointOfStep StepPoint { get; private set; }
    public SortStepPerformedEventArgs(int currentIndex, PointOfStep stepPoint)
    {
        CurrentIndex = currentIndex;
        StepPoint = stepPoint;
    }
}

public enum PointOfStep
{
    BeforeStep, ReAssignedAssumeSorted, CurrentStep
}

public class SwapPerformedEventArgs : EventArgs
{
    public int FirstIndex { get; private set; }
    public int SecondIndex { get; private set; }
    public int FirstValue { get; private set; }
    public int SecondValue { get; private set; }
    public int LengthOfArrayToSort { get; set; }

    public SwapPerformedEventArgs(int firstIndex, int secondIndex, 
        int firstValue, int secondValue, 
        int lengthOfArrayToSort)
    {
        FirstIndex = firstIndex;
        SecondIndex = secondIndex;
        FirstValue = firstValue;
        SecondValue = secondValue;
        LengthOfArrayToSort = lengthOfArrayToSort;
    }

}

Now let us take a look at the BubbleSort class. As you didn't implement the interface explicit, I added a private get to the ArrayToSort property.

public class BubbleSort : ISortAlgorithm
{
    private int current;
    private int assumeSortedFrom;
    private bool hasSwapped;

    private int[] arrayToSort = null;
    public int[] ArrayToSort
    {
        set {
            if (value == null)
            {
                throw new ArgumentNullException("ArrayToSort", "The array to be sorted can't be null");
            }
            arrayToSort = value;
            InitializeSorting();

        }
        private get { return arrayToSort; }
    }

    private void InitializeSorting()
    {
        current = 0;
        assumeSortedFrom = ArrayToSort.Length;
        hasSwapped = false;

    }

    public void PerformSortStep()
    {

        OnSortStepPerformed(current, PointOfStep.BeforeStep);

        if (current + 1 == assumeSortedFrom)
        {
            assumeSortedFrom = current;
            OnSortStepPerformed(current, PointOfStep.ReAssignedAssumeSorted);

            current = 0;
            OnSortStepPerformed(current, PointOfStep.CurrentStep);

            if (!hasSwapped)
            {
                OnSortFinished();
            }
            else
            {
                hasSwapped = false;
            }
        }
        else
        {
            if (ArrayToSort[current] > ArrayToSort[current + 1])
            {
                SwapIndexes(current, current + 1);
                hasSwapped = true;
            }

            current++;
            OnSortStepPerformed(current, PointOfStep.CurrentStep);
        }
    }

    private void SwapIndexes(int currentIndex, int nextIndex)
    {
        int temp;

        temp = arrayToSort[nextIndex];
        ArrayToSort[nextIndex] = ArrayToSort[currentIndex];
        ArrayToSort[currentIndex] = temp;

        SwapPerformedEventArgs e = new SwapPerformedEventArgs(currentIndex, nextIndex,
            ArrayToSort[currentIndex], ArrayToSort[nextIndex], 
            ArrayToSort.Length);

        OnSwapPerformed(e);

    }

    object objectLock = new Object();
    private EventHandler<SortStepPerformedEventArgs> sortStepPerformed;
    public event EventHandler<SortStepPerformedEventArgs> SortStepPerformed
    {
        add
        {
            lock (objectLock)
            {
                sortStepPerformed += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                sortStepPerformed -= value;
            }
        }
    }

    private void OnSortStepPerformed(int currentIndex, PointOfStep pointOfStep)
    {
        OnSortStepPerformed(new SortStepPerformedEventArgs(currentIndex, pointOfStep));
    }

    private void OnSortStepPerformed(SortStepPerformedEventArgs e)
    {
        lock (objectLock)
        {
            if (sortStepPerformed != null)
            {
                sortStepPerformed(this, e);
            }
        }
    }

    private EventHandler<SwapPerformedEventArgs> swapPerformed;
    public event EventHandler<SwapPerformedEventArgs> SwapPerformed
    {
        add
        {
            lock (objectLock)
            {
                swapPerformed += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                swapPerformed -= value;
            }
        }
    }

    private void OnSwapPerformed(SwapPerformedEventArgs e)
    {
        lock (objectLock)
        {
            if (swapPerformed != null)
            {
                swapPerformed(this, e);
            }
        }
    }

    private event EventHandler sortFinished;
    public event EventHandler SortFinished
    {
        add
        {
            lock (objectLock)
            {
                sortFinished += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                sortFinished -= value;
            }
        }
    }

    private void OnSortFinished()
    {
        lock (objectLock)
        {
            if (sortFinished != null)
            {
                sortFinished(this, new EventArgs());
            }
        }
    }
}  

No reference to any calling owner is needed anymore.

As the factory class also has been coupled with the MainWindow we need to decouple this also.

    public IAlgoImplementation GetAlgoImplementationFor(Algorithm algo, MainWindow owner, ref int[] array)
    {
        IAlgoImplementation impl;
        if (!mapping.TryGetValue(algo, out impl))
        {
            MainWindow.CreateAlert("Falling back to default algorithm!");
            owner.SelectAlgo(Algorithm.BUBBLESORT);
            if (!mapping.TryGetValue(Algorithm.BUBBLESORT, out impl))
            {
                throw new NotSupportedException();
            }
        }
        impl.Initialize(owner, ref array);
        return impl;
    }  

First we rename the class to SortAlgorithmFactory. Now we add a property IEnumerator ImplementedAlgorithms to return the algorithms which the factory can create.

class SortAlgorithmFactory
{

    private static SortAlgorithmFactory _instance;
    private Dictionary<Algorithm, ISortAlgorithm> mapping = new Dictionary<Algorithm, ISortAlgorithm>();

    public IEnumerator ImplementedAlgorithms
    {
        get { return mapping.Keys.GetEnumerator(); }
    }

    private SortAlgorithmFactory()
    {
        mapping.Add(Algorithm.BUBBLESORT, new BubbleSort());
        mapping.Add(Algorithm.COCKTAILSHAKER, new Cocktailshaker());
    }

    public static SortAlgorithmFactory Instance()
    {
        if (_instance == null)
            _instance = new SortAlgorithmFactory();

        return _instance;
    }

    public ISortAlgorithm GetAlgoImplementationFor(Algorithm algo, int[] array)
    {
        ISortAlgorithm sortAlgorithm = mapping[algo];
        sortAlgorithm.ArrayToSort = array;

        return sortAlgorithm;
    }
}  

Now there is no reference to the MainWindow anymore. Also by using the ImplementedAlgorithms property, we remove the possibility of an infinite loop for the case someone commented this mapping.Add(Algorithm.BUBBLESORT, new BubbleSort());.

Let us now move to the MainWindow.

private void generateRandomArrayElements()
{
    Random rnd = new Random();

    for (int i = 0; i < arrayToSort.Length; i++)
    {
        arrayToSort[i] = rnd.Next(1, arrayToSort.Length + 1);
    }

    selectAlgo(dropDownSortAlgorithms, null);
    uiInitializePaintArea();
    sw.Stop();
    sw.Reset();
}  

This method does a lot of things, not only generating random array elements, but also selecting an algorithm ... so, let us refactor the method and the 3 usages of this method

    private Random rnd = new Random();
    private void GenerateRandomArrayElements()
    {
        for (int i = 0; i < arrayToSort.Length; i++)
        {
            arrayToSort[i] = rnd.Next(1, arrayToSort.Length + 1);
        }

        sw.Stop();
        sw.Reset();

    }

    private void ArrayLengthChange(object sender, EventArgs e)
    {
        NumericUpDown uiArrayItemCountUpDown = sender as NumericUpDown;
        if ((int)uiArrayItemCountUpDown.Value <= 0)
        {
            ShowAlert("Die Anzahl der Elemente kann nicht 0 oder weniger sein");
            uiArrayItemCountUpDown.Value = 1;
        }
        else
        {
            this.arrayToSort = new int[(int)uiArrayItemCountUpDown.Value];
            GenerateRandomArrayElements();
            AssignArrayToSortAlgorithm();
            uiInitializePaintArea();
        }
    }  

    private void triggerFill_Click(object sender, EventArgs e)
    {
        isSorting = false;
        GenerateRandomArrayElements();
        AssignArrayToSortAlgorithm();
        uiInitializePaintArea();
    }  

And last but not least the former init() method

    private void Initialize()
    {
        this.arrayToSort = new int[STANDARD_ARRAY_SIZE];

        IEnumerator algoEnumerator = algorithmFactory.ImplementedAlgorithms;
        while (algoEnumerator.MoveNext())
        {
            dropDownSortAlgorithms.Items.Add(algoEnumerator.Current);
        }

        dropDownSortAlgorithms.SelectedValueChanged += SelectAlgorithm;

        StepTimer.Start();
        sw = new Stopwatch();

        GenerateRandomArrayElements();

        SelectAlgorithm(Algorithm.BUBBLESORT);

        uiInitializePaintArea();

        isSorting = false;
    }

The complete MainWindow class (note I have also renamed clock to StepTimer)

public partial class MainWindow : Form
{
    private const int STANDARD_ARRAY_SIZE = 10;
    private static SortAlgorithmFactory algorithmFactory = SortAlgorithmFactory.Instance();
    private bool isSorting;
    private int[] arrayToSort;
    private ISortAlgorithm sortAlgorithm;

    private Stopwatch sw;

    public MainWindow()
    {
        InitializeComponent();
        Initialize();
    }

    private void Initialize()
    {
        this.arrayToSort = new int[STANDARD_ARRAY_SIZE];

        IEnumerator algoEnumerator = algorithmFactory.ImplementedAlgorithms;
        while (algoEnumerator.MoveNext())
        {
            dropDownSortAlgorithms.Items.Add(algoEnumerator.Current);
        }

        dropDownSortAlgorithms.SelectedValueChanged += SelectAlgorithm;

        StepTimer.Start();
        sw = new Stopwatch();

        GenerateRandomArrayElements();

        SelectAlgorithm(Algorithm.BUBBLESORT);

        uiInitializePaintArea();

        isSorting = false;
    }

    private void AssignStepAlgorithm(Algorithm selected)
    {
        RemoveSortAlgorithmEventHandler();

        this.sortAlgorithm = algorithmFactory.GetAlgoImplementationFor(selected, arrayToSort);

        AddSortAlgorithmEventHandler();
    }

    private void AssignArrayToSortAlgorithm()
    {
        sortAlgorithm.ArrayToSort = arrayToSort;
    }

    private void RemoveSortAlgorithmEventHandler()
    {
        if (this.sortAlgorithm == null) { return; }
        this.sortAlgorithm.SortFinished -= new EventHandler(StepAlgorithm_SortFinished);
        this.sortAlgorithm.SortStepPerformed -= new EventHandler<SortStepPerformedEventArgs>
            (StepAlgorithm_SortStepPerformed);
        this.sortAlgorithm.SwapPerformed -= new EventHandler<SwapPerformedEventArgs>(StepAlgorithm_SwapPerformed);
    }

    private void AddSortAlgorithmEventHandler()
    {
        this.sortAlgorithm.SortFinished += new EventHandler(StepAlgorithm_SortFinished);
        this.sortAlgorithm.SortStepPerformed += new EventHandler<SortStepPerformedEventArgs>
            (StepAlgorithm_SortStepPerformed);
        this.sortAlgorithm.SwapPerformed += new EventHandler<SwapPerformedEventArgs>(StepAlgorithm_SwapPerformed);
    }

    void StepAlgorithm_SwapPerformed(object sender, SwapPerformedEventArgs e)
    {

        int arrayLength = e.LengthOfArrayToSort;

        Control panelI = this.paintArea.Controls[e.FirstIndex];
        Control panelP = this.paintArea.Controls[e.SecondIndex];

        panelI.Height = (int)(paintArea.Height * e.FirstValue / arrayLength);
        panelP.Height = (int)(paintArea.Height * e.SecondValue / arrayLength);

        panelI.Top = paintArea.Height - panelI.Height;
        panelP.Top = paintArea.Height - panelP.Height;

    }

    void StepAlgorithm_SortStepPerformed(object sender, SortStepPerformedEventArgs e)
    {
        switch (e.StepPoint)
        {
            case PointOfStep.BeforeStep:
                uiRemovePivot(e.CurrentIndex);
                break;

            case PointOfStep.ReAssignedAssumeSorted:
                uiAssumeSorted(e.CurrentIndex);
                break;

            case PointOfStep.CurrentStep:
                uiDeclarePivot(e.CurrentIndex);
                break;
        }

    }

    void StepAlgorithm_SortFinished(object sender, EventArgs e)
    {
        triggerToggleSorting_Click(null, null);
        ShowAlert(String.Format("Alle Elemente sind sortiert\nDauer: {0}", sw.Elapsed));
    }

    private void SelectAlgorithm(Algorithm algorithm)
    {
        dropDownSortAlgorithms.SelectedItem = algorithm;
    }

    private void ShowAlert(string p)
    {
        MessageBox.Show(p);
    }

    private void ArrayLengthChange(object sender, EventArgs e)
    {
        NumericUpDown uiArrayItemCountUpDown = sender as NumericUpDown;
        if ((int)uiArrayItemCountUpDown.Value <= 0)
        {
            ShowAlert("Die Anzahl der Elemente kann nicht 0 oder weniger sein");
            uiArrayItemCountUpDown.Value = 1;
        }
        else
        {
            this.arrayToSort = new int[(int)uiArrayItemCountUpDown.Value];
            GenerateRandomArrayElements();
            AssignArrayToSortAlgorithm();
            uiInitializePaintArea();
        }
    }

    private Random rnd = new Random();
    private void GenerateRandomArrayElements()
    {
        for (int i = 0; i < arrayToSort.Length; i++)
        {
            arrayToSort[i] = rnd.Next(1, arrayToSort.Length + 1);
        }

        sw.Stop();
        sw.Reset();

    }

    #region event handlers

    private void SelectAlgorithm(object sender, EventArgs e)
    {
        ComboBox uiComboBox = sender as ComboBox;
        AssignStepAlgorithm((Algorithm)uiComboBox.SelectedItem);
    }

    private void StepTimer_Tick(object sender, EventArgs e)
    {
        if (isSorting)
        {
            sortAlgorithm.PerformSortStep();
        }
    }

    private void triggerToggleSorting_Click(object sender, EventArgs e)
    {
        isSorting = !isSorting;
        if (isSorting)
        {
            triggerToggleSorting.Text = "Pause";
            sw.Start();
        }
        else
        {
            triggerToggleSorting.Text = "Sortiere";
            sw.Stop();
        }
    }

    private void triggerExit_Click(object sender, EventArgs e)
    {
        Application.Exit();
    }

    private void triggerFill_Click(object sender, EventArgs e)
    {
        isSorting = false;
        GenerateRandomArrayElements();
        AssignArrayToSortAlgorithm();
        uiInitializePaintArea();
    }
    #endregion

    #region ui modification methods
    private void uiInitializePaintArea()
    {
        if (arrayToSort.Length + 1 != paintArea.Controls.Count)
        {
            uiCreateRepresentingPanels();
        }

        for (int i = 0; i < arrayToSort.Length; i++)
        {
            //Should be able to match paintArea.Items[i] with arrayToSort[i]
            Control rectangle = paintArea.Controls.Find(String.Format("_{0}", i), true).First();

            //We do not need to adjust the width, as it always stays the same.
            rectangle.Height = (int)(paintArea.Height * arrayToSort[i] / arrayToSort.Length);
            rectangle.Top = (paintArea.Height - rectangle.Height);
        }

        paintArea.Update();
        paintArea.PerformLayout();
    }

    private void uiCreateRepresentingPanels()
    {
        paintArea.Controls.Clear();

        // the width stays the same for all rectangles
        int width = (int)(paintArea.Width / arrayToSort.Length);

        if (width == 0)
            width = 1;

        for (int i = 0; i < arrayToSort.Length; i++)
        {
            Panel rectangle = new Panel();
            rectangle.Name = String.Format("_{0}", i);
            rectangle.Width = width;
            rectangle.Height = (int)(paintArea.Height * arrayToSort[i] / arrayToSort.Length);
            rectangle.Left = width * i;
            rectangle.Top = (paintArea.Height - rectangle.Height);

            rectangle.BackColor = Color.Green;

            paintArea.Controls.Add(rectangle);
        }
    }

    private void uiAssumeSorted(int index)
    {
        this.paintArea.Controls[index].BackColor = Color.Blue;
    }

    private void uiDeclarePivot(int index)
    {
        this.paintArea.Controls[index].BackColor = Color.Red;
    }

    private void uiRemovePivot(int index)
    {
        this.paintArea.Controls[index].BackColor = Color.Green;
    }
    #endregion
}

Using an abstract class can lead towards less code, if one want to implement the ISortAlgorithm explicit.

public abstract class SortAlgorithm : ISortAlgorithm
{
    protected int current;
    protected int assumeSortedFrom;
    protected bool hasSwapped;
    private int[] arrayToSort = null;
    protected int[] ArrayToSort { get { return arrayToSort; } }
    int[] ISortAlgorithm.ArrayToSort
    {
        set
        {
            if (value == null)
            {
                throw new ArgumentNullException("ArrayToSort", "The array to be sorted can't be null");
            }
            arrayToSort = value;
            InitializeSorting();

        }
    }
    private void InitializeSorting()
    {
        current = 0;
        assumeSortedFrom = ArrayToSort.Length;
        hasSwapped = false;

    }

    void ISortAlgorithm.PerformSortStep()
    {
        this.PerformSortStep();
    }

    protected abstract void PerformSortStep();
    protected abstract void SwapIndexes(int currentIndex, int nextIndex);

    object objectLock = new Object();
    private EventHandler<SortStepPerformedEventArgs> sortStepPerformed;
    event EventHandler<SortStepPerformedEventArgs> ISortAlgorithm.SortStepPerformed
    {
        add
        {
            lock (objectLock)
            {
                sortStepPerformed += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                sortStepPerformed -= value;
            }
        }
    }
    protected void OnSortStepPerformed(int currentIndex, PointOfStep pointOfStep)
    {
        OnSortStepPerformed(new SortStepPerformedEventArgs(currentIndex, pointOfStep));
    }
    protected void OnSortStepPerformed(SortStepPerformedEventArgs e)
    {
        lock (objectLock)
        {
            if (sortStepPerformed != null)
            {
                sortStepPerformed(this, e);
            }
        }
    }
    private EventHandler<SwapPerformedEventArgs> swapPerformed;
    event EventHandler<SwapPerformedEventArgs> ISortAlgorithm.SwapPerformed
    {
        add
        {
            lock (objectLock)
            {
                swapPerformed += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                swapPerformed -= value;
            }
        }
    }
    protected void OnSwapPerformed(SwapPerformedEventArgs e)
    {
        lock (objectLock)
        {
            if (swapPerformed != null)
            {
                swapPerformed(this, e);
            }
        }
    }
    private event EventHandler sortFinished;
    event EventHandler ISortAlgorithm.SortFinished
    {
        add
        {
            lock (objectLock)
            {
                sortFinished += value;
            }
        }
        remove
        {
            lock (objectLock)
            {
                sortFinished -= value;
            }
        }
    }
    protected void OnSortFinished()
    {
        lock (objectLock)
        {
            if (sortFinished != null)
            {
                sortFinished(this, new EventArgs());
            }
        }
    }
}  

public class BubbleSort:SortAlgorithm
{
    protected override void PerformSortStep()
    {
        OnSortStepPerformed(current, PointOfStep.BeforeStep);

        if (current + 1 == assumeSortedFrom)
        {
            assumeSortedFrom = current;
            OnSortStepPerformed(current, PointOfStep.ReAssignedAssumeSorted);

            current = 0;
            OnSortStepPerformed(current, PointOfStep.CurrentStep);

            if (!hasSwapped)
            {
                OnSortFinished();
            }
            else
            {
                hasSwapped = false;
            }
        }
        else
        {
            if (ArrayToSort[current] > ArrayToSort[current + 1])
            {
                SwapIndexes(current, current + 1);
                hasSwapped = true;
            }

            current++;
            OnSortStepPerformed(current, PointOfStep.CurrentStep);
        }
    }
    protected override void SwapIndexes(int currentIndex, int nextIndex)
    {
        int temp;

        temp = ArrayToSort[nextIndex];
        ArrayToSort[nextIndex] = ArrayToSort[currentIndex];
        ArrayToSort[currentIndex] = temp;

        SwapPerformedEventArgs e = new SwapPerformedEventArgs(currentIndex, nextIndex,
            ArrayToSort[currentIndex], ArrayToSort[nextIndex],
            ArrayToSort.Length);

        OnSwapPerformed(e);

    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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