Selection Sort in Liste implementieren

[JoeBo]

Hallo.
Ich hab folgendes Problem, ich will in diese Liste einen Selection Sort implementieren:

class DoubleList { 
  
  class ListNode {  
    
    private String value;
    private ListNode prev;    
    private ListNode next;

    public ListNode(String value, ListNode prev, ListNode next) {
      this.value = value;
      this.prev = prev;
      this.next = next;
      if (next != null) next.prev=this;    
      if (prev != null) prev.next = this;  
    }
    
    public void setPrev(ListNode prev) {
      this.prev = prev;
    }

    public void setNext(ListNode next) {
      this.next = next;
    }
    
    public void setValue(String value) {
      this.value = value;
    }
    
    public ListNode getPrev() {
      return prev;
    }

    public ListNode getNext() {
      return next;
    }
    
    public String getValue() {
      return value;
    }
  }
  
  private ListNode head;
  private ListNode tail;
  
  public DoubleList() {
    head = null;
    tail = null;
  }
  
  public void push_front(String value) {
    head = new ListNode(value, null, head);
    if (tail == null) {  
      tail = head;       
    }
  }
  
  public void push_back(String value) {
    tail = new ListNode(value, tail, null);
    if (head == null) {
      head = tail;
    }
  }      
    
  public ListNode getRoot() {
    return head;
  }
  
  public ListNode getTail() {
    return tail;
  }  
    
  public ListNode pop_front() {
    if (head == null) {
      return null;
    } else {
      ListNode result = head;   
      head = head.getNext();  
      head.setPrev(null); 
      return result;   
    }
  }
  
  public ListNode pop_back() {
    if (tail == null) {
      return null;
    } else {
      ListNode result = tail;
      tail = tail.getPrev();
      tail.setNext(null);
      return result;
    }
  }
  
  public void delete(ListNode node) {
    if(node != null) {
      if (head == node) {     
        head = node.getNext();
      }
      if (tail == node) {
        tail = node.getPrev();     
      }
      if (node.prev != null) {  
        node.getPrev().setNext(node.getNext());
      }
      if (node.next != null) {
        node.next.prev =node.prev; 
      }
    }
  }
    
  public void print() {
    for(ListNode node = head; node != null; node = node.getNext()) {
      System.out.print("(" + node.value + ") ");
    }
    System.out.println();
  }
  
  public int count(){
    int result = 0;
    ListNode node = head;
    while(node != null) {
      node = node.getNext();
      result++;
    }
    return result;
  }

  public ListNode find(String value) {
    for(ListNode node = head; node != null; node = node.next) {
      if (node.getValue().equals(value)) {  
        return node;   
      }
    }
    return null;
  }
}
public class ListExample {
  public static void main(String[] params) {
    DoubleList l = new DoubleList();
    l.push_back("0");
    l.push_back("1");
    l.push_back("2");
    l.push_back("3");
    l.push_back("4");
    l.push_front("5");
    l.push_front("6");
    l.push_front("7");
    l.push_front("8");
    System.out.println(l.count());
    l.print();

    l.delete(l.find("787"));
    l.pop_front();
    l.pop_back();
    l.print();  
  } 
}

Nun hab ich mehrere Ideen wie ich den Selection Sort implementieren kann aber irgendwie funktioniert keine so richtig.

Swap Methode:

public void swap(ListNode node1, ListNode node2){
  	ListNode tmp = node1;
  	node1 = node2;
  	node2 = tmp;
  }

Selection Sort Idee:

 public void SelectionSort(){
		for(ListNode node = head; node != tail; node=node.next){
			ListNode min = new ListNode(node.getValue(), node.getPrev(), node.getNext());
			for(ListNode node2 = node.getNext(); node2 != tail; node2=node2.next ){
				if(node2.getValue() < min.getValue())
					node2.setValue(min);
			}
		}
		
 }

oder

 public void SelectionSort(){
		for(ListNode node = head; node != tail; node=node.next){
			int min = node.getValue();
			for(ListNode node2 = node.getNext(); node2 != tail; node2=node2.next ){
				if(node2.getValue() < min)
					node2.setValue(min);
			}
		}
		
 }

Mein Hauptsächliches Problem besteht darin, die Strings mit ein ander zu vergleichen.

Wäre nett wenn ihr mir helfen könntet, langsam bin ich am verzweifeln.

Gruß JoeBo

 

[SlaterB]

nur mit Code lassen sich manche Probleme nicht lösen,

was soll z.B. "min = node2;" bedeuten?
min ist ein int, node2 ein ListNode..

überlege dir erstmal, was überhaupt passieren soll,
und beschreibe dies sauber in der deutschen Sprache, wenn dir Java noch nicht zusagt

 

[JoeBo]

Ich hab mir überlegt was passieren soll, ich wollte einen Selection Sort für meine Liste implementieren. Wie der Selection Sort standartmäßig aussieht weiß ich, nur nicht wie ich ihn auf meine Liste anwenden soll.

So sieht der für eine Array von int aus:

public class SelectionSort {
	
	static void sort(int[] field){
		for(int i1=0;i1< field.length;i1++){
			int min = i1;
			for(int i2=i1+1; i2< field.length;i2++){
				if(field[i2]<field[min])
					min = i2;
			}
			swap(field, min, i1);
		}
	}

    static void swap(int[] field, int pos1, int pos2){
    	int tmp = field[pos1];
    	field[pos1] = field[pos2];
    	field[pos2] = tmp;
    }

"was soll z.B. "min = node2;" bedeuten?
min ist ein int, node2 ein ListNode.. "

stimmt das war ungewollt, durch das ganze copy paste hat sich da ein Fehler eingeschlichen.
Urpsrünglich war es: node2.setValue(min);

 

[SlaterB]

sowas in der Art könntest du hier dann auch nachbauen,
wenn du die Listen-Nodes so lassen willst, wie sie sind und nur ihren Value änderst,
das ist relativ leicht

...........



eine andere Taktik, die du deiner swap()-Operation nach verfolgst, ist,
die Nodes selber aus der Liste brutal herauszureißen und anderer Stelle wieder einzusetzen,

deine swap()-Operation macht aber praktisch noch gar nix,
sie vertauscht nur lokale Referenzen,
das hat auf die Liste selber keine Auswirkung,

wenn du das weiter verfolgen willst, dann vergiss erstmal die Sortierung,
erstelle dir ein Testliste mit 3-4 Elementen und versuch dort ganz profan das erste mit dem dritten Element zu tauschen,
das muss erstmal funktionieren!

so, und dazu ist es wichtig, die ganzen Referenzen prev und next neu zu setzen,
nicht nur von den beiden zu tauschenden Elementen, sondern auch von deren Vorgängern und Nachfolgern in der Liste,

am besten auf Papier vorher aufmalen

Spezialfälle beachten wie Anfang/ Ende der Liste oder dass die beiden Elemente direkt nebeneinander liegen,
einfacher ist vielleicht, nur einzelne Operationen 'entferne Node aus Liste' + 'fuege Node in Liste hinter Node x ein' zu schreiben,