BucketSort // Sorting of Strings

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

BucketSort // Sorting of Strings

Beitrag von KaeferZuechter »

Laut Algowiki ist die Implementierung "obvious".
Mir ist allerdings bspw, völlig unklar, welche Datenstrukturen man sinnvollerweise verwenden würde.

Weiterhin findet man auf Wikipedia unter dem Begriff BucketSort einen zumindest auf den ersten und zweiten Blick völlig anderen Algorithmus. :?:

Wo finde ich die Erleuchtung auf diese Fragen? :)
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: BucketSort // Sorting of Strings

Beitrag von Prof. Karsten Weihe »

KaeferZuechter hat geschrieben:Laut Algowiki ist die Implementierung "obvious".
Mir ist allerdings bspw, völlig unklar, welche Datenstrukturen man sinnvollerweise verwenden würde.
Bislang hatte diesen Punkt noch niemand hinterfragt, aber natürlich kann ich noch mehr Details ins Wiki schreiben.

Für A bietet sich eigentlich ein Array an, für S' eine LinkedList o.ä., für B ein Array von LinkedList.

Beantwortet das Ihre Frage?

KW

KaeferZuechter
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 108
Registriert: 15. Apr 2015 19:24

Re: BucketSort // Sorting of Strings

Beitrag von KaeferZuechter »

Danke für die Antwort!
So ähnlich hatte ich mir das schon gedacht, es kam mir allerdings viel zu kompliziert vor. :oops:

Für A meinen sie vermutlich ebenfalls ein Array of List/MultiSet?!
Ich werde mal versuchen den Algorithmus so zu implementieren.


Edit:
Schnell mal ein bisschen gecoded:

Code: Alles auswählen

/**
 * @author KaeferZuechter from www.fachschaft.informatik.tu-darmstadt.de/forum
 */
public class BucketSort {

	private Map<Integer, List<String>> lengthMap;
	private List<String> sequence;
	private Map<Character, List<String>> buckets;

	private BucketSort(Iterable<String> input) {
		init(input);
	}

	/**
	 * @param input
	 */
	private void init(Iterable<String> input) {
		lengthMap = new TreeMap<>(Collections.reverseOrder());
		/**
		 * Fill the Collection sorted by length
		 */
		for (String str : input) {
			if (null == lengthMap.get(str.length())) {
				lengthMap.put(str.length(), new LinkedList<>());
			}
			lengthMap.get(str.length()).add(str);
		}
		sequence = new LinkedList<>();
		buckets = new TreeMap<>();
		/**
		 * Prepare the buckets
		 */
		for (char c = 'A'; c < 'z'; ++c) {
			buckets.put(c, new LinkedList<>());
		}

	}

	private Iterable<String> sort() {

		List<String> lst;
		/**
		 * Begin the iterations starting with highest index
		 */
		for (Integer i = lengthMap.keySet().iterator().next(); i > 0; --i) {
			/**
			 * Clear all buckets
			 */
			for (Character c : buckets.keySet()) {
				buckets.get(c).clear();
			}
			/**
			 * If Strings exists with length i put them into the buckets
			 */
			if (null != (lst = lengthMap.get(i))) {
				for (String str : lst) {
					buckets.get(str.charAt(i - 1)).add(str);
				}
			}
			/**
			 * Append remaining strings from sequence into buckets
			 */
			for (String str : sequence) {
				buckets.get(str.charAt(i - 1)).add(str);
			}
			/**
			 * Clear the sequence and refill with data from buckets
			 */
			sequence.clear();
			for (char c = 'A'; c < 'z'; ++c) {
				sequence.addAll(buckets.get(c));
			}
		}
		return sequence;
	}

	/**
	 * Sort a Collection of Strings with BucketSort
	 * 
	 * @param input
	 * @return The Collection sorted in ascending order
	 */
	public static Iterable<String> sort(Iterable<String> input) {
		return new BucketSort(input).sort();
	}

	/**
	 * Sort an Array of Strings with BucketSort
	 * 
	 * @param input
	 * @return The Collection sorted in ascending order
	 */
	public static Iterable<String> sort(String... input) {
		return sort(Arrays.asList(input));
	}

}
Funktionieren tut der Algorithmus jedenfalls.
Ob die TreeMaps eine gute Wahl sind wird sich zeigen wenn ich die Performance checke.
IT'S CALLED A FOURIER TRANSFORM WHEN YOU TAKE A NUMBER AND CONVERT IT TO THE BASE SYSTEM WHERE IT WILL HAVE MORE FOURS, THUS MAKING IT "FOURIER". IF YOU PICK THE BASE WHERE IS HAS THE MOST FOURS, THE NUMBER IS SAID TO BE "FOURIEST".

\(1160_8 \rightarrow 624_{10} \rightarrow 440_{12} \rightarrow 4444_5\)

- Zach Weiner -

Antworten

Zurück zu „Archiv“