Skip to content

Instantly share code, notes, and snippets.

@nikolaZ
Created June 20, 2013 07:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save nikolaZ/5820965 to your computer and use it in GitHub Desktop.
Save nikolaZ/5820965 to your computer and use it in GitHub Desktop.
QuickSorting not working.
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