Сортировка массива чисел

Question

Вчера на работе я решил выяснить, как сортировать числа без использования библиотечного метода Array.Sort. Я работал и выключался, когда позволяло время, и, наконец, смог придумать основной алгоритм работы в конце сегодняшнего дня. Это может быть довольно глупо и самым медленным способом, но я доволен, что у меня есть рабочий код.

Но в логике что-то не так или отсутствует, что приводит к зависанию вывода перед печатью строки: Numbers Sorted. (12/17/2011 2:11:42 AM)

Эта задержка прямо пропорциональна количеству элементов в массиве. Чтобы быть точным, вывод просто висит на позиции, где я положил тильду в разделе результатов ниже. Содержание после тильды печатается после этой заметной задержки.

Вот код, который выполняет сортировку:

while(pass != unsortedNumLen)
{
    for(int i=0,j=1; i < unsortedNumLen-1 && j < unsortedNumLen; i++,j++)
    {
        if (unsorted[i] > unsorted[j])
        {
            pass = 0;
            swaps++;
            Console.Write("Swapping {0} and {1}:\t", unsorted[i], unsorted[j]);
            tmp = unsorted[i];
            unsorted[i] = unsorted[j];
            unsorted[j] = tmp;
            printArray(unsorted);
        }

        else pass++;
    }
}

Результаты:

Numbers unsorted. (12/17/2011 2:11:19 AM)

4 3 2 1
Swapping 4 and 3:       3 4 2 1
Swapping 4 and 2:       3 2 4 1
Swapping 4 and 1:       3 2 1 4
Swapping 3 and 2:       2 3 1 4
Swapping 3 and 1:       2 1 3 4
Swapping 2 and 1:       1 2 3 4
~
Numbers sorted. (12/17/2011 2:11:42 AM)

1 2 3 4
Number of swaps: 6

Можете ли вы помочь определить проблему с моей попыткой?

Ссылка на полный код
Это не домашняя работа, только я работаю.

Answer 1

Измените условие вашего времени на следующее:

while (pass < unsortedNumLen)

Логически pass никогда равно unsortedNumLen, поэтому ваш while не прекратится.

pass в конечном итоге становится равным unsortedNumLen, когда он превышает максимальное значение int и возвращается к нему.

Чтобы увидеть, что происходит самостоятельно, пока он находится в состоянии зависания, простонажмите кнопку паузы в Visual Studio и наведите указатель мыши на pass, чтобы увидеть, что оно содержит огромное значение.

Вы также можете установить точку останова на строке while и добавить часы для pass,Это показало бы, что в первый раз список сортируется, pass равен 5.

Answer 2

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

Измените свой блок else на приведенный ниже и посмотрите, вернет ли он вас на правильный путь.

else {

    Console.WriteLine("Nothing to do for {0} and {1}", unsorted[i], unsorted[j]);
    pass++;
}

Answer 3

Вот исправление:

while(pass < unsortedNumLen)

И вот почему произошла задержка.

После окончания цикла for, в котором массив был в итоге отсортирован, pass содержит не более unsortedNumLen - 2 (если последнее изменение было между первым и вторым членами).Но он не равен длине массива unsorted, поэтому начинается другая итерация while и внутреннего for.Так как массив отсортирован unsorted[i] > unsorted[j] всегда ложно, поэтому pass всегда увеличивается, ровно столько раз, сколько j увеличивается, а это unsortedNumLen - 1.Это не равно unsortedNumLen, и поэтому начинается другая итерация while.Ничего существенно не изменилось, и после этой итерации pass содержит 2 * (unsortedNumLen - 1), который все еще не равен unsortedNumLen.И т. Д.

Когда проход достигает значения int.MaxValue, происходит переполнение, и следующее значение, которое получит переменная pass, равно int.MinValue.И процесс продолжается, пока pass наконец не получит значение unsortedNumLen в момент проверки условия while.Если вам особенно не повезло, это может вообще никогда не произойти.

PS Возможно, вы захотите проверить эту ссылку .

Answer 4

Это просто характеристика алгоритма, который вы используете для сортировки.После завершения сортировки элементов он не может знать, что сортировка завершена, поэтому он делает один последний проход, проверяя каждый элемент снова.Вы можете исправить это, добавив --unsortedNumLen; в конце цикла for следующим образом:

for(int i=0,j=1; i < unsortedNumLen-1 && j < unsortedNumLen; i++,j++)
{
/// existing sorting code
}
--unsortedNumLen;

Причина?Поскольку ваш алгоритм выдает наибольшее значение до конца массива, нет необходимости проверять этот элемент еще раз, поскольку он уже определен как больше всех остальных элементов.