sort.java

自己写的search engine, 有 boolean search, fuzzy search

package searchingEngine.utilites.sorting;

import java.util.*;

public class Sort
{

	public int[] Shell(int array[], int elements)
	{
		int gap, i, j, mid, tmp;
		boolean fertig;

		gap = elements;
		while (gap>1)
		{
			gap = gap >> 1;
			mid = elements-gap;
			do
			{
				fertig = true;
				for (j=0; j<mid; j++)
				{
					i = j+gap;
					if (array[j]>array[i])
					{
						{ // SWAP
							tmp = array[i];
							array[i] = array[j];
							array[j] = tmp;
						}
						fertig = false;
					}
				}
			}
			while (!fertig);
		}
		return array;
	}


	public int[] Shell2(int array[], int elements)	
	{
		int gap, i, j, tmp;

		gap = 1;
		while (gap<elements)
			gap = gap << 1; // +1

		while (gap>1)
		{
			gap = gap >> 1;
			for (i=0; i<elements-gap; i++)
			{
				j=i;
				while (j>=0 && array[j]>array[j+gap])
				{
					{ // SWAP
						tmp = array[j];
						array[j] = array[j+gap];
						array[j+gap] = tmp;
					}			
					j -= gap;
				}
			}
		}
		return array;
	}


	/*
	 * ungetestet, aus numerical recipes in C
	 * geht noch davon aus, dass arrays bei index 1 anfangen ...
	 */
	public int[] Shell3(int array[], int elements)
	{
		int i, j, inc;
		int v;

		inc = 1;

		do inc = inc * 3 + 1; while (inc <= elements);

		do
		{
			inc = inc / 3;
			for (i = inc; i<elements; i++) /* insertion sort */
			{
				v = array[i];
				j = i;
				while (array[j-inc] > v)
				{
					array[j] = array[j-inc];
					j -= inc;
					if (j <= inc)
						break;
				}
				array[j] = v;
			}
		}
		while (inc > 1);

		return array;
	}


	public int[] Shell_Metzner(int array[], int elements)
	{
		int gap, a, i, tmp;
		
		gap = elements >> 1;

		while (gap>0)
		{
			for (i=0; i<elements-gap; i++)
			{
				a = i;
				while (a>=0)
				{
					if (array[a+gap]<array[a])
					{
						{ // SWAP
							tmp = array[a];
							array[a] = array[a+gap];
							array[a+gap] = tmp;
						}
						a -= gap;
					}
					else
						break;
				}
			}
			gap = gap >> 1;
		}
		return array;
	}


	/*
	 * Selection-Sort ...
	 * auch bekannt unter den Namen Delayed-Sort und Straight-Sort
	 */
	public int[] Selection(int array[], int elements)
	{
		int i, j, min, tmp;

		for (i=0; i<elements-1; i++)
		{
			min = i;
			for (j=i+1; j<elements; j++)
				if (array[j]<array[min])
					min = j;

			if (min!=i)
			{ // SWAP
				tmp = array[min];
				array[min] = array[i];
				array[i] = tmp;
			}
		}
		return array;
	}


	/*
	 * Insertion-Sort ...
	 * gleiches System wie beim Sortieren von Spielkarten in der Hand
	 *
	 * best-case: O(n)   {array ist bereits sortiert}
	 * worst-case: O(n?) {genau umgekehrt sortiert}
	 */
	public int[] Insertion(int array[], int elements)
	{
		int i, j, tmp;

		for (i=1; i<elements; i++)
		{
			// herausgreifen
			tmp = array[i];

			// Platz schaffen / neuen Platz suchen
			for (j=i-1; j>=0 && tmp<array[j]; j--)
				array[j+1] = array[j];

			// einf黦en
			array[j+1] = tmp;
		}
		return array;
	}


	/*
	 * Bubble-Sort.
	 * ... die hirnlose Variante (auch Maximum-Sort genannt).
	 */
	public int[] Bubble(int array[], int elements)
	{
		int i, j, tmp;
	
		for (i=0; i<elements-1; i++)
			for (j=i+1; j<elements; j++)
				if (array[i]>array[j])
				{ // SWAP
					tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}

		return array;
	}


