Keskustelu: Koodit: Java: Järjestysalgoritmien vertailua

Sami [22.10.2004 00:42:18]

Ohjelma Bubble-, Insertion-, Heap- ja Quicksortien vertailemiseen.

Jokainen algoritmi on oma säikeensä ja kaikki järjestävät samanlaisen taulukon. Viivettä algoritmeihin on laitettu 5ms/vertailuoperaatio ja 10ms/kahden muuttujan vaihto keskenään.

Kaikki koodi Heap- ja Quicksortia lukuunottamatta ovat täysin itse kirjoitettuja. Heap- ja Quicksort ovat pääosin suoria käännöksiä Wikipediasta löytyvistä algoritmeista/koodeista (http://en.wikipedia.org/wiki/Heapsort ja http://en.wikipedia.org/wiki/Quicksort)

Suoraan käyttövalmis appletti löytyy osoitteesta http://www.paivola.fi/~sami/java/Sort/Sort.html ja kaikki sorsat, käännetyt tiedostot ja html-tiedoston voi ladata yhdessä paketissa osoitteesta http://www.paivola.fi/~sami/java/Sort/Sort.zip

VIIMEISIMPIÄ MUOKKAUKSIA:
27.10:
- Lisätty vertailuun FooBat:in kirjoittamat algoritmit (Selectionsort, Mergesort, Countsort)
- Paranneltu hieman appletin skaalautuvuutta pystysuunnassa.

Array.java

public class Array extends Thread {
	protected int[] array;
	public Array(int[] array) {
		this.array = new int[array.length];
		System.arraycopy(array, 0, this.array, 0, array.length);
	}

	public void run() {
		sort();
	}

	public void sort() {}

	public int getValue(int position) {
		return array[position];
	}
}

Bubblesort.java

public class Bubblesort extends Array {
	public Bubblesort(int[] array) {
		super(array);
	}

	public void sort() {
		for (int i = 0; i < array.length; i++) {
			for (int j = array.length-1; j > i; j--) {
				try {Thread.sleep(5);} catch (InterruptedException e) {}
				if (array[j-1] > array[j]) {
					int tmp = array[j-1];
					array[j-1] = array[j];
					array[j] = tmp;
					try {Thread.sleep(10);} catch (InterruptedException e) {}
				}
			}
		}
	}
}

Insertionsort.java

public class Insertionsort extends Array {
	public Insertionsort(int[] array) {
		super(array);
	}

	public void sort() {
		for (int i = 0; i < array.length; i++) {
			for (int j = i-1; j >= 0; j--) {
				try {Thread.sleep(5);} catch (InterruptedException e) {}
				if (array[j+1] < array[j]) {
					int tmp  = array[j+1];
					array[j+1] = array[j];
					array[j] = tmp;
					try {Thread.sleep(10);} catch (InterruptedException e) {}
				} else {
					break;
				}
			}
		}
	}
}

Heapsort.java

public class Heapsort extends Array {
	public Heapsort(int[] array) {
		super(array);
	}

	public void sort() {
		int start = array.length / 2 - 1, end = array.length - 1;

		while (start >= 0) {
			sift(start, array.length);
			start--;
		}

		while (end >= 0) {
			int tmp = array[end];
			array[end] = array[0];
			array[0] = tmp;
			try {Thread.sleep(10);} catch (InterruptedException e) {}

			sift(0, end);
			end--;
		}
	}

	public void sift(int start, int count) {
		int root = start, child;

		while (root * 2 < count) {
			child = root * 2;
			try {Thread.sleep(5);} catch (InterruptedException e) {}
			if ((child < count - 1) && (array[child] < array[child+1])) {
				child++;
			}

			try {Thread.sleep(5);} catch (InterruptedException e) {}
			if (array[root] < array[child]) {
				int tmp = array[root];
				array[root] = array[child];
				array[child] = tmp;
				root = child;
				try {Thread.sleep(10);} catch (InterruptedException e) {}
			} else return;
		}
	}
}

Quicksort.java

public class Quicksort extends Array {
	public Quicksort(int[] array) {
		super(array);
	}

	public void sort() {
		sort(0, array.length);
	}

	public void sort(int begin, int end) {
		try {Thread.sleep(5);} catch (InterruptedException e) {}
		if (end > begin) {
			int pivot = array[begin];
			int l = begin + 1;
			int r = end;
			while (l < r) {
				try {Thread.sleep(5);} catch (InterruptedException e) {}
				if (array[l] <= pivot) {
					l++;
				} else {
					r--;
					int tmp = array[l];
					array[l] = array[r];
					array[r] = tmp;
					try {Thread.sleep(10);} catch (InterruptedException e) {}
				}
			}
			l--;
			int tmp = array[l];
			array[l] = array[begin];
			array[begin] = tmp;
			try {Thread.sleep(10);} catch (InterruptedException e) {}
			sort(begin, l);
			sort(r, end);
		}
	}
}

Selectionsort.java

public class Selectionsort extends Array {
  public Selectionsort(int[] array) {
    super(array);
  }

  public void sort() {
    int minIx;
    for (int i = 0; i < array.length-1; i++) {
      minIx = i;
      for (int j = i+1; j < array.length; j++) {
        try {Thread.sleep(5);} catch (InterruptedException e) {}
        if (array[j] < array[minIx]) {
          minIx = j;
        }
      }
      int tmp  = array[i];
      array[i] = array[minIx];
      array[minIx] = tmp;
      try {Thread.sleep(10);} catch (InterruptedException e) {}
    }
  }
}

Mergesort.java

public class Mergesort extends Array {
  int [] buffer;
  public Mergesort(int[] array) {
    super(array);
    buffer = new int[array.length];
  }

  public void sort() {
    sort(0, array.length-1);
  }

  public void sort(int low, int hi) {
    try {Thread.sleep(5);} catch (InterruptedException e) {}
    if (low >= hi)
      return;

    int middle = (low+hi)/2;
    //sort
    sort(low, middle);
    sort(middle+1, hi);
    //merge
    int iX = 0;
    int a = low;
    int b = middle+1;
    int amax = middle;
    int bmax = hi;

    for (int i = low; i <= hi;i++) {
      try {Thread.sleep(10);} catch (InterruptedException e) {}
      buffer[i] = array[i];
    }

    for (int i = low; i <= hi; i++) {
      try {Thread.sleep(10);} catch (InterruptedException e) {}
      if (a <= amax)
        if (b <= bmax) {
          try {Thread.sleep(5);} catch (InterruptedException e) {}
          if (buffer[a] < buffer[b])
            array[i] = buffer[a++];
          else
            array[i] = buffer[b++];
        }
        else
          array[i] = buffer[a++];
      else
        array[i] = buffer[b++];

    }

  }
}

Countsort.java

public class Countsort extends Array {
  public Countsort(int[] array) {
    super(array);
  }

  public void sort() {
    int [] c = new int[256];
    for (int i = 0; i < array.length; i++) {
      c[array[i]]++;
      try {Thread.sleep(5);} catch (InterruptedException e) {}
    }
    for (int i = 0, a = 0; i < c.length; i++)
      while(c[i]-- > 0) {
        array[a++] = i;
        try {Thread.sleep(5);} catch (InterruptedException e) {}
      }
  }
}

Sort.java, varsinainen vertailuappletti

import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;


public class Sort extends Applet {
	final int n = 150;
	Insertionsort insertionsort;
	Heapsort heapsort;
	Bubblesort bubblesort;
	Quicksort quicksort;
	Selectionsort selectionsort;
	Mergesort mergesort;
	Countsort countsort;
	final int ALGORITHMS = 7;

	int[] array;

	public void init() {
		array = new int[n];
		for (int i = 0; i < n; i++) {
			array[i] = (int)(Math.random() * 256);
		}

		this.setSize(450, 350);

		insertionsort = new Insertionsort(array);
		heapsort = new Heapsort(array);
		bubblesort = new Bubblesort(array);
		quicksort = new Quicksort(array);
		selectionsort = new Selectionsort(array);
		mergesort = new Mergesort(array);
		countsort = new Countsort(array);

		insertionsort.start();
		heapsort.start();
		bubblesort.start();
		quicksort.start();
		selectionsort.start();
		mergesort.start();
		countsort.start();
}

	public void paint(Graphics g) {
		Image bufferImage = createImage(this.getWidth(), this.getHeight());
		Graphics buffer = bufferImage.getGraphics();

		int height = this.getHeight() / ALGORITHMS;

		//Piirretään Bubblesortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = bubblesort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 0 * height, this.getWidth()/n, height);
		}

		//Piirretään insertionsortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = insertionsort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 1 * height, this.getWidth()/n, height);
		}

		//Piirretään Heapsortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = heapsort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 2 * height, this.getWidth()/n, height);
		}

		//Piirretään Quicksortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = quicksort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 3 * height, this.getWidth()/n, height);
		}

		//Piirretään Selectionsortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = selectionsort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 4 * height, this.getWidth()/n, height);
		}

		//Piirretään Mergesortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = mergesort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 5 * height, this.getWidth()/n, height);
		}

		//Piirretään Countsortin edistymistä
		for (int i = 0; i < n; i++) {
			int value = countsort.getValue(i);
			buffer.setColor(new Color(value, value, value));
			buffer.fillRect(i * (this.getWidth()/n), 6 * height, this.getWidth()/n, height);
		}

		buffer.setColor(Color.RED);
		buffer.drawString("Bubblesort", 10, 10);
		buffer.drawString("Insertionsort", 10, 10 + 1 * height);
		buffer.drawString("Heapsort", 10, 10 + 2 * height);
		buffer.drawString("Quicksort", 10, 10 + 3 * height);
		buffer.drawString("Selectionsort", 10, 10 + 4 * height);
		buffer.drawString("Mergesort", 10, 10 + 5 * height);
		buffer.drawString("Countsort", 10, 10 + 6 * height);

		g.drawImage(bufferImage, 0, 0, this.getWidth(), this.getHeight(), this);

		repaint();
	}

	public void update(Graphics g) {
		paint(g);
	}
}

