C#의 일반 목록에있는 Bubblesort

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 개 이상의 노드를 추가하면 bubblesort 메서드가 작동을 멈추고 (올바르게 정렬되지 않습니다). 아무도 도와 줄 수 있습니까?

Answer 1

"작업 중지"가 의미하는 바를 분명히해야합니다 ... 실패합니까? 코어 덤프? 목록을 올바르게 정렬하지 않습니까?

문제는 당신이합니다 (j 반복 이전에) 다시 head+1-i의 각 반복에 current를 재설정 할 필요가있다. (- 필요 다시 확인하지 않으려면 후 첫 번째 가장 큰 숫자는 상단에있을 것입니다 통과 이후)

당신이 가장 큰 값을 위로 이동하려는 경우, j는 size-i에 1로부터 실행해야합니다. 또는 가장 작은 값을 j을 실행하여 size-1에서 i으로 낮추십시오.

중첩 루프 메소드의 대안 : while/boolean/loop 메소드를 사용할 수 있습니다 (변경 사항이 있는지 여부를 나타내는 부울 값, 내부 루프의 경우 부울 값). 데이터가 이미 다소 순서가 맞으면 약간의 성능 이점이 있습니다. 데이터가 이미 정렬되어 있어도 최대 횟수 실행되는 중첩 된 메서드보다 먼저 처리가 중단됩니다.

Answer 2

i 및 j을 선언하는 두 개의 중첩 루프가 있지만 루프 내에서 절대로 사용하지 마십시오. 그건 분명히 틀린 것 같습니다. 그들이 뒤로 경우 당신이 무엇을해야

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

당신이 Size 방법에서하고있는 것처럼, while 루프를 사용하여 목록을 반복하고, 스왑 인접한 요소입니다. 실제로 스왑을 수행했는지 여부를 bool에서 추적 할 수 있으며, 그렇다면 목록을 다시 반복합니다. 이것은 스왑을 수행하지 않을 때까지 반복됩니다.

이것은 실제로 과제의 요구 사항을 충족시키기 위해 버블 정렬을 구현해야한다고 가정합니다. 그렇지 않으면 프레임 워크의 기본 제공 컬렉션 유형 및 정렬 방법보다 더 선호 할 이유가 없습니다.

Answer 3

어이 남자들 .. 그에게 약간의 여유를 줄여라. 이것은 구글 세대 다.

BTW ..

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

은 당신에게 훌륭한 예를 얻을 수 ..would. 코드에 실제로 무엇이 잘못되었는지에 대한 지금

:

이

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; 
      } 

당신은 변경하지 마십시오 : (위에서)

이 코드

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; 
      } 

     } 
    } 

는 말을 정확히 동일합니다 "현재"노드입니다. 즉, 항상 목록에서 첫 번째와 두 번째 항목을 정렬합니다.

나는 숙제가 무엇인지에 대한 완벽한 해결책을주지 않습니다. 루프에서 내부 루프가 시작될 때 항상 현재 항목이 목록의 'j'번째 항목인지 확인하고 올바른 결과를 얻습니다.

또한 스와핑 비트가 약간 잘못되어 있으므로 노드뿐만 아니라 데이터를 바꿔야합니다. 즉 노드의 다음 필드와 현재 노드를 업데이트해야하는 포인트의 수를 나타냅니다. 그렇게하면 데이터를 바꾸는 것보다 브라우니 포인트가 더 많이 생깁니다.

또한 디버깅 팁 :이 같은 인쇄() 함수를 추가

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 

오! 남자 .. 내가 코드를 읽을 때마다 나는 새로운 것을 발견했다! ...

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

는 순간 아무것도하지 않는

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

당신의 코드가 충돌하지 않는해야합니다.

희망이 도움이됩니다.

Answer 4

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)