	/*
	 * nochmal Bubble-Sort
	 * ... hier ist etwas mehr Gehirn im Spiel. Hierbei wird ausgenutzt,
	 * dass das Feld sortiert ist, wenn im letzten Durchlauf nichts
	 * vertauscht werden musste. Das betrifft bereits sortierte Endstuecke
	 * des Feldes.
	 */
	public int[] Bubble2(int array[], int elements)
	{
		int i, j, tmp;
		boolean fertig;

		fertig = false;
		for (i=0; i<elements-1 && !fertig; i++)
		{
			fertig = true;
			for (j=i+1; j<elements; j++)
			{
				if (array[i]>array[j])
				{
					{ // SWAP
						tmp = array[i];
						array[i] = array[j];
						array[j] = tmp;
					}
					fertig = false;
				}
			}
		}
		return array;
	}


	/*
	 * und noch eine Variante: ein bidirektionales Bubble-Sort
	 * hierbei wird das Feld gleichzeitig von vorne und hinten her
	 * sortiert
	 */
	public int[] BiBubble(int array[], int elements)
	{
		int i, st, tmp;
		boolean fertig;

		elements--;
		fertig = false;
		for (st=0; st<elements && !fertig; st++, --elements)
		{
			fertig = true;
			// linkes Bubble-Sort
			for (i=st; i<elements; i++)
			{
				if (array[i]>array[i+1])
				{
					{ // SWAP
						tmp = array[i];
						array[i] = array[i+1];
						array[i+1] = tmp;
					}
					fertig = false;
				}		
			}
			// rechtes Bubble-Sort
			for (i=elements-1; i>=st; i--)
			{
				if (array[i]>array[i+1])
				{
					{ // SWAP
						tmp = array[i];
						array[i] = array[i+1];
						array[i+1] = tmp;
					}
					fertig = false;
				}
			}
		}
		return array;
	}


	/*
	 * QuickSort sortiert ein (Sub-)Array A[p..r] mittels 'divide & conquer'
	 *
	 * (1) DIVIDE:
	 *       Das Array A[p..r] wird in zwei nicht-leere Sub-Arrays, A[p..q] und
	 *       A[q+1..r] unterteilt, so das jedes Element in A[p..q] <= jedes
	 *       Element in A[q+1..r] ist. Der Index q wird mit Hilfe einer
	 *       Partitionierungs-Prozedur berechnet.
	 *
	 * (2) CONQUER:
	 *       Die beiden Sub-Arrays A[p..q] und A[q+1..r] werden mit Hilfe von
	 *       rekursiven Aufrufen von QuickSort sortiert.
	 *
	 * (3) COMBINE:
	 *       Weil die Sub-Arrays in-place sortiert sind, mu? nichts weiter getan
	 *       werden, um die Teil-L鰏ungen zu kombinieren - A[p..r] ist sortiert.
	 *
	 * Die Paritionierungs-Prozedur:
	 * 
	 * - W鋒le das Element x = A[p] aus A[p..r] als Pivot-Element.
	 * - Lasse zwei Regionen A[p..i] und A[j..r] vom Anfang und Ende des Arrays
	 *   aufeinander zuwachsen. Jedes Element in A[p..i] ist <= x und jedes
	 *   Element in A[j..r] ist >= x.
	 * - Sobald die Situation A[i] >= x >= A[j] erreicht ist, k鰊nen die Regionen
	 *   nicht weiter wachsen. Wenn jetzt A[i] mit A[j] vertauscht werden, kann
	 *   das Wachsen fortgesetzt werden (usw. ... bis x jeweils mit sich selbst
	 *   verglichen wird bzw gilt i>=j)
	 * - q=j wird zur點kgegeben.
	 */

