Bubblesort в общем списке в C #

Question

Я работаю с общим списком в C #, но у меня возникает проблема, когда я пытаюсь отсортировать узлы методом пузырьковой сортировки.

namespace ConsoleApplication1
{    

public class GenericList
{
    private class Node
    {
        // Each node has a reference to the next node in the list.
        public Node Next;           
        public int Data;
    }

    // The list is initially empty.
    private Node head = null;

    // Add a node at the beginning of the list with t as its data value.
    public void AddNode(int t)
    {
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Data = t;
        head = newNode;
    }


//list length
        public int Size()
        {
            int listsize= 0;
            Node current = head;
            while (current != null)
            {
                listsize++;
                current = current.Next;
            }
            return listsize;            
        }

        //bubble sort
        public void bubblesort()
        {
            int size = Size();

            Node current = head;

            for (int i = 1; i < size; i++)
            {
                for (int j = 0; j < size - 1; j++)
                {


                    if (current.Data > current.Next.Data && current.Next!=null)
                    {
                        int temp = current.Data;
                        current.Data = current.Next.Data;
                        current.Next.Data = temp;
                    }

                }
            }

            head = current;
        }
     }
}

Когда я добавляю более 5 узлов в список, метод пузырьковой сортировки перестает работать (неправильно сортирует список). Может ли кто-нибудь помочь мне?

Answer 1

Вам нужно уточнить, что вы подразумеваете под "перестает работать" ... не удается? Core-дампы? Не правильно сортировать список?

Проблема в том, что вам нужно сбрасывать current обратно на head+1 на каждой итерации i (до итерации j).

Если вы хотите переместить наибольшее значение вверх, то j должно увеличиться с 1 до size-i (так как после первого прохода наибольшее число будет наверху - нет необходимости проверять его снова). Или же уменьшите наименьшее значение, запустив j с size-1 до i.

Альтернатива методу вложенного цикла: вы можете использовать метод while / boolean / loop (снаружи while, логическое значение, указывающее, было ли внесено изменение, для внутреннего цикла). Это дает небольшой выигрыш в производительности, когда данные уже в некотором порядке: обработка прекратится перед вложенным методом (который выполняется максимальное количество раз, даже если данные уже отсортированы).

Answer 2

Да ладно, ребята .. ослабьте его .. это поколение Google.

кстати ..

http://www.google.co.uk/search?q=C%23+bubble+sort

.. приведу несколько отличных примеров.

Теперь о том, что на самом деле не так с вашим кодом:

Этот код (сверху)

    Node current = head;

    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {


            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

        }
    }

точно так же, как сказать:

    Node current = head;
            if (current.Data > current.Next.Data && current.Next!=null)
            {
                int temp = current.Data;
                current.Data = current.Next.Data;
                current.Next.Data = temp;
            }

Вы не изменяете «текущий» узел, т. Е. Вы всегда сортируете первый и второй элемент в вашем списке.

Я не дам вам полного решения, для этого и нужна домашняя работа. В цикле убедитесь, что ваш текущий всегда является 'j' -ым элементом в вашем списке, когда он начинается, это внутренний цикл, и вы получите правильные результаты.

Также вы получаете немного неверный бит подкачки, вы должны поменять местами узлы, а не только данные. то есть поле Next узла и то, что указывает на текущий узел, необходимо обновить. Это должно принести вам больше очков, чем просто обмен данными.

Также несколько советов по отладке: добавьте функцию Print () следующим образом:

public void Print()
    {
        Node current = head;
        Console.Write("List: ");
        while (current != null)
        {
            Console.Write("{0} ", current.Data);
            current = current.Next;
        }
        Console.WriteLine("");
    }

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

List: 3 1 50 2 5 4
List: 3 1 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 50 2 5 4
List: 1 3 2 50 5 4
List: 1 3 2 5 50 4
List: 1 3 2 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 5 4 50
List: 1 2 3 4 5 50

Oh! человек .. каждый раз, когда я читаю код, я нахожу что-то новое, что не так! ...

        if (current.Data > current.Next.Data && current.Next!=null)

должно быть

        if (current != null && current.Next!=null && current.Data > current.Next.Data)

Ваш код не дает сбоя, так как в данный момент он ничего не делает.

Надеюсь, это поможет.

Answer 3

Еще один пример с простым классом с 2 свойствами. Это НЕ для массивов, а для простого класса, имитирующего указатели ... Сделано просто для удовольствия!

class MyLinkedList
{
    MyLinkedList nextNode;
    int data;

    public void OrderListBubbleAlgoritm(ref MyLinkedList head)
    {
        bool needRestart = true;
        MyLinkedList actualNode = head; //node Im working with        
        int temp;

        while (needRestart)
        {
            needRestart = false;
            actualNode = head;
            while (!needRestart && actualNode.nextNode != null)
            {
                if (actualNode.nextNode.data >= actualNode.data) //is sorted
                {
                    actualNode = actualNode.nextNode;
                }
                else
                {
                    //swap the data
                    temp = actualNode.data;
                    actualNode.data = actualNode.nextNode.data;
                    actualNode.nextNode.data = temp;

                    needRestart = true;
                }
            }
        }
    }
 }

Не забудьте использовать пузырьковую сортировку только с небольшим количеством данных.
Это производительность: O (n ^ 2)

Answer 4

У вас есть два вложенных цикла, объявляющих переменные i и j, но вы никогда не используете их внутри циклов. Это, очевидно, неправильно.

for (int i = 1; i < size; i++)
{
    for (int j = 0; j < size - 1; j++)
    {

То, что вы должны сделать, - это перебрать список с помощью цикла while, как вы делаете это в методе Size, и поменять местами соседние элементы, если они обратные. В bool вы будете отслеживать, действительно ли вы выполняли какие-либо перестановки, и, если это так, снова просматривать список. Это будет повторяться до тех пор, пока вы не выполните никаких перестановок.

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