C# – Seite 2

Combosort

Published by Thomas Christof on 5. November 2015

        public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();

            //Calculate an efficient step size.
            //Ofc it depends on many factors and it won't be perfect in every case.
            int divideValue = (int)Math.Pow(objectList.Count, 1 / 3);

            for (int partCount = divideValue; partCount > 0; partCount--)
            {
                //Split the objectList up into smaller lists and sort them parallel.
                List<List<T>> listParts = new List<List<T>>();
                int elementsPerPart = objectList.Count / partCount;
                bool isEvenCollection = ((float)(objectList.Count / partCount)) % 1 == 0;

                for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)
                {
                    listParts.Add(objectList.GetRange(listPartIndex * elementsPerPart, elementsPerPart));
                    if (!isEvenCollection && listPartIndex == partCount - 1) //It is not an even number. We have to handle the uneven element.
                        listParts[listParts.Count - 1].Add(objectList.ElementAt((listPartIndex * elementsPerPart) + elementsPerPart));
                }

                //Sort all the lists with the bubblesort.
                Parallel.ForEach(listParts, (currentCollection) =>
                {
                    listParts[listParts.IndexOf(listParts.Where(currentListPart => currentListPart.Equals(currentCollection)).Single())] =
                    SortFactory.Sort(sortFunction, currentCollection, SortMethod.Bubble).ToList();
                });

                //Create a temporary array which will get all the sorted results.
                T[] newObjectArray = new T[listParts.Sum(currentListPart => currentListPart.Count)];
                for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)
                    Array.Copy(listParts[listPartIndex].ToArray(), 0, newObjectArray, listPartIndex * elementsPerPart, listParts[listPartIndex].Count);
                objectList = newObjectArray.ToList();
            }

            return objectList;
        }
    }

public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

//Calculate an efficient step size.

//Ofc it depends on many factors and it won't be perfect in every case.

int divideValue = (int)Math.Pow(objectList.Count, 1 / 3);

for (int partCount = divideValue; partCount > 0; partCount--)

{

//Split the objectList up into smaller lists and sort them parallel.

List<List<T>> listParts = new List<List<T>>();

int elementsPerPart = objectList.Count / partCount;

bool isEvenCollection = ((float)(objectList.Count / partCount)) % 1 == 0;

for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)

{

listParts.Add(objectList.GetRange(listPartIndex * elementsPerPart, elementsPerPart));

if (!isEvenCollection && listPartIndex == partCount - 1) //It is not an even number. We have to handle the uneven element.

listParts[listParts.Count - 1].Add(objectList.ElementAt((listPartIndex * elementsPerPart) + elementsPerPart));

}

//Sort all the lists with the bubblesort.

Parallel.ForEach(listParts, (currentCollection) =>

{

listParts[listParts.IndexOf(listParts.Where(currentListPart => currentListPart.Equals(currentCollection)).Single())] =

SortFactory.Sort(sortFunction, currentCollection, SortMethod.Bubble).ToList();

});

//Create a temporary array which will get all the sorted results.

T[] newObjectArray = new T[listParts.Sum(currentListPart => currentListPart.Count)];

for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)

Array.Copy(listParts[listPartIndex].ToArray(), 0, newObjectArray, listPartIndex * elementsPerPart, listParts[listPartIndex].Count);

objectList = newObjectArray.ToList();

}

return objectList;

}

Shellsort

Published by Thomas Christof on 5. November 2015

        public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();

            //Calculate an efficient step size.
            //Ofc it depends on many factors and it won't be perfect in every case.
            int divideValue = (int)Math.Pow(objectList.Count, 1 / 3);

            for (int partCount = divideValue; partCount > 0; partCount--)
            {
                //Split the objectList up into smaller lists and sort them parallel.
                List<List<T>> listParts = new List<List<T>>();
                int elementsPerPart = objectList.Count / partCount;
                bool isEvenCollection = ((float)(objectList.Count / partCount)) % 1 == 0;

                for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)
                {
                    listParts.Add(objectList.GetRange(listPartIndex * elementsPerPart, elementsPerPart));
                    if (!isEvenCollection && listPartIndex == partCount - 1) //It is not an even number. We have to handle the uneven element.
                        listParts[listParts.Count - 1].Add(objectList.ElementAt((listPartIndex * elementsPerPart) + elementsPerPart));
                }

                //Sort all the lists with the insertionsort.
                Parallel.ForEach(listParts, (currentCollection) =>
                {
                    listParts[listParts.IndexOf(listParts.Where(currentListPart => currentListPart.Equals(currentCollection)).Single())] = 
                    SortFactory.Sort(sortFunction, currentCollection, SortMethod.Insertion).ToList();
                });

                //Create a temporary array which will get all the sorted results.
                T[] newObjectArray = new T[listParts.Sum(currentListPart => currentListPart.Count)];
                for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)
                    Array.Copy(listParts[listPartIndex].ToArray(), 0, newObjectArray, listPartIndex * elementsPerPart, listParts[listPartIndex].Count);
                objectList = newObjectArray.ToList();
            }

            return objectList;
        }

public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

//Calculate an efficient step size.

