1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
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; } } |
Schlagwort: C#
Shellsort
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
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; } |
1 2 3 4 5 6 |
public static void Swap(this IList list, int x, int y) { object buffer = list[y]; list[y] = list[x]; list[x] = buffer; } |
Shakesort (Cocktailsort)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
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; } |
1 2 3 4 5 6 |
public static void Swap(this IList list, int x, int y) { object buffer = list[y]; list[y] = list[x]; list[x] = buffer; } |
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 …
DevLog #3 Alpha – [0.05554.7204]
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 …