sort.java

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

				{
					while (array[i] < x) i++;
					while (array[j] > x) j--;

					if (i<=j)
					{
						{ // SWAP
							tmp = array[i];
							array[i] = array[j];
							array[j] = tmp;
						}
						i++;
						j--;
					}
				}

				if (j-left < right-i)
				{
					if (i < right)
					{
						top++;
						lStack[top] = i;
						rStack[top] = right;
					}
					right = j;
				}
				else
				{
					if (left < j)
					{
						top++;
						lStack[top] = left;
						rStack[top] = j;
					}
					left = i;
				}
			}
		}
		return array;
	}


	/*
	 * Comb-Sort11 ist eine optimierte Version des einfachen Bubble-Sort.
	 * Orginal-Kommentar einer Pascal-Version:
	 *
	 * "The combsort is an optimised version of the bubble sort. It uses a
	 * decreasing gap in order to compare values of more than one element
	 * apart.  By decreasing the gap the array is gradually "combed" into
	 * order ... like combing your hair. First you get rid of the large
	 * tangles, then the smaller ones ...
	 * There are a few particular things about the combsort.
	 * Firstly, the optimal shrink factor is 1.3 (worked out through a
	 * process of exhaustion by the guys at BYTE magazine). Secondly, by
	 * never having a gap of 9 or 10, but always using 11, the sort is
	 * faster.
	 * This sort approximates an n log n sort - it's faster than any other
	 * sort I've seen except the quicksort (and it beats that too sometimes).
	 * The combsort does not slow down under *any* circumstances. In fact, on
	 * partially sorted lists (including *reverse* sorted lists) it speeds up."
	 *
	 * Idee aus dem "Byte magazine", April 1991, Richard Box/Stephen Lacey
	 */
	public int[] Comb11(int array[], int elements)
	{
		int gap, i, j, tmp;
		boolean fertig;
		float shrink = 1.3F; // optimaler shrink-Faktor fuer Comb-Sort

		gap = elements;

		do
		{
			fertig = true;
			gap = (int)((float)gap/shrink);

			// gap darf niemals kleiner als 1 werden. Im Fall von
			// gap==1 verhaelt sich Comb-Sort wie Bubble-Sort.
			if (gap<1)
				gap = 1;
			else if (gap==9 || gap==10)
				gap = 11; // optimieren (Comb-Sort >>11<<)

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


	public int[] Shaker(int array[], int elements)
	{
		int i, j, k, min, max, tmp;

		for (i=0, k=elements-1; i<k; i++, k--)
		{
			min = max = i;
			for (j=i+1; j<=k; j++)
			{
				if (array[j] < array[min])
					min = j;
				if (array[j] > array[max])
					max = j;
			}

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


	public int[] Merge(int array[], int lo, int hi)
	{
		int mid, end_lo, start_hi, tmp, k;

		if (lo<hi)
		{
			mid = (lo+hi)>>1;
			end_lo = mid;
			start_hi = mid+1;

			Merge(array, lo, end_lo);
			Merge(array, start_hi, hi);

			while ((lo <= end_lo) && (start_hi <= hi))
			{
				if (array[lo] < array[start_hi]) lo++;
				else
				{
					tmp = array[start_hi];
					for (k = start_hi - 1; k >= lo; k--)
					{
						array[k+1] = array[k];
					}
					array[lo] = tmp;
					lo++;
					end_lo++;
					start_hi++;
				}
			}
		}
		return array;
	}


	/*
	 * Traditionelles Heap-Sort, O(N*ld(N))
	 */
	public int[] Heap(int array[], int elements)
	{
		int i;
		int tmp;
		int size = elements-1;

		// Erstelle den Heap. heapify wird auf den inneren
		// Knoten aufgerufen (index < elements/2). Der r點kw鋜ts
		// laufende Index im Heap entspricht einem Aufstieg zur
		// Wurzel.
		// Komplexit鋞: O(N*ld(N)) (genauer sogar: O(N))
		for (i=elements/2-1; i>=0; i--)
			heapify(array, i, elements);

		// Sortierung. Prinzip: Nach jedem heapify steht der
		// gr鲞te Index immer an der Wurzel => fortlaufendes
		// Austauschen der Wurzel. O(N*ld(N))
		for (i=elements-1; i>=1; i--)
		{
			{ // SWAP
				tmp = array[i];
				array[i] = array[0];
				array[0] = tmp;
			}

			// Heap-Eigenschaft f黵 nicht-sortierte Elemente
			// wiederherstellen: O(ld(N))
			heapify(array, 0, size--);
		}

		return array;
	}
	private int LEFT(int i) { return 2*i+1; }
	private int RIGHT(int i){ return 2*i+2; }
	/*
	// traditionelle rekursive Version von 'heapify'
	private void heapify(int array[], int i, int size)
	{
		int l = LEFT(i);
		int r = RIGHT(i);
		int largest;
		int tmp;

		if (l<size && array[l]>array[i])
			largest = l;
		else
			largest = i;

		if (r<size && array[r]>array[largest])
			largest = r;

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

			// getauschten Wert so tief wie n鰐ig im Heap
			// "versickern" lassen:
			heapify(array, largest, size);
		}
	}
	*/
	// die endst鋘dige Rekursion der traditionellen heapify-Funktion
	// l溥t sich leicht in eine iterative Funktion umwandeln:
	private void heapify(int array[], int i, int size)
	{
		int j, l, r;
		int largest;
		int tmp;

		j = i;
		while (true)
		{
			l = LEFT(j);
			r = RIGHT(j);

			if (l<size && array[l]>array[j])
				largest = l;
			else
				largest = j;

			if (r<size && array[r]>array[largest])
				largest = r;

			if (largest != j)
			{ // SWAP
				tmp = array[j];
				array[j] = array[largest];
				array[largest] = tmp;

				// getauschten Wert so tief wie n鰐ig im Heap
				// "versickern" lassen:
				j = largest;
			}
			else break;
		}
	}


	/*
	 * Heap-Sort (Funktion Heap und iterative Unterfunktion heapify_iter)
	 */
	public int[] Heap2(int array[], int elements)
	{
		int tmp, k;

		// Heap aufbauen ...
		for (k=elements>>1; k>0; k--)
			heapify_iter(array, k, elements);

		do
		{
			elements--;

			{ // SWAP
				tmp = array[0];
				array[0] = array[elements];
				array[elements] = tmp;
			}
			
			heapify_iter(array, 1, elements);
		}
		while (elements>1);

		return array;
	}
	private void heapify_iter(int array[], int k, int n)
	{
		int i, tmp;
		
		tmp = array[k-1];

		while (k <= n>>1)
		{
			i = k<<1;
			if ((i<n) && (array[i-1]<array[i])) i++;
			if (tmp >= array[i-1]) break;
			else
			{
				array[k-1] = array[i-1];
				k = i;
			}
		}
		array[k-1] = tmp;
	}


	/*
	 * RadixSort (Funktion Radix und Unterfunktion radix_pass)
	 * Absolut Java-int-spezifisch - In Java ist ein int 4 Byte gross
	 * Der Name hat seinen Ursprung in engl. radix = Zahlenbasis; im
	 * Dezimalsystem wird beispielsweise mit "radix 3" die Ziffer
	 * bezeichnet, die den Stellenwert 10^3 hat.
	 *
	 * In RadixSort finden keine Vergleiche statt - aus diesem Grund gibt
	 * es auch auch keinen SWAP-Teil. Ein Feld wird in mehreren
	 * Durchgaengen nach und nach sortiert [...Beschreibung Algo...]
	 *
	 * RadixSort ist leider sehr Typ- und Plattform-spezisch und muss fuer
	 * jede neue Anwendung neu programmiert werden. Ein weiterer Nachteil
	 * ist der Speicherverbrauch. Fuer spezielle Anwendungen, in denen es
	 * auf Geschwindigkeit ankommt und das Feld nicht allzu gross ist
	 * (Speicherverbrauch!), ist es dennoch sehr empfehlenswert, da
	 * Feldgroesse und Laufzeit in linearem Zusammenhang [ O(N) ] stehen,
	 * wodurch es (in seinem speziellen Einsatzgebiet) schneller als z.B.
	 * HeapSort [ O(N*ld(N)) ] ist.
	 */
	public int[] Radix(int source[], int elements)
	{
		int temp[] = new int[elements];

		// N int-Zahlen nach byte 0 von source nach temp sortieren
		// das lsb ... least-significant-byte
		counting_sort_by_radix(0, elements, source, temp);

		// N int-Zahlen nach byte 1 von temp nach source sortieren
		counting_sort_by_radix(1, elements, temp, source);

		// N int-Zahlen nach byte 2 von source nach temp sortieren
		counting_sort_by_radix(2, elements, source, temp);

		// N int-Zahlen nach byte 3 von temp nach source sortieren
		// das msb ... most-significant-byte
		counting_sort_by_radix(3, elements, temp, source);

		return source;
	}
	private int GETBYTE(int val, int bytenum)
	{
		return (val >> (8 * bytenum)) & 0xff;
	}
	private void counting_sort_by_radix(int int_byte, int elements, int source[], int dest[])
	{
		final int k = 256; // Anzahl der 'Klassen'
		int count[] = new int[k]; // ein Z鋒ler f黵 jede Klasse
		int i;
		int source_i;

		// etwas wie
		// for (i=0; i<k; i++) count[i] = 0;
		// kann in Java entfallen

		// Anzahl der Zahlenwerte einzelner 'Klassen' z鋒len
		for (i=0; i<elements; i++)
		{
			source_i = GETBYTE(source[i], int_byte);
			count[source_i]++;
		}

		// sp鋞ere Array-Indices berechnen:
		// k0[0]		-> dest[0]
		// ...
		// k0[count[k0]]	-> dest[count[k0]]
		// k1[0]		-> dest[count[k0]+1]
		// ...
		// k1[count[k1]]	-> dest[count[k0]+count[k1]]
		// ...
		for (i=1; i<k; i++)
			count[i] += count[i-1];

		// Sortieren:
		for (i=elements-1; i>=0; i--)
		{
			// zu sortierendes Byte 'herausfischen'
			source_i = GETBYTE(source[i], int_byte);

			dest[count[source_i]-1] = source[i];

			// da ansonsten alle mehrfach auftretenden Zahlenwerte
			// einer 'Klasse' auf ein dest-Element abgebildet werden
			// w黵den ...
			count[source_i]--;
		}
	}

	public static void main(String[] Args)
	{
		int SortierFeld[] = new int[256];
		int i;
		int last;
		Sort S = new Sort();
		Random rand = new Random(System.currentTimeMillis());

		for (i=0; i<SortierFeld.length; i++)
			SortierFeld[i] = Math.abs(rand.nextInt()) % 32768;

		// SortierFeld = S.Shell(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Shell2(SortierFeld, SortierFeld.length);
		// SortierFeld = S.Shell3(SortierFeld, SortierFeld.length);
		// SortierFeld = S.Shell_Metzner(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Selection(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Insertion(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Bubble(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Bubble2(SortierFeld,SortierFeld.length);
		// SortierFeld = S.BiBubble(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Quick(SortierFeld,0,SortierFeld.length-1);
		// SortierFeld = S.Quick2(SortierFeld,0,SortierFeld.length-1);
		// SortierFeld = S.iQuick(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Comb11(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Shaker(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Merge(SortierFeld,0,SortierFeld.length-1);
		// SortierFeld = S.Heap(SortierFeld,SortierFeld.length);
		// SortierFeld = S.Heap2(SortierFeld,SortierFeld.length);
		SortierFeld = S.Radix(SortierFeld,SortierFeld.length);

		last = SortierFeld[0];
		for (i=1; i<SortierFeld.length; i++)
		{
			if (last>SortierFeld[i]) break;
			last = SortierFeld[i];
		}

		if (i == SortierFeld.length)
			System.out.println("Feld ist sortiert!");
		else
			System.out.println("Fehler: Feld ist nicht sortiert :-(");
	}
}