[Løst] Sortere en liste ved hjelp av Binary Search Tree

[nwinger]

Hei,

 

Sliter med en oppgave her på skolen. (Jeg nevner med en gang at jeg ikke ute etter et konkret svar, men snarere noen hint i riktig retning)

Med følgende utgangspunkt skal jeg sortere en gitt liste:

import java.util.ArrayList;
import java.util.List;

public class Sorter<T extends Comparable> {

   /**
   * Sort a list using a binary search tree.
   * @param list the list to be sorted
   * @return a sorted list with the same elements
   * as the parameter list
   */
   public List<T> sort(List<T> list) {
   }


   public static void main(String[] args) {
       Sorter<Integer> s = new Sorter<Integer>();
       List<Integer> l = new ArrayList<Integer>();
       l.add(5);
       l.add(2);
       l.add(3);
       l.add(9);
       l.add(8);
       l.add(4);
       l.add(7);
       l.add(6);
       l.add(1);
       l.add(10);

       s.sort(l);
       for (int i : l) System.out.print(" "+i);
       System.out.println();
   }
}

 

Metoden sort skal bruke et binært søketre til å sortere dataene. (Jeg har forøvrig skrevet en BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> implements SearchTree<E> klasse, samt BinaryTree og SearchTree.

Mulig det har blitt for mye glaning på skjermen i dag, men jeg klarer ikke helt å se hvordan dette skal gjøres. Håper noen der ute kan hinte meg i riktig retning!

 

Under følger BinarySearchTree og BinaryTree:

import java.io.*;
import java.util.*;

/**
* BinarySearchTree.
*/
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> implements SearchTree<E> {
   // data fields
   /*
    * Return value from the public add method
    */
   protected boolean addReturn;
   /*
    * Return value from the public delete method
    */
   protected E deleteReturn;

   /*
    * Starter method add
    * pre: The object to insert must implement the Comparable interface
    * @param ittem The object being inserted
    * @return true if the object is inserted, false if the object already
    * exists in the tree
    */
   public boolean add(E item) {
       root = add(root, item);
       return addReturn;
   }

   /*
    * Recursive add method
    * post: The data field addReturn is set true if the item is added to the
    * tree, false if the item is already in the tree.
    * @param localRoot The local root of the subtree
    * @param item The object to be inserted
    * @return The new local root that now contains the inserted item
    */
   private Node<E> add(Node<E> localRoot, E item) {
       if (localRoot == null) {
           // item is not in the tree ÔøΩ insert it.
           addReturn = true;
           return new Node<E>(item);
       } else if (item.compareTo(localRoot.data) == 0) {
           // item is equal to localRoot.data
           addReturn = false;
           return localRoot;
       } else if (item.compareTo(localRoot.data) < 0) {
           // item is less than localRoot.data
           localRoot.left = add(localRoot.left, item);
           return localRoot;
       } else {
           // item is greater than localRoot.data
           localRoot.right = add(localRoot.right, item);
           return localRoot;
       }
   }


   public boolean contains(E target) {
       throw new UnsupportedOperationException("Not supported yet.");
   }

   /*
    * Starter method find.
    * pre: The target object must implement the Comparable interface
    * @param target The Comparable object being sought
    * @return The object, if found, otherwise null
    */
   public E find(E target) {
       return find(root, target);
   }
   /*
    * Recursive find method
    * @param localRoot The local subtree's root
    * @param target The object being sought
    * @return The object, if found, otherwise null
    */
   private E find(Node<E> localRoot, E target) {
       if (localRoot == null) {
           return null;
       }

       // Compare the target with the data field at the root.
       int compResult = target.compareTo(localRoot.data);
       if (compResult == 0) {
           return localRoot.data;
       } else if (compResult < 0) {
           return find(localRoot.left, target);
       } else {
           return find(localRoot.right, target);
       }
   }

   /*
    * Starter method delete
    * post: The object is not in the tree.
    * @param target The object to be deleted
    * @return The object deleted from the tree
    * or null if the object was not in the tree
    * @thros ClassCastException if target does not implement Comparable
    */
   public E delete(E target) {
       root = delete(root, target);
       return deleteReturn;
   }

   /*
    * Recurseive delete method.
    * post: The item is not in the tree;
    * deleteReturn is equal to the deleted item
    * as it was stored in the tree or null if the item was not found.
    * @param localRoot The root of the current subtree
    * @param item The item to be deleted
    * @return The modified local root that does not contain the item
    */
   private Node<E> delete(Node<E> localRoot, E item) {
       if(localRoot == null) {
           // item is not in the tree
           deleteReturn = null;
           return localRoot;
       }

       // Search for item to delete
       int compResult = item.compareTo(localRoot.data);
       if(compResult < 0) {
           // Item is smaller than localRoot.data
           localRoot.left = delete(localRoot.left, item);
           return localRoot;
       } else if(compResult > 0) {
           // item is larger than localRoot.data
           localRoot.right = delete(localRoot.right, item);
           return localRoot;
       } else {
           // item is at localRoot
           deleteReturn = localRoot.data;
           if(localRoot.left == null) {
               // If there is no left child, return right child
               // which can also be null
               return localRoot.right;
           } else if (localRoot.right == null) {
               // If there is no right child, return left child
               return localRoot.left;
       } else {
               // Node being deleted has 2 children, replace the data
               // with inorder predecessor
               if(localRoot.left.right == null) {
                   // The left child has no right child
                   // Replace the data with the data in the left child
                   localRoot.data = localRoot.left.data;
                   // Replace the left child with its left child.
                   localRoot.left = localRoot.left.left;
                   return localRoot;
               } else {
                   // search for the inorder predecessor (ip) and
                   // replace deleted node's data with ip.
                   localRoot.data = findLargestChild(localRoot.left);
                   return localRoot;
               }
           }
       }
   }

   /*
    * Find the node that is the
    * inorder predeceessor and replace it
    * with its left child (if any)
    * post: The inorder predecessor is removed from the tree
    * @param parent The parent of possible inorder predecessor (ip)
    * @return The data in the ip
    */

   private E findLargestChild(Node<E> parent) {
       // If the right child has no right child, it is the
       // inorder predecessor.
       if(parent.right.right == null) {
           E returnValue = parent.right.data;
           parent.right = parent.right.left;
           return returnValue;
       } else {
           return findLargestChild(parent.right);
       }
   }

   public boolean remove(E target) {
       throw new UnsupportedOperationException("Not supported yet.");
   }

}

 

import java.io.*;
import java.util.Scanner;

/**
* BinaryNode class
* Elements to be stored in a tree.
*/

public class BinaryTree<E> implements Serializable {

   protected static class Node<E> implements Serializable {
       // Data fields

       /** The information stored in this node */
       protected E data;
       /** Reference to the left child */
       protected Node<E> left;
       /** Reference to the right child */
       protected Node<E> right;

       // Constructors
       /**
        * Constructs a node with given data and no children.
        * @param data The data to store in this node
        */
       public Node(E data) {
           this.data = data;
           left = null;
           right = null;
       }

       // Methods

       /**
        * Return a string representation of the node.
        * @return A string representation of data fields.
        */
       @Override
       public String toString() {
           return data.toString();
       }

   } // end BinaryNode (Nested class)

   // Data fields
   protected Node<E> root;

   // Constructors
   public BinaryTree() {
       root = null;
   }

   protected BinaryTree(Node<E> root) {
       this.root = root;
   }

   /*
    * Constructs a new binary tree with data in its root,
    * leftTree as its left subtree and rightTree as its right subtree.
    */
   public BinaryTree(E data, BinaryTree<E> leftTree, BinaryTree<E> rightTree) {
       root = new Node<E>(data);
       if(leftTree != null) {
           root.left = leftTree.root;
       } else {
           root.left = null;
       }

       if(rightTree != null) {
           root.right = rightTree.root;
       } else {
           root.right = null;
       }
   }

   /**
    * Return the left subtree
    * @return The left subtree or null if either the root or the left subtree
    * is null.
    */
   public BinaryTree<E> getLeftSubTree() {
       if(root != null && root.left != null) {
           return new BinaryTree<E>(root.left);
       } else {
           return new BinaryTree<E> (null);
       }
   }
   /**
    * Return the right subtree
    * @return The right subtree or null if either the root or the right subtree
    * is null.
    */
   public BinaryTree<E> getRightSubTree() {
       if(root != null && root.right != null) {
           return new BinaryTree<E>(root.right);
       } else {
           return new BinaryTree<E> (null);
       }
   }

   /**
    * Determine whether this tree is a leaf.
    * @return true if the root has no children
    */
   public boolean isLeaf() {
       return root == null || (root.left == null && root.right == null);
       }

   @Override
   public String toString() {
       StringBuilder sb = new StringBuilder();
       //inOrderTraverse(root, 1, sb);
       preOrderTraverse(root, 1, sb);
       return sb.toString();
   }

   /*
    * Perform a preorder traversal
    * @param node The local root
    * @param depth The depth
    * @param sb The string buffer to save the output
    */
   private void preOrderTraverse(Node<E> node, int depth, StringBuilder sb) {
       for(int i = 1; i < depth; i++) {
           sb.append(" ");
       }
       if(node == null) {
           sb.append("null\n");
       } else {
           sb.append(node.toString());
           sb.append("\n");
           preOrderTraverse(node.left, depth + 1, sb);
           preOrderTraverse(node.right, depth + 1, sb);
       }
   }

   /**
    *
    * Perform an inorder traversal
    * @param node The local root
    * @param depth The depth
    * @param sb The string buffer to save the output
    */
   private void inOrderTraverse(Node<E> node, int depth, StringBuilder sb) {
       for(int i = 1; i < depth; i++) {
           sb.append(" ");
       }
       if(node == null) {
           sb.append("\n");
       } else {
           inOrderTraverse(node.left, depth + 1, sb);
           sb.append(node.toString());
           sb.append("\n");
           inOrderTraverse(node.right, depth + 1, sb);
       }
   }

   /**
    * Method to read a binary tree
    * pre: The input consists of a preorder traversal of the
    * binary tree. The line "null" indicates a null tree.
    * @param scan the Scanner attached to the input file
    * @return The binary tree
    */
   public static BinaryTree<String> readBinaryTree(Scanner scan) {
       // Read a line and trim leading and trailing spaces
       String data = scan.next();
       if(data.equals("null")) {
           return null;
       } else {
           BinaryTree<String> leftTree = readBinaryTree(scan);
           BinaryTree<String> rightTree = readBinaryTree(scan);
           return new BinaryTree<String>(data, leftTree, rightTree);
       }
   }
}

Endret 1. mars 2011 av nwinger

[ti-guru]

Hei!

 

Så at du har løst oppgaven din, men kunne ikke la være å komme med noen tanker som kanskje kan komme til nytte senere. Når du sorterer lister er det viktig å gjøre seg noen tanker rundt forventet kjøretid for algoritmen du velger. I innlegget ditt valgte du å bruke et (ubalansert) binært tre. Her er verste kjøretid O(n^2), noe som ikke er optimalt. Dersom du vil gjøre sorteringen enda raskere kan du ta en titt på heap-sort med bottom-up oppbygning av heap'en. Her er du garantert en kjøretid i verste tilfelle på O(n*log n), som er langt bedre. Dette er en klar forbedring dersom du skal sortere en milliard elementer!

 

Gitt at du bare skal sortere heltall, så kan du gjøre sorteringen din enda enklere:

 

public class BucketSort {

public static void sort(int[] list) {

	int high = 0;
	int low = 0;

	for(int i = 0; i < list.length; i++) {
		if (list[i] > high) {
			high = list[i];
		} else if (list[i] < low) {
			low = list[i];
		}
	}

	int[] pos = new int[high + 1];
	int[] neg = new int[1 - low];
	int index = 0;

	for(int i = 0; i < list.length; i++) {

		index = list[i];

		if (index < 0) {
			neg[-index] += 1;
		} else {
			pos[index] += 1;
		}
	}

	index = 0;

	for(int i = neg.length - 1; i >= 0; i--) {
		for(int j = 0; j < neg[i]; j++) {
			list[index] = -i;
			index += 1;
		}
	}

	for(int i = 0; i < pos.length; i++) {
		for(int j = 0; j < pos[i]; j++) {
			list[index] = i;
			index += 1;
		}
	}
}

}

 

Legg merke til at denne algoritmen har verste kjøretid på O(n^2), men en gj.snitt kjøretid på O(n)! Dvs at du kan sortere tall i lineær tid...

 

Edit:

Gjorde en rask test på laptopen med 10^7 elementer i listen. Dersom high og low er innenfor list.length, så vil sort kjøre på under halvparten av tiden av java.util.Arrays sin sort-metode. Dersom high og low er langt over list.length (f.eks x100), så vil java.util.Arrays sin sort-metode (en quick sort) være bedre da denne garanterer n*log n kjøring.

Endret 13. mars 2011 av ti-guru

[zotbar1234]

Gitt at du bare skal sortere heltall, så kan du gjøre sorteringen din enda enklere:

 

... gitt at man bare skal sortere forholdsvis små heltall.

 

Legg merke til at denne algoritmen har verste kjøretid på O(n^2) (...)

 

Nei, den har ikke det. Det er trivielt å lage et moteksempel til din implementasjon som vil gjøre det MYE verre enn O(n^2). Verste kjøretid er O(2^(log(k))), der k = max(abs(i)) for alle tall i input. Dvs. gitt at vi skal sortere 32-bits tall, er verste kjøretid proprosjonal med 2^32.

 

(...) men en gj.snitt kjøretid på O(n)! Dvs at du kan sortere tall i lineær tid...

 

Kilde for denne påstanden?

[ti-guru]

Gitt at du bare skal sortere heltall, så kan du gjøre sorteringen din enda enklere:

 

... gitt at man bare skal sortere forholdsvis små heltall.

 

Legg merke til at denne algoritmen har verste kjøretid på O(n^2) (...)

 

Nei, den har ikke det. Det er trivielt å lage et moteksempel til din implementasjon som vil gjøre det MYE verre enn O(n^2). Verste kjøretid er O(2^(log(k))), der k = max(abs(i)) for alle tall i input. Dvs. gitt at vi skal sortere 32-bits tall, er verste kjøretid proprosjonal med 2^32.

 

(...) men en gj.snitt kjøretid på O(n)! Dvs at du kan sortere tall i lineær tid...

 

Kilde for denne påstanden?

 

Se her og her. Ser nå at jeg gjorde en liten feil i gj.snitt kjøretid; skal stå O(n + m), der n er antall elementer og m er høyeste verdien som sorteres. I følge det jeg har lest og egne kjøreresultater, så var tiden avh av at høyeste verdi ikke var større enn antall elementer i arrayen. Når det kommer til verste kjøretid, så viser jeg til wikipedia og læreboka over.

Endret 19. mars 2011 av ti-guru

[zotbar1234]

Det er trivielt å lage et moteksempel til din implementasjon som vil gjøre det MYE verre enn O(n^2). Verste kjøretid er O(2^(log(k))), der k = max(abs(i)) for alle tall i input. Dvs. gitt at vi skal sortere 32-bits tall, er verste kjøretid proprosjonal med 2^32.

 

Denne påstanden holder fremdeles for algoritmen din. Du bruker tid proporsjonal med størrelsen til den største absoluttverdien av de tallene du sorterer. Noe som wikipedia er iofs enig i.

 

Counting sort er en fornuftig strategi kun dersom man sorterer tall innenfor et veldig lite intervall (din implementasjon har en tilleggssvakhet i at den er ute av stand til å sortere veldig store/små tall innad et lite intervall effektivt. Sortering av list = [integer.INT_MAX, Integer.INT_MAX-1, Integer.INT_MAX-2] vil illustrere dette).

 

(...) men en gj.snitt kjøretid på O(n)! Dvs at du kan sortere tall i lineær tid...

 

Kilde for denne påstanden?

 

Se her og her.

 

Ja, men algoritmen din er jo ikke en standard bucket sort! Du bruker det som heter counting sort (og en dårlig implementasjon av det sogar).

 

Bucket sort er lineær i gjennomsnittet, dersom man gjør noen tilleggsantagelser (D. Knuth henviser til et teorem bevist av av M. Tamminen).

 

Ser nå at jeg gjorde en liten feil i gj.snitt kjøretid; skal stå O(n + m), der n er antall elementer og m er høyeste verdien som sorteres.

 

... for bucket sort er det antall buckets, for counting sort -- absoluttverdien av den største verdien, ja. Feilen er ikke "liten" heller, mtp. hva som er den øvre grensen for m.

 

I følge det jeg har lest og egne kjøreresultater, så var tiden avh av at høyeste verdi ikke var større enn antall elementer i arrayen.

 

Der kommer den essensielle antagelsen, ja. Jeg ser ingen slik innskrankning hos OP.

 

Når det kommer til verste kjøretid, så viser jeg til wikipedia og læreboka over.

 

... og verste kjøretiden er O(n+k), der k er proporsjonal med størrelsen på tall man skal sortere (som jeg opprinnelig skrev).

 

Den verste kjøretiden for bucket sort er O(n^2) (takk for å ha poengtert det. Der har jeg lært noe nytt).

 

Kort oppsummert -- algoritmen din er hverken lineær i antall elementer man skal sortere i gjennomsnittet, eller er oppad begrenset av kvadratet av antall elementer man skal sortere i verste fall.

 

	int[] pos = new int[high + 1];
	int[] neg = new int[1 - low];

 

... ødelegger alt i algoritmen din. Allerede der kjører du i O(2^log(max(a))) i verste tilfellet, der a er absoluttverdien til tall du skal sortere.