Array Sortieren?
Ich kann mit der folgenden Definition nichts anfangen.
Beispiele für solche Arrays:
A = {1,9,24,12,9}
A = {3,12,18,18,21,5}
Könnte mir bitte jemand helfen?
2 Antworten
Diese Klammern um n/2 ist die Gaußklammer. Also die Abrundung Funktion.
Bei deinem ersten Array ist n=5, somit ist Gauß(5/2)=Gauß(2.5)=2
Das Array ist summit sortiert, da die Elemente mit den Indices 0, 1 und 2 aufsteigend sortiert sind und die Elente mit den Indices 3 und 4 absteigend sortiert sind.
Beim zweiten Array sind die Elemente mit den Indices 0, 1, 2, 3 aufsteigend sortiert, und die Elemente mit den Indices 4, 5 absteigend sortiert (hier ist Gauß(6/2)=3)
Summit bedeutet ja auf deutsch Gipfel, wenn du also die Werte im Koordinatensystem plotten würdest (wobei die x Koordinate der Index ist) würden die Punkte wie ein Berg mit einer spitze aussehen.
Könnte mir bitte jemand helfen?
Wo genau hängt es denn? An sich sagt das nicht anderes aus als:
- Du hast ein Array mit n Elementen
- Die Indizes gehen von 0 bis n - 1
- Sind i und j beide kleiner oder gleich floor(n/2), sind die Werte immer aufsteigend - ist also i immer kleiner als j, ist A[i] <= A[j]
- Sind i und j beide größer als floor(n/2), sind die Werte immer absteigend - ist also i immer kleiner als j, ist A[i] >= A[j]
- nicht definiert, wenn i kleiner gleich und j größer als floor(n/2) ist - zumindest mit den Regeln
Es ist also quasi ein "Berg" - erst werden Werte größer, dann wieder kleiner
floor(n/2) ist hierbei nichts anderes als Abrunden. Aus 5 wird 2, aus 6 wird 3, aus 7 wird 3 usw ...
Könnte man das erste Array auch so sortieren: A={9,9,12,24,1} ?
Könnte man das erste Array auch so sortieren: A={9,9,12,24,1} ?
Ja, auch das wäre nach dem Screenshot eine summit-sortierte Liste. Die wichtige Kenngröße ist n = 5, damit ist also floor(n/2) = 2
Für die Indizes 0, 1 und 2 muss dann also gelten, dass A[i] >= A[j] wenn i >= j - das ist für 9, 9 und 12 gegeben, es ist immer aufsteigend
Für die Indizes über floor(n/2) = 2 muss es dann eben andersrum gelten: A[i] >= A[j] wenn i <= j - das ist für die beiden Werte (24 und 1) gegeben
Könnte man das erste Array auch so sortieren: A={9,9,12,24,1} ?