Antti Laaksonen [22.10.2004 22:45:50]

Hyvä havainnollistaminen! Vähän samantapainen QBasic-ohjelma on tässä.

FooBat [26.10.2004 15:06:12]

Havainnollistaminen on hyvä, mutta tuosta puuttuu kolme omaa suosikkialgoritmiani.

Kaikkein intuiivisin järjestysalgoritmi eli SelectionSort. Erittäin hyvä 10:n alkion järjestämiseen. Tästä ainakin heti näkee miten se toimii. Kilpailee tasapäisesti insertion sortin kanssa, mutta on ainakin minun mielestä yksinkertaisempi.

Mergesort, joka on ehdottomasti paras tapa järjestää paksu nippu numeroituja papereita käsin. Vaatii nopeasti toimiakseen järjestettävän taulukon verran lisätilaa. Toimii hyvin listoille.

Counting sort jolla voi pistää luun kurkkuu kaikille huippukoodareille, jotka väittävät, että quicksort on ratkaisu kaikkiin järjestysongelmiin. Tämä on oikeastikin hyödyllinen järjestystapa, mutta sen käyttö on hiukan rajoitettua ilmeisistä syistä.

//Selectionsort.java
public class Selectionsort extends Array {
  public Selectionsort(int[] array) {
    super(array);
  }

