Ошибка в интроспективной сортировке массива целых чисел по убыванию - C#

Узнай цену своей работы

Формулировка задачи:

Пытаюсь сделать сортировку большого массива целых чисел по убыванию следующим образом: 
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
 
namespace introSort
{
 
    class Program
    {
        public static void IntrospectiveSorting(ref int[] array)
        {
            int sizeOfPartition = Partitioning(ref array, 0, array.Length - 1);
 
            if (sizeOfPartition < 16)
            {
                InsertionSorting(ref array);
            }
            else if (sizeOfPartition > (2 * Math.Log(array.Length)))
            {
                HeapSorting(array);
            }
            else
            {
                QuickRecursiveSorting(ref array, 0, array.Length - 1);
            }
        }
 
        private static void InsertionSorting(ref int[] array)
        {
            for (int i = 1; i < array.Length; ++i)
            {
                int j = i;
 
                while ((j > 0))
                {
                    if (array[j - 1] < array[j])
                    {
                        array[j - 1] ^= array[j];
                        array[j] ^= array[j - 1];
                        array[j - 1] ^= array[j];
 
                        --j;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        static void MinHeapCreating(int[] input)
        {
            input[0] = input.Length - 1;
 
            for (int i = (input[0] / 2); i > 0; i--)
            {
                MinHeapify(input, i);
            }
        }
 
        static void MinHeapify(int[] input, int index)
        {
            var left = 2 * index;
            var right = 2 * index + 1;
            int smallest;
 
            if (left <= input[0] && input[left] < input[index])
                smallest = left;
            else
                smallest = index;
 
            if (right <= input[0] && input[right] < input[smallest])
                smallest = right;
 
            if (smallest != index)
            {
                Swaping(ref input[smallest], ref input[index]);
                MinHeapify(input, smallest);
            }
        }
 
        static public void HeapSorting(int[] input)
        {
            MinHeapCreating(input);
 
            for (int i = input[0]; i > 0; i--)
            {
                Swaping(ref input[1], ref input[i]);
                input[0]--;
                MinHeapify(input, 1);
            }
        }
 
        static public void Swaping(ref int a, ref int b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        private static void QuickRecursiveSorting(ref int[] array, int left, int right)
        {
            if (left > right)
            {
                int q = Partitioning(ref array, left, right);
                QuickRecursiveSorting(ref array, left, q - 1);
                QuickRecursiveSorting(ref array, q + 1, right);
            }
        }
 
        private static int Partitioning(ref int[] array, int left, int right)
        {
            int root = array[right];
            int temp;
            int i = left;
 
            for (int j = left; j < right; ++j)
            {
                if (array[j] <= root)
                {
                    temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                    ++i;
                }
            }
 
            array[right] = array[i];
            array[i] = root;
 
            return i;
        }
        static void Main(string[] args)
        {
            int[] array = { 3, 4, 50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 
                            4, 20, 111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20,
                            4, 20, 111, 123, 4, 50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10,
                            5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10,
                            5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 
                            20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8,
                            20, 304, 10, 2, 30, 4, 05, 660, 234, 102, 5053, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4,
                            0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 
                            5, 2, 3, 7, 8, 20, 304, 10, 2, 30, 4, 05, 660, 234, 102, 50, 50, 100, 200, 0, 10, 20, 30, 500, 4, 50, 100, 200, 0, 10, 20, 30, 5004, 50, 100, 200, 
                            0, 10, 20, 30, 500, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 100, 
                            200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 
                            23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 4,
                            50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20,
                            111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20,
                            111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 
                            123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8, 20, 304, 10, 2, 30, 
                            4, 05, 660, 234, 102, 5053, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 
                            4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8, 20, 304, 10, 
                            2, 30, 4, 05, 660, 234, 102, 50, 50, 100, 200, 0, 10, 20, 30, 500, 4, 50, 100, 200, 0, 10, 20, 30, 5004, 50, 100, 200, 0, 10, 20, 30, 500, 7, 2, 3, 
                            4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56 };
            IntrospectiveSorting(ref array);
            for (int i = 0; i < array.Length - 1; i++)
            {
 
                if (i % 7 == 0 && i != 0)
                    Console.Write("\n");
                Console.Write(array[i]);
                Console.Write(' ');
            }
 
        }
    }
 
}
Она работает неверно т. к. в качестве первого элемента массива получается ноль. Как это происходит для меня какая-то загадка не смотря на часы попыток разобраться с этим ((( Может кто-нибудь сможет понять как сюда закралась эта ошибка? Заранее огромная благодарность. P. S. Сдвинуть массив на элемент влево не предлагать т. к. это критично для времени. И еще наверно было бы круто если бы подсказали как лучше распараллелить QuickRecursiveSorting.

Решение задачи: «Ошибка в интроспективной сортировке массива целых чисел по убыванию»

textual
Листинг программы 
using System;
using System.Collections.Generic;
using System.Text;
using System.Threading.Tasks;
 
namespace introSort
{
 
    class Program
    {
        public static void IntrospectiveSorting(ref int[] array)
        {
            int sizeOfPartition = Partitioning(ref array, 0, array.Length - 1);
 
            if (sizeOfPartition < 16)
            {
                InsertionSorting(ref array);
            }
            else if (sizeOfPartition > (2 * Math.Log(array.Length)))
            {
                HeapSorting(array);
            }
            else
            {
                QuickRecursiveSorting(ref array, 0, array.Length - 1);
            }
        }
 
        private static void InsertionSorting(ref int[] array)
        {
            for (int i = 1; i < array.Length; ++i)
            {
                int j = i;
 
                while ((j > 0))
                {
                    if (array[j - 1] < array[j])
                    {
                        array[j - 1] ^= array[j];
                        array[j] ^= array[j - 1];
                        array[j - 1] ^= array[j];
 
                        --j;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        static void MinHeapCreating(int[] input,int first)
        {
 
            for (int i = (first / 2); i > 0; i--)
            {
                MinHeapify(input, i,first);
            }
        }
 
        static void MinHeapify(int[] input, int index,int first)
        {
            var left = 2 * index;
            var right = 2 * index+1;
            int smallest;
 
            if (left <= first && input[left] < input[index])
                smallest = left;
            else
                smallest = index;
 
            if (right <= first && input[right] < input[smallest])
                smallest = right;
 
            if (smallest != index)
            {
                Swaping(ref input[smallest], ref input[index]);
                MinHeapify(input, smallest,first);
            }
        }
 
        static public void HeapSorting(int[] input)
        {
            int first = input.Length-1;
 
            MinHeapCreating(input,first);
            for (int i = first; i > 0; i--)
            {
                Swaping(ref input[0], ref input[i]);
                first--;
                MinHeapify(input, 0,first);
            }
        }
 
        static public void Swaping(ref int a, ref int b)
        {
            var temp = a;
            a = b;
            b = temp;
        }
 
 
        private static void QuickRecursiveSorting(ref int[] array, int left, int right)
        {
            if (left > right)
            {
                int q = Partitioning(ref array, left, right);
                QuickRecursiveSorting(ref array, left, q - 1);
                QuickRecursiveSorting(ref array, q + 1, right);
            }
        }
 
        private static int Partitioning(ref int[] array, int left, int right)
        {
            int root = array[right];
            int temp;
            int i = left;
 
            for (int j = left; j < right; ++j)
            {
                if (array[j] <= root)
                {
                    temp = array[j];
                    array[j] = array[i];
                    array[i] = temp;
                    ++i;
                }
            }
 
            array[right] = array[i];
            array[i] = root;
 
            return i;
        }
        static void Main(string[] args)
        {
            int[] array = { 3, 4, 50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 
                            4, 20, 111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20,
                            4, 20, 111, 123, 4, 50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10,
                            5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10,
                            5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 
                            20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8,
                            20, 304, 10, 2, 30, 4, 05, 660, 234, 102, 5053, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4,
                            0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 
                            5, 2, 3, 7, 8, 20, 304, 10, 2, 30, 4, 05, 660, 234, 102, 50, 50, 100, 200, 0, 10, 20, 30, 500, 4, 50, 100, 200, 0, 10, 20, 30, 5004, 50, 100, 200, 
                            0, 10, 20, 30, 500, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 100, 
                            200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 
                            23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 4,
                            50, 100, 200, 0, 10, 20, 30, 500, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20,
                            111, 123, 53, 23, 778, 45, 3, 400, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20,
                            111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 4, 20, 111, 
                            123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8, 20, 304, 10, 2, 30, 
                            4, 05, 660, 234, 102, 5053, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56, 45, 2, 6, 0, 2, 6, 7, 2, 3, 4, 0, 10, 5, 67, 20, 
                            4, 20, 111, 123, 53, 23, 778, 45, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 845, 3, 67, 8, 34, 8, 3, 4, 5, 2, 3, 7, 867, 8, 34, 8, 3, 4, 5, 2, 3, 7, 8, 20, 304, 10, 
                            2, 30, 4, 05, 660, 234, 102, 50, 50, 100, 200, 0, 10, 20, 30, 500, 4, 50, 100, 200, 0, 10, 20, 30, 5004, 50, 100, 200, 0, 10, 20, 30, 500, 7, 2, 3, 
                            4, 0, 10, 5, 67, 20, 4, 20, 111, 123, 53, 23, 778, 0, 10, 302, 10, 0, 1, 20, 3, 5, 345, 2, 12, 345, 456, 3, 56 };
            IntrospectiveSorting(ref array);
            for (int i = 0; i < array.Length - 1; i++)
            {
 
                if (i % 7 == 0 && i != 0)
                    Console.Write("\n");
                Console.Write(array[i]);
                Console.Write(' ');
            }
            Console.ReadKey();
        }
    }
 
}

ИИ поможет Вам:

  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

11   голосов , оценка 3.909 из 5
Похожие ответы