Counting Sort (Sortieren durch Zählen)

[Blistex]

hallo , ich habe die aufgabe, einen Counting Sort zu implementieren. Komme nun aber einfach nicht weiter ... wäre nett wenn mir jemand helfen könnte.

das habe ich bis jetzt:

import java.util.*;

class zählen
{
public static void main(String[] args)
{
 int n = 1;  // Anzahl der Elemente des Arrays
	int[] array = new int[n]; 
    
	// Zufallsgenerator:
	Random rnd = new Random(); 
	for (int i=0; i<array.length; i++)
	{
		array[i] = rnd.nextInt(10*n)+1; // Zufallszahlen zwischen 1 und 10n	
    }
	
	zaehlen(array,k);
	

static void zaehlen (int[]array, k)
 {
 int k = max_value();  								// Maximum in Array
 int neu[] = new int[array.length];
 int hilf[] = new int[k+1]; 						// +1 ?
 
 for( i= 0 ; i<k+1 ; i++)							// Erzeugung eines Arrays mit 0
	{
    hilf[ i ] = 0;
	}

for(i = 0 ; i<array.Length; i++) 					// Anzahl der Häufigkeit einer Zahl
{
    hilf[array[i]] = hilf[array[i]] + 1;
}
 
for( i = 0 ; i<k+1 ; i++) 							// Addieren des Hilf-Arrays (bis zu welcher Position eine Zahl auftaucht)
{
    hilf[i] = hilf[i] + hilf[i + 1];
}

for(i = array.length-1;i>=0 ; i--) 					// Sortieren in neues Array (von hinten nach vorne)
{
    neu[hilf[array[i]] - 1 ] = array[i];	// Werte werden ins neue Array geschrieben --> -1 weg?
    hilf[array[i]] = hilf[array[i]] - 1;	// um 1 vermindert
}

 }
}
}

das wird mir als Fehler beim compilieren angezeigt:

:20: error: illegal start of expression
static void zaehlen (int[]array, k)

Vielen Dank schonmal für eure Antworten.

 

[MR_UNIX]

Du hast in deinen Parametern stehen "int[] array, k" - dein "k" ist aber nicht typisiert. Du musst dem Compiler noch sagen, was dein "k" für ein Datentyp sein soll.

 

[Blistex]

naja ok, dann habe ich ein int vor das k gesetzt, aber das probem ist immernoch da

 

[Ruzmanz]

Downloade dir Eclipse oder Netbeans und pack dort deinen Code rein.

int k = max_value();
array.length
int i;
...

 

[Deros]

dein Code ist leider gespickt mit Fehlern.
1. Deine Main Methode öffnet sich zwar mit einer geschweiften Klammer aber schliesst diese erst nach der Methode zahlen, das müsste sie vorher.
2. IN Zeile 17 rufst du zahlen mit k auf. Was soll k sein? Die Variabel fällt in dem Moment einfach vom Himmel oder wie?
3. Konsequenterweise hat in Zeile 20 die Methode zahlen auch keinen Typ für den Parameter k, was so natürlich nicht klapp.
4. Zeile 22 k bekommt endlich einen Typ und soll mit der Methode max_value() initialisiert werden. Die Methode fehlt aber im Code...
5. Zeile 26 das i in der for-Schleife hat auch keinen Typ int wäre hier wohl angebracht. Wiederholt sich für alle for-schleifen.
6. Zeile 31. array.Length müsste array.length sein

Dann würde der Code zumindest kompilieren, aber ob er auch nur ansatzweise das macht was er soll...???:L

 

[Blistex]

also zu deinem 4. punkt kann ich nur sagen , dass ich den befehl max_value() einfach so von meinem lehrer auf einem blatt bekommen habe. Was muss ich denn machen, damit der funktioniert?

achso und zudem sollte man sagen, dass informatik nicht gerade mein fach ist 😀

 

[Deros]

