У меня проблемы с попыткой заставить этот алгоритм быстрой сортировки работать на 100%.На данный момент, он немного зависает, когда пытается поменять 2 одинаковых числа (попытался исправить это, как вы увидите в коде).
Черт, что-то почти там.Я просто не уверен, что мне не хватает.Я потратил несколько часов, пытаясь понять это безрезультатно.
Я делаю это для класса, к сожалению, мой учитель сказал, что он не может помочь мне, так как я делаю дженерики (для дополнительного кредита) ион может извлекать только строки или целые числа в C # (он в основном учитель java / c ++ .... он не работает с c # очень долго).
Статический класс быстрой сортировки
class QuickSort<T> where T : IComparable<T>
{
//No variables or properties, more of a helper class
//This is the method that will be called by the user.
//It ties the internal methods into one to sort the
//array. It needs an array passed into it, As well as
//the size of the array.
public static void QSort(T[] array,int size)
{
//If array is empty, or has 1 element, it is sorted.
//Return immediatly.
if (size == 1 || size == 0)
{ return; }
else
{
//Time to sort, pass in the array, the left bounds of 0,
//and the right bounds of high - 1 (the last element).
Partition(array, 0, size);
}
}
//This method splits the work area in half, putting lower
//values left of the pivot, and greater values right of
//the pivot.
private static void Partition(T[] array, int lower, int upper)
{
//If upper is less 1, then there is no
//sorting that can be done.
if ((upper - lower) < 2)
{ return; }
//Get the right bound -1, to make sure it stays
//within actual array bounds
int left = lower;
int right = upper-1;
//Set pivot to equal the middle most array. I used this
//expression because wikipedia mentions it will stop
//overflow and invalid pivot position that can come
//with exceptionally large arrays using the basic
//(a+b)/2 equation.
int pivot_index = left + (right - left) / 2;
T pivot = array[pivot_index];
while (left < right)
{
//array[left] < pivot
while ((array[left].CompareTo(pivot) <= 0) && (left < right))
{
left++;
}
//array[right] > pivot
while ((array[right].CompareTo(pivot) >= 0)&& (left < right))
{
right--;
}
if (left != right)
{
Swap(array, left, right);
left++;
right--;
}
}
//Send in the lower bound, and the pivot point.
Partition(array, lower, right);
//Send in the pivot point as lower bound, and upper
Partition(array, right+1, upper);
}
//This method simply swaps the first position with the second.
private static void Swap(T[] array, int position1, int position2)
{
T tempHolder = array[position1];
array[position1] = array[position2];
array[position2] = tempHolder;
}
}
Основной класс
class Tester
{
static void Main(string[] args)
{
ContiguousList<int> tester = new ContiguousList<int>(100);
Random rand = new Random(5433);
for (int ii = 0; ii < tester.Size; ii++)
{
tester.SetElement(ii, rand.Next(0, 100));
}
for (int ii = 0; ii < tester.Size; ii++)
{
Console.WriteLine(tester.GetElement(ii).ToString());
}
Console.WriteLine();
tester.Sort();
for (int ii = 0; ii < tester.Size; ii++)
{
Console.WriteLine(tester.GetElement(ii).ToString());
}
}
}
Для меня это довольно сложно, поскольку единственные онлайн-реализации, за которыми я могу следовать, это либо для c ++ (нашел хорошее объяснение psuedocode, которое сработало бы, если бы я мог использовать указатели>. <) или их только для сортировки целых чисел. </p>
Я думаю, может быть, отсутствует своп, или моя логика для решения, если массив [left] == array [right] неисправен.
(О, и не возражайте против ContiguousList в основном ... наш учитель велел нам кодировать наш собственный умный массив и велел нам использовать его, чтобы мы могли видеть, как работают умные массивы.)
Спасибо залюбая помощь людям.Мой мозг действительно в тупик.
- Правка Я изменил циклы, поэтому один проверяет> = 0, другой <0, чтобы избавиться от ненужной проверки. </p>
- Редакцию я немного подправил, теперь кажется, что она почти отсортирована, но не совсем, мои первые 10 элементов - 1,1,2,3,2,3,6,5,4,5, так что как-то что-топроисходит неправильная перестановка, когда значения совпадают.
Edit-- Просто перечитайте описание быстрого псевдокода / псевдокода, которое я использовал, и заметили немного "эта версия будет работать только на массивах с уникальными элементами"предупреждение ... так что я прав, в том, что это нужно делать, когда 2 элемента содержат одно и то же значение, что-то не работает ... Однако, как исправить это, atm>. <</p>