	/*
	 * Paritionierungs-Prozedur: Laufzeit ist Theta(n)
	 *
	 * Im worst-case f黵 QuickSort paritioniert diese Prozedur ein Array mit n
	 * Elementen in zwei Sub-Arrays mit n-1 Elementen und einem einzelnen Element
	 */
	private int partition(int A[], int p, int r)
	{
		int i = p-1;
		int j = r+1;
		int tmp;
		int x = A[p];
	
		while (true)
		{
			do j--; while (A[j] > x);
			do i++; while (A[i] < x);
	
			if (i<j)
			{ // swap
				tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
			else return j;
		}
	}

	/*
	 * worst-case: partition unterteilt n-Elemente-Array in (n-1)-Elemente-Array
	 *             und 1-Element-Array. Weil ein 1-Element-Array in einem Schritt
	 *             sortiert wird, gilt T(1) = Theta(1). F黵 die Rekurrenz im
	 *             worst-case ergibt sich (Theta(n) ist die Komplexit鋞 von
	 *             partition):
	 *
	 *             T(n) = T(n-1) + Theta(n) = Theta(n^2)
	 *
	 *             Das worst-case-Verhalten wird von partition ausgel鰏t, wenn es
	 *             auf ein Array angesetzt wird, das bereits vollst鋘dig sortiert
	 *             ist. Insertion-Sort zeigt hier eine Laufzeit von O(n) !!!
	 *
	 *             genauer:
	 *
	 *             T(n) = max[1<=q<=n-1](T(q) + T(n-q)) + Theta(n)
	 *
	 *             Annahme: T(n) <= cn^2
	 *
	 *             T(n) <= max[1<=q<=n-1](cq^2 + c(n-q)^2) + Theta(n)
	 *
	 *                   = c max[1<=q<=n-1](q^2 + (n-q)^2) + Theta(n)
	 *
	 *             Der Ausdruck q^2+(n-q)^2 wird an den Randpunkten maximal
	 *             (Parabel) also bei 1^2+(n-1)^2 = (n-1)^2+(n-(n-1))^2 = n^2-2(n-1)
	 *
	 *             also: T(n) <= cn^2+2c(n-1)+Theta(n) <= cn^2 ==> T(n)=Theta(n^2)
	 *
	 * best-case:  Im best-case erzeugt partition zwei n/2 gro遝 Partitionen. Die
	 *             Rekurrenz lautet:
	 *
	 *             T(n) = 2*T(n/2) + Theta(n) = Theta(n*lg(n))
	 *
	 *             Fall [2] des Master-Theorems greift. Selbst, wenn n im
	 *             Verh鋖tnis 9:1 oder sogar 99:1 geteilt wird, ergibt sich eine
	 *             Laufzeit von Theta(n*lg(n)). Der worst-case ist also eher
	 *             ungew鰄nlich und QuickSort verh鋖t sich typischerweise eher
	 *             wie im best-case beschrieben.
	 *
	 * avg.-case:  
	 */
	public int[] Quick(int A[], int p, int r)
	{
		if (p<r)
		{
			int q = partition(A, p, r);

			Quick(A, p, q);
			Quick(A, q+1, r);
		}
		return A;
	}


	/*
	 * nochmal QuickSort in leicht angeaenderter Form
	 */
	public int[] Quick2(int array[], int left, int right)
	{
		int i, j, tmp;
		if (right>left)
		{
			i = left-1;
			j = right;
			do
			{
				do i++; while (array[i]<array[right]);
				do j--; while (array[j]>array[right] && j>0);

				{ // SWAP
					tmp = array[i];
					array[i] = array[j];
					array[j] = tmp;
				}
			}
			while (j>i);

			array[j] = array[i];
			array[i] = array[right];
			array[right] = tmp;
			Quick2(array, left, i-1);
			Quick2(array, i+1, right);
		}
		return array;
	}


	/*
	 * Ein iteratives QuickSort
	 */
	public int[] iQuick(int array[], int elements)
	{
		int left=0, right=elements-1, top=0;
		int sSize = (int)Math.ceil(Math.log(elements)/Math.log(2));
		int lStack[] = new int[sSize];
		int rStack[] = new int[sSize];
		int tmp;
		int i, j, x;

		lStack[top] = left; rStack[top] = right;

		while (top >= 0)
		{
			left = lStack[top];
			right = rStack[top];
			top--;

			while (left < right)
			{
				i = left;
				j = right;
				x = array[(left+right)/2];

				while (i <= j)