da stand doch bestimmt noch was bei, was soll die Methode denn deiner Meinung nach machen? Wahrscheinlich doch den maximal Wert von irgendwas zurückgeben oder? dazu müsste die Methode ja zumindest wissen wovon du den maximal Wert haben möchtest oder? Das array würde sich doch anbieten...

 

[Blistex]

ja also mit dem befehl möchte ich ja den höchsten wert aus dem array wissen bzw angeben. muss ich also max_value() deklarieren oder wie ? also muss ich angeben, welcher der höchste wert ist?

 

[Ruzmanz]

Du brauchst eine Schleife, die das Array bis zum Ende durchläuft und den höchsten Wert findet.

 

[Blistex]

schleife ok, aber wie mach ich das mit der höchsten zahl?

 

[Deros]

dir ist doch bestimmt bekannt wie man 2 zahlen vergleicht?
also erste Zahl merken mit der zweiten vergleichen. größere von beiden merken und mit der nächsten vergleichen und soweiter und sofort bis array durchgelaufen ist.

 

[Blistex]

nein ist mir leider nicht :/

 

[kaoZ]

Ich habe mal Versucht es so einfach und übersichtlich wie möglich zu gestalten, eine Implementierung zum Auffinden der niedrigsten Zahl solltest du unter Verwendung dieses Beispiels eigentlich alleine hinbekommen:

public class Foo {
	
	public Foo() {}
	
	static int findHighestValue(int[] arr){
		int helper = 0;
		
		for (int i = 0; i < arr.length; i++) {
	        if (arr[i] > helper) {
	            helper = arr[i];
            }
        }
		
		return helper;
	}
	
	public static void main(String[] args) {
		
		int[] array = {1,5,3,6,7,9,44};
		
	    System.out.println(Foo.findHighestValue(array));
    }
}

Ausgabe ist Logischerweise :

44

 

[Blistex]

jetzt steh ich iwie total auf dem schlauch oder ich bin einfach zu doof für sowas... :/

das hab ich bis jetzt ...

import java.util.*;

class zaehlen1
{
public static void main(String[] args)
{
    //int n = 5;  // Anzahl der Elemente des Arrays
	//int[] array = new int[n]; 
    
	// Zufallsgenerator:
	//Random rnd = new Random(); 
	//for (int i=0; i<array.length; i++)
	//{
	   //array[i] = rnd.nextInt(10*n)+1; // Zufallszahlen zwischen 1 und 10n	
   // }
	
	 int[] array = {1, 2, 4, 2, 6};
	 
	 System.out.println(zaehlen1.findewert(array));
	
	zaehlen(array);
}

 static int findewert(int[] array)					// höchsten Wert finden
 {

        int helper = 0;

        for (int i = 0; i < array.length; i++) 
		{

            if (array[i] > helper) 
			{
			helper = array[i];
			}
		}

        return helper;

    }


static void zaehlen (int[]array)
 {
 int k = helper;									// max_value();  ?								 // Maximum in Array
 int neu[] = new int[array.length];
 int hilf[] = new int[k+1]; 						// +1 ?
 
 for(int i= 0 ; i<k+1 ; i++)							// Erzeugung eines Arrays mit 0
	{
    hilf[ i ] = 0;
	}

for(int i = 0 ; i<array.length; i++) 					// Anzahl der Häufigkeit einer Zahl
{
    hilf[array[i]] = hilf[array[i]] + 1;
}
 
for(int i = 0 ; i<k+1 ; i++) 							// Addieren des Hilf-Arrays (bis zu welcher Position eine Zahl auftaucht)
{
    hilf[i] = hilf[i] + hilf[i + 1];
}

for(int i = array.length-1;i>=0 ; i--) 					// Sortieren in neues Array (von hinten nach vorne)
{
    neu[hilf[array[i]] - 1 ] = array[i];	// Werte werden ins neue Array geschrieben --> -1 weg?
    hilf[array[i]] = hilf[array[i]] - 1;	// um 1 vermindert
}

 }

}