Array mit quicksort und median als pivot element sortieren?

Hey, ich hab die Aufgabe eine Methode Median(), welche mir den Median einer Methode wiedergibt so in den Quicksort Algorithmus zu implementieren, dass er diesen als Pivot Element nimmt und somit eine Laufzeit von O(log(n)) hat. Mein Gedanke war jetzt Folgender:

	/**
	 * Sorts an array with the quicksort algorithm.
	 * 
	 * @param numbers the array to sort.
	 * @param l    the left index of the sorted range.
	 * @param r    the right index of the sorted range.
	 * @return the sorted array.
	 */
	public static int[] quicksort(int[] numbers, int l, int r) {
		quicksortArray = numbers;

		int x;
		int temp;
		int i;
		int j;

		if (l < r) {

			int[] arrayForMedian = Arrays.copyOfRange(quicksortArray, l, r);
			x = lowerMedian(arrayForMedian);
			i = l + 1;
			j = r;

			while (i <= j) {
				while ((i <= j) && (quicksortArray[i] <= x)) {
					i = i + 1;
				}
				while ((i <= j) && (quicksortArray[j] >= x)) {
					j = j - 1;
				}

				if (i < j) {
					temp = quicksortArray[i];
					quicksortArray[i] = quicksortArray[j];
					quicksortArray[j] = temp;
				}
			}
			i = i - 1;
			quicksortArray[l] = quicksortArray[i];
			quicksortArray[i] = x;
			quicksort(quicksortArray, l, i - 1);
			quicksort(quicksortArray, i + 1, r);
		}
		return quicksortArray;
	}

Wenn ich diesen jedoch auf beispielsweise {10,1,9,2,8,3,7,4,6,5} anwende kommt [1, 1, 2, 2, 4, 6, 6, 6, 6, 9] heraus. Ist meine Idee der Implementierung hier komplett falsch oder warum funktioniert es nicht?

Computer, Programmieren, Java, Informatik
Wie kann man diesen Java-Code "eleganter" gestalten?

Es geht darum in einem boolean-2d-Array den den Wert aller Nachbarn um einen Wert herum abzufragen, und dann die Anzahl der Nachbarn mit dem Wert "true" zurückzugeben...

Mein Code den ich jetzt geschrieben habe "funktioniert" zwar, sieht aber absolut mies aus.

public class ArrayTest
{
    public static boolean[][] grid = new boolean[10][10];
   
    public static void main(String[] args)
    {
        grid[2][1] = true;
        grid[1][2] = true;
        grid[1][0] = true;
        int a = aliveAdjacent(1, 1);
        System.out.println(a);
    }


    public static int aliveAdjacent (int x, int y)              
    {
        int count = 0;
        
        if (x != 0 && y != 0)                                   
        {
            if (x != 9 && y != 9)                               
            {
                if (grid[x-1][y-1] == true)
                count++;
                if (grid[x-1][y] == true)
                count++;
                if (grid[x-1][y+1] == true)
                count++;
                if (grid[x][y-1] == true)
                count++;
                if (grid[x+1][y-1] == true)
                count++;
                if (grid[x-1][y] == true)
                count++;
                if (grid[x+1][y] == true)
                count++;
                if (grid[x][y+1] == true)
                count++;
                if (grid[x+1][y+1] == true)
                count++;
            }
            return count;
        }
        return 0;
    }
}

Ich würde das irgendwie gerne mit 2 for-loops lösen anstelle jede einzelne Position manuell abzufragen, habe dort aber das Problem dass ich zum einen nicht weiß wie ich am schlausten hoch zählen kann, und dazu die Loops so zu "begrenzen" dass ich keine out-of-bounce exception bekomme wenn ich Werte an die Funktion übergebe die sich am Rand des Arrays befinden.

Das ganze ist im übrigen für ein "Conways game of life" Spiel.

Also falls jemand so etwas schon mal gemacht hat oder eine elegantere Möglichkeit kennt als diese hier, wäre es nett wenn er mir hilft :)

Lg Valentin

Programmieren, Java, Informatik
Java mehrer Interatoren?

Erstmal Hallo,

ich muss für eine Aufgabe ein Programm schreiben:

package aufgabe11;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;


public class TeilaufgabeA {

