(Java) Schnell Art ein Zahlen char Paare von Nummer zu sortieren dann

Question

ersten, char I der Algorithmus hier geändert habe: http://www.algolist.net/Algorithms/Sorting/Quicksort

mit meiner Node Klasse umgehen:

public class Node 
{ 
    public int frequency; 
    public char value; 
} 

Grundsätzlich Es sollte zuerst nach der Frequenz sortiert werden. Wenn die Frequenzen gleich sind, sehen Sie sich den char-Wert an.

Dies ist mein Code:

public static int partition(Node arr[], int left, int right) 
{ 
     int i = left, j = right; 
     Node tmp; 
     int pivot = (left + right)/2; 

     while (i <= j) { 
      while (arr[i].frequency < arr[pivot].frequency) 
        i++; 
      while (arr[j].frequency > arr[pivot].frequency) 
        j--; 
      if (i <= j) { 

       if (arr[i].frequency == arr[j].frequency) 
       { 
        if (arr[i].value > arr[j].value) 
        { 
         tmp = arr[i]; 
         arr[i] = arr[j]; 
         arr[j] = tmp;       
        } 
       } 
       else //(arr[i].frequency > arr[j].frequency) 
       { 
        tmp = arr[i]; 
        arr[i] = arr[j]; 
        arr[j] = tmp;       
       } 

       i++; 
       j--; 
      } 
     }; 

     return i; 
} 

public static void quickSort(Node arr[], int left, int right) { 
     int index = partition(arr, left, right); 
     if (left < index - 1) 
      quickSort(arr, left, index - 1); 
     if (index < right) 
      quickSort(arr, index, right); 
} 

Gerade jetzt ist es tut Arbeit, aber es verpasst einen Brief ab und zu. Nur um es richtig funktionieren zu lassen.

Jede Hilfe wird geschätzt!

Danke.

EDIT: Vielen Dank an alle, die geantwortet haben! Ich benutzte den Vergleichswert. Es ist jetzt sehr gut sortiert.

Answer 1

hier 5 Weg, dies zu tun (man mehr hinzufügen):
als diese http://www.algolist.net/Algorithms/Sorting/Quicksort
sagte + Code mit einigen edit:

package AR; 

class Node { 
    public int frequency; 
    public char value; 

    public Node(int frequency, char value) { 
     this.frequency = frequency; 
     this.value = value; 
    } 
} 

final class Sort { 

    int partition(Node arr[], int left, int right) { 
     int i = left, j = right; 
     Node tmp; 
     Node pivot = arr[(left + right)/2]; 

     while (i <= j) { 
      while (i <= j && (arr[i].frequency < pivot.frequency || (arr[i].frequency == pivot.frequency && arr[i].value < pivot.value))) 
       i++; 
      while (i <= j && (arr[j].frequency > pivot.frequency || (arr[j].frequency == pivot.frequency && arr[j].value > pivot.value))) 
       j--; 
      if (i <= j) { 
       tmp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = tmp; 
       i++; 
       j--; 
      } 
     } 
     return i; 
    } 

    public void quickSort(Node arr[], int left, int right) { 
     if (left > right) return; 
     int index = partition(arr, left, right); 
     if (left < index - 1) 
      quickSort(arr, left, index - 1); 
     if (index < right) 
      quickSort(arr, index, right); 
    } 
} 

final class Main { 
    public static void main(String[] args) { 

     Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')}; 
     int n = ns.length; 
     Sort cl = new Sort(); 
     cl.quickSort(ns, 0, n - 1); 
     for (int i = 0; i < n; i++) { 
      System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), "); 
      //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c), 
     } 
    } 
} 

// in @ Debosmit Ray Art und Weise: (nur int T aus) unter Verwendung von Generics in Java ::

package AR; 

class Node implements Comparable<Node> { 
    public int frequency; 
    public char value; 

