Created
June 20, 2013 07:53
-
-
Save nikolaZ/5820965 to your computer and use it in GitHub Desktop.
QuickSorting not working.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
namespace SortingHomework | |
{ | |
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
public class Quicksorter<T> : ISorter<T> where T : IComparable<T> | |
{ | |
public IList<T> Collection { get; set; } | |
public void Sort(IList<T> collection) | |
{ | |
if (collection == null) | |
{ | |
throw new ArgumentNullException("collection", "Collection is null. Collection cannot be sorted!"); | |
} | |
int length = collection.Count; | |
if (length <= 1) | |
{ | |
return; | |
} | |
this.Collection = collection; | |
this.QuickSorting(0, length - 1); | |
collection = this.Collection; | |
} | |
private void QuickSorting(int startIndex, int endIndex) | |
{ | |
if (startIndex < endIndex) | |
{ | |
int pivotIndex = this.Collection.Count / 2; | |
int pivotNewIndex = this.Partition(startIndex, endIndex, pivotIndex); | |
// Recursively sort elements smaller than the pivot | |
this.QuickSorting(startIndex, pivotNewIndex - 1); | |
// Recursively sort elements at least as big as the pivot | |
this.QuickSorting(pivotNewIndex + 1, endIndex); | |
} | |
} | |
private int Partition(int startIndex, int endIndex, int pivotIndex) | |
{ | |
T pivot = this.Collection[pivotIndex]; | |
////swap, move pivot to end | |
//T safe = collection[endIndex]; | |
//collection[endIndex] = pivot; | |
//collection[pivotIndex] = safe; | |
this.Swap(pivotIndex, endIndex); | |
int storeIndex = startIndex; | |
for (int i = startIndex; i < endIndex - 1; i++) | |
{ | |
if (this.Collection[i].CompareTo(pivot) <= 0) | |
{ | |
////swap collection[i] and collection[storeIndex] | |
//T swap = collection[i]; | |
//collection[i] = collection[storeIndex]; | |
//collection[storeIndex] = swap; | |
//storeIndex++; | |
this.Swap(i, storeIndex); | |
} | |
} | |
//T change = collection[storeIndex]; | |
//collection[storeIndex] = collection[endIndex]; | |
//collection[endIndex] = change; | |
this.Swap(storeIndex, endIndex); | |
return storeIndex; | |
} | |
private void Swap(int index1, int index2) | |
{ | |
T swapValue = this.Collection[index1]; | |
this.Collection[index1] = this.Collection[index2]; | |
this.Collection[index2] = swapValue; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment