Least Squares Fitting--Exponential

Let's consider following functional form:

A and B coefficients are given by formulas: B = b and A = exp(a) where:

a=

and

b=

Least Squares Fitting

The term least squares describes a frequently used approach to solving overdetermined or inexactly specified systems of equations in an approximate sense. Instead of solving the equations exactly, we seek only to minimize the sum of the squares of the residuals.
The least squares criterion has important statistical interpretations. If appropriate probabilistic assumptions about underlying error distributions are made, least squares produces what is known as the maximum-likelihood estimate of the parameters. Even if the probabilistic assumptions are not satisfied, years of experience
have shown that least squares produces useful results.
The computational techniques for linear least squares problems make use of orthogonal matrix factorizations.
Lets consider function:

for estimation of coefficients a and b we can use following equations:

double sumY = 0;
double sumX = 0;
double sumXY = 0;
double sumX2 = 0;

foreach (Sample s in samples)
{
    sumY = sumY + s.y;
    sumX = sumX + s.x;
    sumX2 = sumX2 + s.x * s.x;
    sumXY = sumXY + s.x * s.y;
}

double a = (sumY * sumX2 - sumX * sumXY) / (samples.Count * sumX2 - (sumX * sumX));
double b = (samples.Count * sumXY - (sumX * sumY)) / (samples.Count * sumX2 - (sumX * sumX));

New article on CodeProject.com: Visualization and Comparison of sorting algorithms in C#

Before a couple of days I have posted new article about sorting algorithms and visualization. More about that you can find here

• BiDirectional Bubble Sort
• Bubble Sort
• Bucket Sort
• Comb Sort
• Cycle Sort
• Gnome Sort
• Heap Sort
• Insertion Sort
• Merge Sort
• Odd-Even Sort
• Pigeonhole Sort
• Quick Sort
• Quick Sort with Bubble Sort
• Selection Sort
• Shell Sort

Gnome Sort

Gnome sort, originally proposed by Hamid Sarbazi-Azad in 2000 and called Stupid sort, and then later on described by Dick Grune and named "Gnome sort", is a sorting algorithm which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort.

It is conceptually simple, requiring no nested loops. The running time is O(n²), but tends towards O(n) if the list is initially almost sorted. In practice the algorithm can run as fast as Insertion sort. The average runtime is O(n²)

The algorithm always finds the first place where two adjacent elements are in the wrong order, and swaps them. It takes advantage of the fact that performing a swap can introduce a new out-of-order adjacent pair only right before or after the two swapped elements. It does not assume that elements forward of the current position are sorted, so it only needs to check the position directly before the swapped elements.

public IList GnomeSort(IList arrayToSort)
{
    int pos = 1;
    while (pos < arrayToSort.Count)
    {
        if (((IComparable)arrayToSort[pos]).CompareTo(arrayToSort[pos - 1]) >= 0)
        {
            pos++;
        }
        else
        {
            object temp = arrayToSort[pos];
            arrayToSort[pos] = arrayToSort[pos - 1];
            RedrawItem(pos);

            arrayToSort[pos - 1] = temp;
            RedrawItem(pos - 1);
            RefreshPanel(pnlSamples);
            if (savePicture)
                SavePicture();
            if (pos > 1)
            {
                pos--;
            }
        }
    }
    return arrayToSort;
}

Shell Sort

The principle of Shell sort is to rearrange the file so that looking at every hth element yields a sorted file. We call such a file h-sorted. If the file is then k-sorted for some other integer k, then the file remains h-sorted. For instance, if a list was 5-sorted and then 3-sorted, the list is now not only 3-sorted, but both 5- and 3-sorted. If this were not true, the algorithm would undo work that it had done in previous iterations, and would not achieve such a low running time.


