quicksort

Question

Hallo, ich bin neu in diesem Forum.

Bisher prog. ich in vb.net. Nun probiere ich mich in C#. Ich versuche schon längere Zeit den angeschlossen Code zum Laufen zu brigen. Der Code erklärt sich von selbst. Kann mir jemand helden. Ich komme nicht in die Rutine Quicksort.

    private void btnQuickSort_Click(object sender, EventArgs e)
    {

      string[] sortDaten = new string[10];

      int zz = 0;
      sortDaten[zz++] = "Katze ";
      sortDaten[zz++] = "Hund ";
      sortDaten[zz++] = "Br ";
      sortDaten[zz++] = "Wolf ";
      sortDaten[zz++] = "Adler ";

      listBox1.Items.Clear();

      for (zz = 1; zz < 6; zz++)
          listBox1.Items.Add(" -> " + sortDaten[zz]);
          //????? was mache ich hier falsch ???????????????????????????????????
      QuickSort(sortDaten, zz, List);
          //??????????????????????????????????????????????????????????????????? 
            listBox1.Items.Add("-------- sortiert zurck -----------");

            for (zz = 1; zz < 6; zz++)

        listBox1.Items.Add(" --> " + sortDaten[zz]);
        MessageBox.Show(" END ", " TEST ");
        Application.Exit(); 
    }

    private void QuickSort(string[] sortDaten, int left, int right)
       {
       int i = left, j = right;
       string leftString = sortDaten[i];
       string rightString = sortDaten[j];
       double pivotValue = ((left + right) / 2);
       string middle = sortDaten[Convert.ToInt32(pivotValue)];
       string temp = null;

       while (i <= j)
       {
       while (sortDaten[i].CompareTo(middle) < 0)
       {
       i++;
       leftString = sortDaten[i];
       }
       while (sortDaten[j].CompareTo(middle) > 0)
       {
       j--;
       rightString = sortDaten[j];
       }
       if (i <= j)
       {
       temp = sortDaten[i];
       sortDaten[i++] = sortDaten[j];
       sortDaten[j--] = temp;
       }
       }

       if (left < j) QuickSort(sortDaten, left, j);
       if (i < right) QuickSort(sortDaten, i, right);
       }

Answer 1

Hallo D.,

Also ich da sind ein paar Variablen nicht ganz richtig, aber hauptsächlich liegt es an der Mehrfachbenutzung von "zz".
Zunächst - Dein "List<string>" hat schon eine Sort-Methode, die intern Array.Sort benutzt, die wiederum QuickSort benutzt.

Ich habe Dir aber trotzdem mal ein verbessertes korrigiertes Coding gemacht, was auch richtig sortiert:

using System;
using System.Windows.Forms;

namespace DeinQuickSortNamensraum
{
 public partial class Form1 : Form
 {
 public Form1()
 {
 InitializeComponent();

 }

 private void btnQuickSort_Click(object sender, EventArgs e)
 {
 string[] sortDaten = new string[]{
 "Katze ", "Hund ", "Br ", "Wolf ", "Adler "};

 listBox1.Items.Clear();

 for (int zz = 0; zz < sortDaten.Length; zz++)
 listBox1.Items.Add(" -> " + sortDaten[zz]);

 QuickSort(sortDaten, 0, sortDaten.Length - 1);

 listBox1.Items.Add("-------- sortiert zurck -----------");

 for (int zz = 0; zz < sortDaten.Length; zz++)
 listBox1.Items.Add(" --> " + sortDaten[zz]);

 MessageBox.Show(" END ", " TEST ");
 //Application.Exit();
 }

 private void QuickSort(string[] sortDaten, int left, int right)
 {
 int i = left, j = right;
 string leftString = sortDaten[i];
 string rightString = sortDaten[j];
 double pivotValue = ((left + right) / 2);
 string middle = sortDaten[Convert.ToInt32(pivotValue)];
 string temp = null;

 while (i <= j)
 {
 while (sortDaten[i].CompareTo(middle) < 0)
 {
  i++;
  leftString = sortDaten[i];
 }
 while (sortDaten[j].CompareTo(middle) > 0)
 {
  j--;
  rightString = sortDaten[j];
 }
 if (i <= j)
 {
  temp = sortDaten[i];
  sortDaten[i++] = sortDaten[j];
  sortDaten[j--] = temp;
 }
 }

 if (left < j) QuickSort(sortDaten, left, j);
 if (i < right) QuickSort(sortDaten, i, right);
 }
 }
}

---

ciao Frank

Answer 2

Hallo d

nur zur Vollständigkeit wenn es dir ausschliesslich ums sortieren per QS ginge, gemäss
Array.Sort
http://msdn.microsoft.com/de-de/library/6tf1f0bc.aspx
 "Diese Methode verwendet den QuickSort-Algorithmus"

würde dies ein Einzeiler sein:

string [] sortDaten = new string[] { "Katze", "Ziege", "Hund", "Baer", "Wolf", "Adler"};
Array.Sort(sortDaten);