    public Node(int frequency, char value) { 
     this.frequency = frequency; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Node o) { 
     if (this.frequency > o.frequency) return 1; 
     if (this.frequency < o.frequency) return -1; 
     if (this.value > o.value) return 1; 
     if (this.value < o.value) return -1; 
     return 0; 
    } 
} 

final class Sort<T extends Comparable<T>> { 

    int partition(T arr[], int left, int right) { 
     int i = left, j = right; 
     T tmp; 
     T pivot = arr[(left + right)/2]; 

     while (i <= j) { 
      while (i <= j && arr[i].compareTo(pivot) < 0) 
       i++; 
      while (i <= j && arr[j].compareTo(pivot) > 0) 
       j--; 
      if (i <= j) { 
       tmp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = tmp; 
       i++; 
       j--; 
      } 
     } 
     return i; 
    } 

    public void quickSort(T arr[], int left, int right) { 
     if (left > right) return; 
     int index = partition(arr, left, right); 
     if (left < index - 1) 
      quickSort(arr, left, index - 1); 
     if (index < right) 
      quickSort(arr, index, right); 
    } 
} 

final class Main { 
    public static void main(String[] args) { 

     Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')}; 
     int n = ns.length; 
     Sort cl = new Sort(); 
     cl.quickSort(ns, 0, n - 1); 
     for (int i = 0; i < n; i++) { 
      System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), "); 
      //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c), 
     } 
    } 
} 

// Ort schwenken in der linken Seite des Arrays, ein d in einer Schleife, wie dies vergleichen:

package AR; 

class Node { 
    public int frequency; 
    public char value; 
    public Node(int frequency, char value) { 
     this.frequency = frequency; 
     this.value = value; 
    } 
} 
final class Main { 
    static int partition(Node[] arr, int left, int right) { 
     int i = left+1, j = right; 
     Node tmp; 
     int pivot = left ; 
     while (i <= j) { 
      while (i <= j && (arr[i].frequency < arr[pivot].frequency || (arr[i].frequency == arr[pivot].frequency && arr[i].value <= arr[pivot].value))) 
       i++; 
      while (i <= j && (arr[j].frequency > arr[pivot].frequency || (arr[j].frequency == arr[pivot].frequency && arr[j].value > arr[pivot].value))) 
       j--; 
      if (i > j) break; 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
     } 
     tmp = arr[pivot]; 
     arr[pivot] = arr[j]; 
     arr[j] = tmp; 
     return j; 
    } 
    public static void quickSort(Node arr[], int left, int right) { 
     if (left >= right) return; 
     int i = partition(arr, left, right); 
     quickSort(arr, left, i - 1); 
     quickSort(arr, i + 1, right); 
    } 
    public static void main(String[] args) { 
     Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(0, 'z'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(1, 'z')}; 
     int n = ns.length; 
     quickSort(ns, 0, n - 1); 
     for (int i = 0; i < n; i++) { 
      System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), "); 
      //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,b), 
     } 
    } 
} 

// @ Debosmit Ray Art und Weise sehr schön zu vergleichen ist, und es vereinfacht den Code:

package AR; 
class Node implements Comparable<Node> { 
    public int frequency; 
    public char value; 
    public Node(int frequency, char value) { 
     this.frequency = frequency; 
     this.value = value; 
    } 
    @Override 
    public int compareTo(Node o) { 
     if (this.frequency > o.frequency) return 1; 
     if (this.frequency < o.frequency) return -1; 
     if (this.value > o.value) return 1; 
     if (this.value < o.value) return -1; 
     return 0; 
    } 
} 
final class Main { 
    static void swap(Node[] arr, int i, int j) { 
     Node temp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = temp; 
    } 
    static int partition(Node[] arr, int left, int right) { 
     int i = left; 
     Node pivot = arr[left++]; 
     while (left <= right) { 
      while (left <= right && arr[left].compareTo(pivot) <= 0) left++; 
      while (left <= right && arr[right].compareTo(pivot) > 0) right--; 
      if (left > right)break; 
      swap(arr, left++, right--); 
     } 
     swap(arr, i, right); 
     return right; 
    } 
    public static void quickSort(Node arr[], int left, int right) { 
     if (left >= right) return; 
     int i = partition(arr, left, right); 
     quickSort(arr, left, i - 1); 
     quickSort(arr, i + 1, right); 
    } 
    public static void main(String[] args) { 

     Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')}; 
     int n = ns.length; 
     quickSort(ns, 0, n - 1); 
     for (int i = 0; i < n; i++) { 
      System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), "); 
      //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,b), 
     } 
    } 
} 