  public void sort() {
    int minIx;
    for (int i = 0; i < array.length-1; i++) {
      minIx = i;
      for (int j = i+1; j < array.length; j++) {
        try {Thread.sleep(5);} catch (InterruptedException e) {}
        if (array[j] < array[minIx]) {
          minIx = j;
        }
      }
      int tmp  = array[i];
      array[i] = array[minIx];
      array[minIx] = tmp;
      try {Thread.sleep(10);} catch (InterruptedException e) {}
    }
  }
}

public class Mergesort extends Array {
  int [] buffer;
  public Mergesort(int[] array) {
    super(array);
    buffer = new int[array.length];
  }

  public void sort() {
    sort(0, array.length-1);
  }

  public void sort(int low, int hi) {
    try {Thread.sleep(5);} catch (InterruptedException e) {}
    if (low >= hi)
      return;

    int middle = (low+hi)/2;
    //sort
    sort(low, middle);
    sort(middle+1, hi);
    //merge
    int iX = 0;
    int a = low;
    int b = middle+1;
    int amax = middle;
    int bmax = hi;

    for (int i = low; i <= hi;i++) {
      try {Thread.sleep(10);} catch (InterruptedException e) {}
      buffer[i] = array[i];
    }

    for (int i = low; i <= hi; i++) {
      try {Thread.sleep(10);} catch (InterruptedException e) {}
      if (a <= amax)
        if (b <= bmax) {
          try {Thread.sleep(5);} catch (InterruptedException e) {}
          if (buffer[a] < buffer[b])
            array[i] = buffer[a++];
          else
            array[i] = buffer[b++];
        }
        else
          array[i] = buffer[a++];
      else
        array[i] = buffer[b++];

    }

  }
}

//Countsort.java
public class Countsort extends Array {
  public Countsort(int[] array) {
    super(array);
  }

  public void sort() {
    int [] c = new int[256];
    for (int i = 0; i < array.length; i++) {
      c[array[i]]++;
      try {Thread.sleep(5);} catch (InterruptedException e) {}
    }
    for (int i = 0, a = 0; i < c.length; i++)
      while(c[i]-- > 0) {
        array[a++] = i;
        try {Thread.sleep(5);} catch (InterruptedException e) {}
      }
  }
}

phadej [26.12.2004 20:24:17]

Olisi paljon kivempi, ja ehkä havannoilitavampi, jos appletti ottais satunnaisesti alkioita lajiteltavaan taulukkoon. Muuten tästä voi syntyä väärinkäsityksiä (tai edes satunnaisesti sekottaisi taulukon alussa).

JrPr [02.12.2008 15:23:40]

Eikös se niin teekin... ainakin uusin versio.

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Kirjautuminen

Haku

Tehtävät