Rabin-Karp

internal override SearchResult Search(string text, string pattern) { if (pattern.Length > text.Length) return SearchResult.Empty(); SearchResult searchResult = new SearchResult() { Matches = new List<Match>() }; int patternHashValue = pattern.GetHashCode(); for(int index = 0; index + pattern.Length < text.Length; index++) { string indexString = text.Substring(index, pattern.Length); int indexHashValue = indexString.GetHashCode(); if(patternHashValue == indexHashValue) if (string.CompareOrdinal(pattern, indexString) …

Heapsort

internal class Heap : StorageObjectSort { private object[] items; public int Size { get; set; } = 0; public override IEnumerable<T> Sort<T>(IComparer<T> sortFunction, IEnumerable<T> collection) { List<T> objectList = collection.ToList(); Initialize(objectList.Count); objectList.ForEach(o => Insert(o, sortFunction)); objectList.Clear(); while (Size > 0) objectList.Add((T)Remove(sortFunction)); return objectList; } protected override void Insert<T>(object item, IComparer<T> sortFunction) { items[Size] = item; …

Combosort

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 …

Shellsort

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 …

Inserationsort

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 …

Selectionsort

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

Grobanalyse von Algorithmen

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)

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); } …

Bubblesort

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 …