	public static void main(String[] args) {
		
		ArrayList<String> mylist = new ArrayList<String>();
		
		mylist.add("Mein");
		mylist.add("kleiner");
		mylist.add("grüner");
		
		for(int i = 0 ; i < args.length; ++i) { // hier sollen die Kommandozeilenparamter von von hinten aus angehängt werden , also "Kaktus" , "steht".....
			mylist.add(args[args.length - i - 1]);
		}
		if(!mylist.contains("Hollari")) {
			mylist.add("Hollari");
		}else if(!mylist.contains("hollari")) {
			mylist.add("hollari");
		}else if(!mylist.contains("hollaro")) {
			mylist.add("hollaro");
		}
		
		 Iterator<String> iter = mylist.iterator(); 
	     while (iter.hasNext()) { 
	         String s = iter.next(); 
	         if(s.equals(",")) mylist.remove(s);//die Kommas sollen entfernt werden
	     }
	     
	     int size = mylist.size() - 5;
	     for(ListIterator<String> lif = mylist.listIterator(size); lif.hasNext(); ) {
	    	 String k = lif.next(); //die einzelenen Strings sollen ausgegeben werden
	    	 System.out.print(k);
	     }


	}
}

Nun bekomme ich Exeption bei " String s = iter.next(); " mit der Kommandozeilenparamtereingabe : " "Balkon" , "am" , "draußen" , "steht" , "Kaktus" "

------------------------- Frage: Warum bekomme ich hier eine Exeption ? --------------------

Gruß

Computer, Programmieren, Schleifen, Java, Informatik
Weiß jemand, wie ich die lock und conditions in java hier zu programmieren habe?

Hi, ich beschäftige mich zurzeit mit lock und conditions.

public class LockedDataObject extends DataObject {


    /** Anzahl aktueller Leser */
    int noReaders;


    /** Wahr, wenn Schreiber momentan wartend oder schreibend */
    boolean writer;


    /**
     * Condition-Variable zum Schlafenlegen von bzw. Aufwecken des Schreibers
     */
    Condition condWrite;


    /** Condition-Variable zum Schlafenlegen bzw. Aufwecken der Leser */
    Condition condRead;


    /**
     * Sperre, um alle oberen Variablen zu schützen. Bevor auf eine der
     * Variablen zugeriffen wird, muss ggf. diese Sperre erworben werden. Der
     * Erwerb der Sperre soll *nur dann* erfolgen, wenn es für die korrekte
     * Ausführung unbedingt notwendig ist. Das ist bei einem ändernden Zugriff
     * nur dann der Fall, wenn andere Threads die entsprechende Variable
     * zeitgleich lesen oder schreiben können. Bei einem lesenden Zugriff soll
     * die Sperre nicht erworben werden, wenn andere Threads zeitgleich nur
     * lesend, aber nicht schreibend, auf die entsprechende Variable zugreifen
     * können.
     */
    ReentrantLock lock;


    public LockedDataObject() {
        this.lock = new ReentrantLock();
        this.condRead = lock.newCondition();
        this.condWrite = lock.newCondition();
        this.noReaders = 0;
        this.writer = false;
    }


    public int sum() {
        // Beachten Sie durchgängig die korrekte Verwendung der Sperrvariable
        // "lock". Erwerben Sie die Sperre nur, falls unbedingt notwendig.


        // 1. Solange ein Schreiber wartet oder schreibt, schlafenlegen.


        // 2. Anzahl der Leser um 1 erhöhen.


        // 3. Summe bilden
        int sum = super.sum();


        // 4. Anzahl der Leser erniedrigen und ggf. Schreiber aufwecken.


        // 5. Summe zurueckgeben
        return sum;
    }


    public void randomSwap() {
        // Beachten Sie durchgängig die korrekte Verwendung der Sperrvariable
        // "lock". Erwerben Sie die Sperre nur, falls unbedingt notwendig.


        // 1. Anzeigen, dass ein Schreiber wartet.


        // 2. Schlafenlegen, solange noch mindestens ein Leser aktiv


        // 3. Elemente vertauschen
        super.randomSwap();


        // 4. Anzeigen, dass kein Schreiber mehr wartet/schreibt und
        // ggf. Leser aufwecken.
    }
}




Diese Aufgabe haben wir als Übung erhalten, der Dozent meinte, durch die Kommentare, sei das eine 5 Minuten Aufgabe, damit können wir mal üben.

Es sei so einfach, dass keine Lösungen nötig seien..., da ja alles kommentiert sei.

Die Aufgaben stehen bei den beiden Methoden, also was genau man zu tun hat...

Wie wprde man das lösen? Könnte das jemand kurz tun, damit ich mal sehe, wie man hier vorgeht, ich lerne mehr beim sehen einer korrekten Lösung, wenn ich ein Thema neu lerne.

Ich konnte mir zu allem was denken, außer zu: "    // 1. Anzeigen, dass ein Schreiber wartet." Wie soll man das zeigen?

Computer, Schule, Programmieren, Java, Informatik

Meistgelesene Fragen zum Thema Informatik