Answer 3

Deine Quicksort-Methode erwartet eine typisierte Liste. Du willst ein Array

übergeben. Da meldet schon der Compiler, dass die Typen nicht passen. Hier

mal eine Konsolendemo:

 

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

List<string> sortDaten = new List<string>();

sortDaten.Add("Katze ");

sortDaten.Add("Hund ");

sortDaten.Add("Br ");

sortDaten.Add("Wolf ");

sortDaten.Add("Adler ");

 

QuickSort(sortDaten, 0, sortDaten.Count - 1);

 

for (int i = 0; i < sortDaten.Count; i++)

Console.WriteLine(sortDaten[i]);

 

Console.WriteLine("--- Exit, press any key.");

Console.ReadKey();

}

 

private static void QuickSort(List<string> sortDaten, int left, int

right)

{

int i = left;

int j = right;

string leftString = sortDaten[i];

string rightString = sortDaten[j];

double pivotValue = ((left + right) / 2);

string middle = sortDaten[Convert.ToInt32(pivotValue)];

string temp = null;

while (i <= j)

{

while (sortDaten[i].CompareTo(middle) < 0)

{

i++;

leftString = sortDaten[i];

}

while (sortDaten[j].CompareTo(middle) > 0)

{

j--;

rightString = sortDaten[j];

}

if (i <= j)

{

temp = sortDaten[i];

sortDaten[i++] = sortDaten[j];

sortDaten[j--] = temp;

}

}

if (left < j) { QuickSort(sortDaten, left, j); }

if (i < right) { QuickSort(sortDaten, i, right); }

}

}

}

 

--

Viele Grüße

Peter

 

 

Answer 4

d,
und für den List<string> Fall entsprechend etwa wie:
List<T>.Sort-Methode
http://msdn.microsoft.com/de-de/library/b0zbh7b6.aspx
 "Diese Methode verwendet Array.Sort, das wiederum den QuickSort-Algorithmus verwendet"

List<string> sortDaten = new List<string>(new string[] { "Katze", "Ziege", "Hund", "Baer", "Wolf", "Adler"});
sortDaten.Sort();

Answer 5

Hallo Thomas,

Du schriebst:

 List<string> sortDaten = new List<string>(new string[] { "Katze", "Ziege", "Hund", "Baer", "Wolf", "Adler"});

nebenbei ... das "new string[]" braucht man in dem Fall nicht, bzw. man kann es kürzer schreiben:

 List<string> sortDaten = new List<string> { "Katze ", "Hund ", "Br ", "Wolf ", "Adler " };

[Objekt- und Auflistungsinitialisierer (C#-Programmierhandbuch)]
http://msdn.microsoft.com/de-de/library/bb384062.aspx

---

ciao Frank

Answer 6

Hallo Frank,

vielen Dank für die Hilfe. Genau so habe ich es mir vorgestellt.

Ich habe noch viel in C# zu lernen.

Viele Grüße

Georg Martin

Answer 7

Hallo dompfaff23,

Schau Dir mal auch folgendes Beispiel an. Es zeigt Dir die Sortierung mithilfe von LINQ.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;


namespace WindowsFormsApplication1
{
  public partial class Form1 : Form
  {
    public Form1()
    {
      InitializeComponent();
    }

    private void btnQuickSort_Click(object sender, EventArgs e)
    {

      string[] sortDaten = new string[] { "Katze ","Hund ","Br ","Wolf ","Adler "};

      listBox1.Items.Clear();

      for (int zz = 0; zz < sortDaten.Length; zz++)

        listBox1.Items.Add(" -> " + sortDaten[zz]);

      
      listBox1.Items.Add("-------- sortiert zurück -----------");
      
      string[] sortierterString = SortLINQ(sortDaten);

      for (int zz = 0; zz < sortierterString.Length; zz++)

        listBox1.Items.Add(" --> " + sortierterString[zz]);

      MessageBox.Show(" END ", " TEST ");

      //Application.Exit(); 

    }

    private string[] SortLINQ(string[] data)
    {

      string[] retVal = (from val in data orderby val ascending select val).ToArray();

      return retVal;

    }

  }
}

 

Schau Dir mal auch die folgenden Links an. Vielleicht können sie Dir mit Infos auch noch weiter helfen.

Algorithms in C#: quick sort (part one)

Algorithms in C#: quick sort (part two)

Algorithms in C#: quick sort (part three)

Grüße,

Robert

Answer 8

Hallo Robert,

       > orderby val ascending

wobei man das "ascending" auch weglassen kann, denn "orderby" sortiert standardmäßig aufsteigend (ascending):

Weil wir nun schon mal dabei sind ... noch ein anderer Hinweis. Mit:

   listBox1.Sorted = true;

... könnte man sich ggf. das ganze Sortieren auch sparen - und intern wird dann auch mit einem QuickSort sortiert.

 

---

ciao Frank