// Verwendung von Generics in Java:

package AR; 

class Node implements Comparable<Node> { 
    public int frequency; 
    public char value; 

    public Node(int frequency, char value) { 
     this.frequency = frequency; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Node o) { 
     if (this.frequency > o.frequency) return 1; 
     if (this.frequency < o.frequency) return -1; 
     if (this.value > o.value) return 1; 
     if (this.value < o.value) return -1; 
     return 0; 
    } 
} 

final class Sort<T extends Comparable<T>> { 
    void swap(T[] arr, int i, int j) { 
     T temp = arr[i]; 
     arr[i] = arr[j]; 
     arr[j] = temp; 
    } 

    int partition(T[] arr, int left, int right) { 
     int i = left; 
     T pivot = arr[left++]; 
     while (left <= right) { 
      while (left <= right && arr[left].compareTo(pivot) <= 0) left++; 
      while (left <= right && arr[right].compareTo(pivot) > 0) right--; 
      if (left > right) break; 
      swap(arr, left++, right--); 
     } 
     swap(arr, i, right); 
     return right; 
    } 

    public void quickSort(T arr[], int left, int right) { 
     if (left >= right) return; 
     int i = partition(arr, left, right); 
     quickSort(arr, left, i - 1); 
     quickSort(arr, i + 1, right); 
    } 

} 

final class Main { 
    public static void main(String[] args) { 

     Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')}; 
     int n = ns.length; 
     Sort cl = new Sort(); 
     cl.quickSort(ns, 0, n - 1); 
     for (int i = 0; i < n; i++) { 
      System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), "); 
      //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c), 
     } 
    } 
} 

Answer 2

Der Kommentar hier ist nicht wahr:

  else //(arr[i].frequency > arr[j].frequency) 

Die if-Zweig überprüft, ob die Frequenzen gleich sind, so in der sonst müssen Sie noch überprüfen, ob sie vor dem Vertauschen sie in der richtigen Reihenfolge sind.

Ich würde vorschlagen, eine separate Funktion zum Vergleichen von Knoten zu schreiben.

Answer 3

Ich schlage vor, Sie bewegen sich im Vergleich 2 Node Objekte auf eine andere Methode, oder machen Node vergleichbar. Ich werde hier die zweite Möglichkeit demonstrieren.

public class Node implements Comparable<Node> { 
    public int frequency; 
    public char value; 

    @Override 
    public int compareTo(Node o) { 
     if(this.frequency < o.frequency) 
      return -1; 
     else if(this.frequency > o.frequency) 
      return 1; 
     else { 
      if(this.value < o.value) 
       return -1; 
      else if(this.value > o.value) 
       return 1; 
      return 0; 
     } 
    } 
} 

Statt nun sowohl die Felder zu überprüfen, während ein Vergleich für die schnelle Art zu tun, können Sie einfach so etwas wie if(arr[i].compareTo(arr[j]) < 0 tun. Lassen Sie mich wissen, ob das hilft. Wenn nicht, kann ich mit etwas mehr Code helfen.

Zum Sortieren würde ich vorschlagen Arrays.sort(arr), jetzt, dass Sie Ihre Comparable implementiert haben. Bearbeiten. Für Arrays von Primitiven in Java verwendet diese Funktion ein Dual-Pivot-Quicksort, was ziemlich cool ist. Für Arrays von Objekten wird TimSort verwendet.[docs] [TimSort vs QuickSort]