//Ofc it depends on many factors and it won't be perfect in every case.

int divideValue = (int)Math.Pow(objectList.Count, 1 / 3);

for (int partCount = divideValue; partCount > 0; partCount--)

{

//Split the objectList up into smaller lists and sort them parallel.

List<List<T>> listParts = new List<List<T>>();

int elementsPerPart = objectList.Count / partCount;

bool isEvenCollection = ((float)(objectList.Count / partCount)) % 1 == 0;

for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)

{

listParts.Add(objectList.GetRange(listPartIndex * elementsPerPart, elementsPerPart));

if (!isEvenCollection && listPartIndex == partCount - 1) //It is not an even number. We have to handle the uneven element.

listParts[listParts.Count - 1].Add(objectList.ElementAt((listPartIndex * elementsPerPart) + elementsPerPart));

}

//Sort all the lists with the insertionsort.

Parallel.ForEach(listParts, (currentCollection) =>

{

listParts[listParts.IndexOf(listParts.Where(currentListPart => currentListPart.Equals(currentCollection)).Single())] =

SortFactory.Sort(sortFunction, currentCollection, SortMethod.Insertion).ToList();

});

//Create a temporary array which will get all the sorted results.

T[] newObjectArray = new T[listParts.Sum(currentListPart => currentListPart.Count)];

for (int listPartIndex = 0; listPartIndex < partCount; listPartIndex++)

Array.Copy(listParts[listPartIndex].ToArray(), 0, newObjectArray, listPartIndex * elementsPerPart, listParts[listPartIndex].Count);

objectList = newObjectArray.ToList();

}

return objectList;

}

Inserationsort

Published by Thomas Christof on 5. November 2015

    internal class Insertion : ObjectSort
    {
        public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();

            for (int currentIndex = 1; currentIndex < objectList.Count; currentIndex++)
            {
                //Put the current object into a buffer.
                T objectBuffer = objectList[currentIndex];

                //The index we have to shift.
                int shiftIndex = 0; //Shift all from 0 to the current index.

                //Climb down all the elements from the current index till 0.
                //Search for a smaller element than objectBuffer.
                for(int lowerIndex = currentIndex - 1; lowerIndex >= 0; lowerIndex--)
                {
                    bool isSmaller = (sortFunction.Compare(objectList[lowerIndex], objectList[currentIndex]) > 0);
                    if (isSmaller) continue; //We want the smallest element in the list.
                    shiftIndex = lowerIndex + 1;
                    break; //No more comparisons necessary.
                }

                if (currentIndex == shiftIndex) continue;
                T[] newObjectArray = new T[objectList.Count];
                objectList.CopyTo(currentIndex + 1, newObjectArray, currentIndex + 1, newObjectArray.Length - (currentIndex + 1));
                objectList.CopyTo(shiftIndex, newObjectArray, shiftIndex + 1, currentIndex - shiftIndex);
                if (shiftIndex > 0) objectList.CopyTo(0, newObjectArray, 0, shiftIndex);
                newObjectArray[shiftIndex] = objectBuffer;
                objectList = newObjectArray.ToList();
            }

            return objectList;
        }
    }

internal class Insertion : ObjectSort

{

public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

for (int currentIndex = 1; currentIndex < objectList.Count; currentIndex++)

{

//Put the current object into a buffer.

T objectBuffer = objectList[currentIndex];

//The index we have to shift.

int shiftIndex = 0; //Shift all from 0 to the current index.

//Climb down all the elements from the current index till 0.

//Search for a smaller element than objectBuffer.

for(int lowerIndex = currentIndex - 1; lowerIndex >= 0; lowerIndex--)

{

bool isSmaller = (sortFunction.Compare(objectList[lowerIndex], objectList[currentIndex]) > 0);

if (isSmaller) continue; //We want the smallest element in the list.

shiftIndex = lowerIndex + 1;

break; //No more comparisons necessary.

}

if (currentIndex == shiftIndex) continue;

T[] newObjectArray = new T[objectList.Count];

objectList.CopyTo(currentIndex + 1, newObjectArray, currentIndex + 1, newObjectArray.Length - (currentIndex + 1));

objectList.CopyTo(shiftIndex, newObjectArray, shiftIndex + 1, currentIndex - shiftIndex);

if (shiftIndex > 0) objectList.CopyTo(0, newObjectArray, 0, shiftIndex);

newObjectArray[shiftIndex] = objectBuffer;

objectList = newObjectArray.ToList();

}

return objectList;

}

Selectionsort

Published by Thomas Christof on 14. Oktober 2015

        public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();

            for(int currentIndex = 0; currentIndex < objectList.Count; currentIndex++)
            {
                //Always select the current index at first.
                int currentMinIndex = currentIndex;

                //Determine the min object in the list.
                for(int minIndex = currentIndex + 1; minIndex < objectList.Count; minIndex++)
                {
                    if (sortFunction.Compare(objectList[currentMinIndex], objectList[minIndex]) > 0)
                        currentMinIndex = minIndex;
                }

                //Swap the min object with the current position.
                //Swap with the same position won't have an effect.
                objectList.Swap(currentIndex, currentMinIndex);
            }

            return objectList;
        }

