IComparable <T>дает стекопотока при использовании для отрицательных чисел? - PullRequest
Новая
       56

IComparable <T>дает стекопотока при использовании для отрицательных чисел?

0 голосов
/ 29 декабря 2011

Это утомленная проблема, я реализовал простую быструю сортировку следующим образом. 

        static void Main(string[] args)
    {
        List<int> unsorted = new List<int> { 1, 3, 5, 7, 9, 8, 6, 4, 2 };
        List<int> sorted = quicksort(unsorted);
        Console.WriteLine(string.Join(",", sorted));
        Console.ReadKey();
    }

    private static List<T> quicksort<T>(List<T> arr) where T : IComparable<T>
    {
        List<T> loe = new List<T>(), gt = new List<T>();

        if (arr.Count < 2)
            return arr;

        int pivot = arr.Count / 2;
        T pivot_val = arr[pivot];
        arr.RemoveAt(pivot);

        foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
                loe.Add(i);
            else
                gt.Add(i);
        }

        List<T> resultSet = new List<T>();
        resultSet.AddRange(quicksort(loe));

        gt.Add(pivot_val);

        resultSet.AddRange(quicksort(gt));
        return resultSet;
    }

Вывод: 1,2,3,4,5,6,7,8,9

Но когда я использую любое отрицательное число в несортированном списке, возникает ошибка переполнения стека,

например если список не отсортирован = новый список {1, 3, 5, 7, 9, 8, 6, 4, 2, -1 }; Теперь есть переполнение стека ..

Что происходит? Почему это не работает?

Ответы [ 2 ]

4 голосов
/ 29 декабря 2011

В вашем алгоритме есть ошибка.Рассмотрим простейший список ввода {1, -1}.Давайте рассмотрим вашу логику.

  1. Сначала вы выбираете сводный индекс Count / 2, равный 1.
  2. Затем вы удаляете сводный элемент с индексом 1 (-1) изсписок arr.
  3. Затем вы сравниваете каждый оставшийся элемент в списке arr (в индексе 0 только 1) с сводкой.
  4. 1 больше, чем сводка(-1), поэтому вы добавляете его в список gt.
  5. Затем вы быстро сортируете список loe, который пуст.Такая сортировка возвращает пустой список, который вы добавляете в результирующий набор.
  6. Затем вы добавляете сводное значение в конец списка gt, поэтому список gt теперь выглядит следующим образом: {1-1 Обратите внимание, что это тот же список, с которого вы начали.
  7. Затем вы пытаетесь быстро отсортировать список gt.Так как вы вызываете подпрограмму быстрой сортировки с тем же входным сигналом, та же последовательность шагов повторяется до тех пор, пока стек не переполнится.

Кажется, ошибка в вашей логике состоит в том, что вы слепо добавляете сводку кGT список, не сравнивая его ни с чем.Я оставлю это вам, чтобы выяснить, как заставить это работать.

Отредактировано, чтобы добавить: я предполагаю, что это домашнее задание, но если это не так, я настоятельно рекомендую использовать встроенный .NETSort() метод на List<T>.Он был высоко оптимизирован и тщательно протестирован, и, скорее всего, будет работать лучше, чем что-либо домашнее.Зачем изобретать велосипед?

0 голосов
/ 29 декабря 2011

, если у вас нет отладчика, попробуйте это ... 

foreach (T i in arr)
        {
            if (i.CompareTo(pivot_val) <= 0)
            {

                loe.Add(i);
                Console.WriteLine("loe.add " + i.ToString());
            }
            else
            {
                gt.Add(i);
                Console.WriteLine("gt.add " + i.ToString());
            }
        }
...