The algorithm draws upon a sequence of positive integers known as the increment sequence. Any sequence will do, as long as it ends with 1, but some sequences perform better than others. The algorithm begins by performing a gap insertion sort, with the gap being the first number in the increment sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1. When the increment reaches 1, the gap insertion sort is simply an ordinary insertion sort, guaranteeing that the final list is sorted. Beginning with large increments allows elements in the file to move quickly towards their final positions, and makes it easier to subsequently sort for smaller increments.

public IList ShellSort(IList arrayToSort)
{
    int i, j, increment;
    object temp;

    increment = arrayToSort.Count / 2;

    while (increment > 0)
    {
        for (i = 0; i < arrayToSort.Count; i++)
        {
            j = i;
            temp = arrayToSort[i];
            while ((j >= increment) && (((IComparable)arrayToSort[j - increment]).CompareTo(temp) > 0))
            {
                arrayToSort[j] = arrayToSort[j - increment];
                RedrawItem(j);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
                j = j - increment;
            }
            arrayToSort[j] = temp;
            RedrawItem(j);
            pnlSamples.Refresh();
            if (chkCreateAnimation.Checked)
                SavePicture();
        }
        if (increment == 2)
            increment = 1;
        else
            increment = increment * 5 / 11;
    }

    return arrayToSort;
}

Selection Sort

The algorithm works as follows:

• Find the minimum value in the list
• Swap it with the value in the first position
• Repeat the steps above for the remainder of the list (starting at the second position and advancing each time)

Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array.

public IList SelectionSort(IList arrayToSort)
{
    int min;
    for (int i = 0; i < arrayToSort.Count; i++)
    {

        min = i;
        for (int j = i + 1; j < arrayToSort.Count; j++)
        {
            if (((IComparable)arrayToSort[j]).CompareTo(arrayToSort[min]) < 0)
            {
                min = j;
            }
        }
        object temp = arrayToSort[i];
        arrayToSort[i] = arrayToSort[min];
        arrayToSort[min] = temp;

        RedrawItem(i);
        RedrawItem(min);
        pnlSamples.Refresh();
        if (chkCreateAnimation.Checked)
            SavePicture();    
    }

    return arrayToSort;
}

Quick Sort with Bubble Sort

public IList BubbleSort(IList arrayToSort, int left, int right)
{

    for (int i = left; i < right; i++)
    {
        for (int j = right; j > i; j--)
        {
            if (((IComparable)arrayToSort[j - 1]).CompareTo(arrayToSort[j]) > 0)
            {
                object temp = arrayToSort[j - 1];
                arrayToSort[j - 1] = arrayToSort[j];
                RedrawItem(j-1);
                arrayToSort[j] = temp;
                RedrawItem(j);
                pnlSamples.Refresh();
                if (chkCreateAnimation.Checked)
                    SavePicture();
            }
        }
    }

    return arrayToSort;
}

public IList QuickSortWithBubbleSort(IList a, int left, int right)
{
    int i = left;
    int j = right;


    if (right - left <= 6)
    {
        BubbleSort(a, left, right);
        return a;
    }

    double pivotValue = ((left + right) / 2);
    int x = (int)a[int.Parse(pivotValue.ToString())];

    a[(left + right) / 2] = a[right];
    a[right] = x;
    RedrawItem(right);
    pnlSamples.Refresh();
    if (chkCreateAnimation.Checked)
        SavePicture();

    while (i <= j)
    {
        while (((IComparable)a[i]).CompareTo(x) < 0)
        {
            i++;
        }
        while (((IComparable)x).CompareTo(a[j]) < 0)
        {
            j--;
        }

        if (i <= j)
        {
            object temp = a[i];
            a[i++] = a[j];
            RedrawItem(i - 1);
            a[j--] = temp;
            RedrawItem(j + 1);
            pnlSamples.Refresh();
            if (chkCreateAnimation.Checked)
                SavePicture();
        }
    }
    if (left < j)
    {
        QuickSortWithBubbleSort(a, left, j);
    }
    if (i < right)
    {
        QuickSortWithBubbleSort(a, i, right);
    }

    return a;
}