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 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;
	}
}
0 0 vote
Article Rating
Subscribe
Notify of
1 Comment
Most Voted
Newest Oldest
Inline Feedbacks
View all comments
trackback

[…] Der Insertionsort befindet sich hier. […]