Быстрая сортировка на четность нечетность чисел - C#
Формулировка задачи:
Есть собственный список. А так же реализован алгоритм быстрой сортировки.
Где IMyComparer у нас интерфейс с одним методом. (да знаю, в таком случае лучше использовать делегат, но у нас задание реализовать с помощью интерфейса).
Ну и сама сортировка выглядит следующим образом:
Собственно вопрос как в данном случае реализовать сортировку четных не четных чисел. Сам алгоритм сортировки должен быть в функции Compare. Я думаю, что проблема в реализации, ведь мы в сортировке сравниваем некое число с опорным элементом. Как обойти? И есть ли толк от быстрой сортировки в данном случае, ведь нам по идее надо будет разделить в последствии наш массив на две части, и отсортировать его подчасти.
В идеале - массив делят на две части, левая например с четными елементами, правая с нечетными. Потом уже каждая часть сортируется по отдельности по возрастанию.
У кого какие идеи?
public void Sort(IMyComparer<T> comparer) { Sort(0, Count - 1, comparer); } public void Sort(int low, int high, IMyComparer<T> comparer) { ThrowIfIsOutOfRange(low, high); T pivot = array[low + (high - low) / 2]; // also like (high+low)/2 but don't owerflow array on big data int i = low; int j = high; Partition(ref i, ref j, pivot, comparer); if (i < high) Sort(i, high, comparer); if (low < j) Sort(low, j, comparer); } private void Partition(ref int i, ref int j, T pivot, IMyComparer<T> comparer) { while (i < j) { while (comparer.Compare(array[i], pivot) < 0) i++; while (comparer.Compare(array[j], pivot) > 0) j--; if (i <= j) { T temp = array[i]; array[i] = array[j]; array[j] = temp; i++; j--; } } }
interface IMyComparer<T> { int Compare(T left, T right); }
static void Main(string[] args) { MyList<int> list = new MyList<int>(); Random rnd = new Random(); for (int i = 0; i <= 10; i++) { list.Add(rnd.Next(10)); } MyComparer myComperer = new MyComparer(); list.Sort(myComperer); for (int i = 0; i < list.Count; i++) { Console.WriteLine("{0}", list[i]); } Console.ReadKey(true); } sealed class MyComparer : IMyComparer<int> { public int Compare(int left, int right) { //Discending sort return -left.CompareTo(right); } }
Решение задачи: «Быстрая сортировка на четность нечетность чисел»
textual
Листинг программы
sealed class MyComparer : IMyComparer<int> { public int Compare(int left, int right) { int a = left & 1; int b = right & 1; return (a == b) ? left.CompareTo(right) : a.CompareTo(b); } }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д