public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

for(int currentIndex = 0; currentIndex < objectList.Count; currentIndex++)

{

//Always select the current index at first.

int currentMinIndex = currentIndex;

//Determine the min object in the list.

for(int minIndex = currentIndex + 1; minIndex < objectList.Count; minIndex++)

{

if (sortFunction.Compare(objectList[currentMinIndex], objectList[minIndex]) > 0)

currentMinIndex = minIndex;

}

//Swap the min object with the current position.

//Swap with the same position won't have an effect.

objectList.Swap(currentIndex, currentMinIndex);

}

return objectList;

}

       public static void Swap(this IList list, int x, int y)
        {
            object buffer = list[y];
            list[y] = list[x];
            list[x] = buffer;
        }

public static void Swap(this IList list, int x, int y)

{

object buffer = list[y];

list[y] = list[x];

list[x] = buffer;

}

Grobanalyse von Algorithmen

Published by Thomas Christof on 12. Oktober 2015

Eine erste grobe Einschätzung über die Effizienz eines Algorithmus ist schnell mit einer Grobanalyse erstellt. Der Algorithmus wird als Blackbox betrachtet und Speicher und CPU Auslastungen wird außer Acht gelassen. Was zählt ist nur die Zeit die für die Durchführung benötigt wird.

Shakesort (Cocktailsort)

Published by Thomas Christof on 11. Oktober 2015

        public override IEnumerable<T> Sort(IComparer<T> sortFunction, IEnumerable<T> collection)
        {
            List<T> objectList = collection.ToList();
            int endIndexLow = objectList.Count - 1;
            int endIndexHigh = 0;
            bool elementSwapped;

            do
            {
                elementSwapped = false;

                for (int x = endIndexHigh; x < endIndexLow; x++)
                {
                    if (sortFunction.Compare(objectList[x], objectList[x + 1]) > 0)
                    {
                        elementSwapped = true;
                        objectList.Swap(x, x + 1);
                    }
                }

                endIndexLow--;
                if (!elementSwapped)
                    break;

                elementSwapped = false;

                for (int y = endIndexLow; y > endIndexHigh; y--)
                {
                    if (sortFunction.Compare(objectList[y], objectList[y - 1]) < 0)
                    {
                        elementSwapped = true;
                        objectList.Swap(y, y - 1);
                    }
                }

                endIndexHigh++;
            } while (elementSwapped);

            return objectList;
        }

public override IEnumerable<T> Sort(IComparer<T> sortFunction, IEnumerable<T> collection)

{

List<T> objectList = collection.ToList();

int endIndexLow = objectList.Count - 1;

int endIndexHigh = 0;

bool elementSwapped;

{

elementSwapped = false;

for (int x = endIndexHigh; x < endIndexLow; x++)

{

if (sortFunction.Compare(objectList[x], objectList[x + 1]) > 0)

{

elementSwapped = true;

objectList.Swap(x, x + 1);

}

endIndexLow--;

if (!elementSwapped)

break;

elementSwapped = false;

for (int y = endIndexLow; y > endIndexHigh; y--)

{

if (sortFunction.Compare(objectList[y], objectList[y - 1]) < 0)

{

elementSwapped = true;

objectList.Swap(y, y - 1);

}

endIndexHigh++;

} while (elementSwapped);

return objectList;

}

        public static void Swap(this IList list, int x, int y)
        {
            object buffer = list[y];
            list[y] = list[x];
            list[x] = buffer;
        }

public static void Swap(this IList list, int x, int y)

{

object buffer = list[y];

list[y] = list[x];

list[x] = buffer;

}

Bubblesort

Published by Thomas Christof on 11. Oktober 2015

Der Bubblesort ist einer der einfachsten Sortieralgorithmen. Die Vorsortierung der zu sortierenden Datenmenge hat keinerlei Auswirkung auf die Laufzeit. Laufzeit Selbst nach der Optimierung des Algorithmus werden viele Einträge doppelt verglichen. Im Allgemeinen beträgt die Laufzeit Θ(n²), kann jedoch durch Optimierungen auf O(n²) reduziert werden. Einsatzgebiet Aufgrund der Einfachheit und der schlechten performance gibt es keine besonderen Einsatzgebiete. Jedoch für …

Knuth Morris Pratt (KMP)

Published by Thomas Christof on 9. Oktober 2015

Knuth Morris Pratt (KMP) in C#. SearchResult ist ein Datenbehälter und wird hier deshalb nicht aufgeführt.

DevLog #3 Alpha – [0.05554.7204]

Published by Thomas Christof on 17. März 2015

Noch 29 Tage bis zu dem Release auf Steam. Bis dorthin ist es noch ein weiter Weg für alle Projektbeteiligten. Der Steam-Store wartet sehnsüchtig auf seine Einrichtung, Grafiken und Trailer müssen noch erstellt und neue Levels/Features ausprogrammiert werden. Dennoch liegen wir gut im Zeitplan. DevLog #3 Alpha – [0.05554.7204] Boosts gelten nunmehr nur noch temporär. Durch …