Index des kleinsten Wertes eines Arrays

[Christoph H. (christoph_b)]

Hallo

Ich habe folgendes Problem

Ich muss in einem Array den niedrigsten und den 2 niedrigsten Wert 
finden und den Index davon ausgeben. Das ganze leider in C

zb.
A[]== {951, 953, 896, 33, 932, 973}

kleinster Wert ist 33 also A[3] also den Wert 3
2 kleinster Wert ist 896 also A[2] also Wert 2

Ich blicke da momentan nicht durch wie ich das am besten angehe ;-)

Gruß Christoph

[Fabian O. (xfr)]

Du legst Dir zwei Variablen an, die den Index des niedrigsten und 
zweitniedrigsten Werts enthalten sollen. Als initiale Indizes nimmst Du 
0 und 1 (je nachdem, welcher Array-Wert größer ist).

Dann gehst Du in einer Schleife alle Elemente des Arrays durch und 
vergleichst den aktuellen Wert mit den bisher niedrigsten Werten, deren 
Indizes in den beiden Variablen stehen. Wenn er kleiner ist, 
aktualisierst Du die Variablen. Wenn Du einmal durch bist, stehen in den 
beiden Variablen die richtigen Indizes.

[Jannik G. (jannik_96)]

Hallo,

ich programmiere eigentlich nicht mit C, aber so würde ich es machen:
Erstmal nach der Größe sortieren lassen,
dann im Ursprungsarray den Index suchen, bei dem der Wert gleich dem 
ersten des sortierten Arrays ist.

grüße
jannik

'Edit: Da war wohl jemand schneller.

[Frank M. (ukw) (Moderator)]

Jannik G. schrieb:
> Erstmal nach der Größe sortieren lassen,

Der Schritt ist zuviel. Um zu sortieren, musst Du vergleichen. Wenn Du 
vergleichst, bist Du sowieso schon fertig. Die Umsortiererei kannst Du 
Dir also sparen.

[Klaus W. (mfgkw)]

Jannik G. schrieb:
> ich programmiere eigentlich nicht mit C, aber so würde ich es machen:
> Erstmal nach der Größe sortieren lassen,
> dann im Ursprungsarray den Index suchen, bei dem der Wert gleich dem
> ersten des sortierten Arrays ist.

D.h. du sortierst das ganze Feld um, (Laufzeitordnung mindestens 
O(n*log(n))), um anschließend das Feld linear zu durchlaufen (O(n)), 
obwohl auch eine lineare Suche reicht?


>
> grüße
> jannik
>
> 'Edit: Da war wohl jemand schneller.

Kein Wunder bei dieser Vorgehensweise :-)

Mein Vorschlag: einen Zeiger auf das kleinstwertige Feldelement anlegen 
(ich nenne ihn mal pMin) und auf Verdacht mit der Adresse des ersten 
Feldelements initlaisieren (pMin=&feld[0]).
Dann ab [1] das Feld durchlaufen und jedes Elemente mit *pMin 
vergleichen. Falls das aktuelle Element kleiner ist als *pMin, dann pMin 
auf das aktuelle setzen.

Wenn man zum Schluß nicht den Zeiger braucht, sondern den Index, dann 
(pMin-feld) nehmen, das ist der Index.

[Karl H. (kbuchegg)]

Und nicht auf die Sonderfälle vergessen.
Welches ist der korrekte Index, wenn das Feld nur 1 Element groß ist? 
Welches, wenn das Feld überhaupt keine Elemente enthält?

[Lupo (Gast)]

In einem Durchgang:

Input:
ARRAY_MAXINDEX = Höchster Index im Array

int a[MAXINDEX+1];
int i, m, k, n1, n2;

n1 = -1;
n2 = -1;
k = MAXINT;
m = ARRAY_MAXINDEX;

for (i = 0; (i <= m); i++)
{
  if (a[i] < k1)
  {
    n2 = n1;
    k1 = a[i];
    n1 = i;
  }
}

Resultate:

n1 = Index kleinstes Element (Wert in k)
n2 = Index zweitkleinstes Element
n1, n2 in [0..MAXINDEX] oder -1, falls nicht vorhanden

[Karl H. (kbuchegg)]

@Lupo


keine gute Idee.
Er ist Schüler und soll was lernen. Das tut er aber nicht, wenn du ihm 
jetzt schon den Code vorwirfst. Erst mal soll er sich selber die 
Programmstrategie zurechtlegen. Auf dem Papier mal ein bischen testen. 
Solange, bis er eine brauchbare Konzeptidee hat die er auch 
ausformulieren kann.
Wenn er dann noch programmtechnische Schwierigkeiten hat, dann hilf ihm. 
Dagegen ist nichts zu sagen. Aber erst mal muss er mal mit einem 
Gedankengang rüberkommen (der noch den einen oder anderen Fehler 
enthalten kann). In der ersten Lernphase ist die Beschäftigung mit dem 
Problem schon fast wichtiger als die Umsetzung.
Du musst dir immer denken: Auf diesem Lernlevel ist es wichtiger, dass 
er in möglichst allen Details versteht, warum ein Verfahren sein Problem 
löst. Das er danach ein Programm hat ist eher ein Abfallprodukt davon.

[Lupo (Gast)]

Karl Heinz Buchegger schrieb:
> Er ist Schüler und soll was lernen.

Das blieb mir verborgen - und über genügend Greise, deren Belehrung 
keinerlei wirtschaftlichen Nutzen mehr verspricht, dürfte Deutschland 
verfügen. So bleibt als Motivation zu helfen lediglich Altruismus.

[Simon K. (simon)]

Christoph B. schrieb:
> Ich muss in einem Array den niedrigsten und den 2 niedrigsten Wert
> finden und den Index davon ausgeben. Das ganze leider in C

Wieso "leider"?

[Verwirrter Anfänger (Gast)]

Lupo schrieb:
> Input:
> ARRAY_MAXINDEX = Höchster Index im Array
> int a[MAXINDEX+1];
> int i, m, k, n1, n2;
>
> n1 = -1;
> n2 = -1;
> k = MAXINT;
> m = ARRAY_MAXINDEX;
>
> for (i = 0; (i <= m); i++)
> {
>   if (a[i] < k1)
>   {
>     n2 = n1;
>     k1 = a[i];
>     n1 = i;
>   }
> }


Ich denke hier gibts auch ein Problem, wenn a[n1] < a[i] < a[n2], oder 
hab ich was übersehen?

[Bernd (Gast)]

Lupo schrieb:
> So bleibt als Motivation zu helfen lediglich Altruismus.
du hilfst ihm aber nicht

es gibt da noch was über das du dich Mal informieren solltest:
http://de.wikipedia.org/wiki/Helfersyndrom

[Bernd (Gast)]

ich nehms zurück, du hilfst ihm doch, da sind ja so viele Fehler drin,
wenn er die rausfindet lernt er doch was
abgesehen von Tippfehlern: was ist mit 2 gleichen kleinsten Zahlen?

[MagIO (Gast)]

@Verwirrter Anfänger:
Richtig, ... kann aber nur passieren, wenn der erste Wert schon der 
kleinste ist.
Man sollte also besser 2 if-Bedingungen benutzen. Eines für k1/n1 und 
eines für k2/n2.

Aber mehr wird nicht verraten ;o)

[Christoph H. (christoph_b)]

Danke für die Anregungen. Werde mir das morgen mal genauer Anschauen und 
mich bei bedarf nochmals melden ;-)

[Drobel (Gast)]

Karl Heinz Buchegger schrieb:

> Er ist Schüler und soll was lernen.

So oder so kein Problem, da das Programm nicht funktioniert.

[Tim T. (tim_taylor)]

Schüler lernen eh nichts gescheites mehr (in der Schule), also kann man 
auch direkt die Lösung geben:

int a[]; // Beispielhaft mit einer bestimmten Anzahl an Elementen
int i, anzahl, min;

min = 0; // Zählung ab 0. Element, welches erstmal das Kleinste ist.
anzahl = sizeof(a) / sizeof(int); // Größe des Arrays durch die Größe eines Elementes ist die Anzahl der Elemente

for (i = 1; i < anzahl; i++) if (a[i] < a[min]) min = i;

Der Code ermittelt den Index des ersten auftretens der kleinsten Zahl, 
wenn die if-Abfrage auf <= testet, wird das letzte Auftreten getestet.

Wer will kann jetzt noch den Sonderfall, mit einem leeren Array 
behandeln.

[Karl H. (kbuchegg)]

Lupo schrieb:
> Karl Heinz Buchegger schrieb:
>> Er ist Schüler und soll was lernen.
>
> Das blieb mir verborgen

Die Aufgabenstellung ist eine typische Schulaufgabe.
(und die Worte 'muss' und 'leider' erzählen den Rest).

[Christoph H. (christoph_b)]

ich kann euch versichern das es keine Schulaufgabe ist. Aus diesem Alter 
bin ich raus.

Es geht um ein Projekt das ich in der Schule abgeschlossen habe und wo 
ich nun in meine Freizeit weitermache und es gerne verbessere.

Ich versuche die Rasenkante mittels 16 IR Sensoren zu erkennen. Um 
Fehler auszubessern probiere ich es gerade mittels Korrelation.

Das "Leider" kommt daher da ich die Funktionen von C# sehr schätze und 
mir das leider in C fehlt.

Gruß Christoph

[Karl H. (kbuchegg)]

OK, ich nehm (fast) alles zurück.

(Traurig was C# und Java mit dem Nachwuchs machen. Das der Nachwuchs 
keine dynamischen Datenstrukturen mehr implementieren kann, daran hab 
ich mich schon gewöhnt. Das man allerdings keine Idee hat, wie man das 
kleinste Element in einem Array findet, das ist neu. Dabei ist das DIE 
(grossgeschrieben) Standardaufgabe für die erst Übung mit Arrays)

[Bernd (Gast)]

Tim T. schrieb:
> Der Code ermittelt den Index des ersten auftretens der kleinsten Zahl,
> wenn die if-Abfrage auf <= testet, wird das letzte Auftreten getestet.

tja, schönes Programm, aber leider Themaverfehlung, das war nicht die 
Fragestellung,

wird ja auch immer beklagt das das Textverständnis der heutigen 
Generation zu wünschen läßt ;-)

[Tim T. (tim_taylor)]

Bernd schrieb:
> tja, schönes Programm, aber leider Themaverfehlung, das war nicht die
> Fragestellung,

Stimmt, hatte nur die Überschrift gelesen.

Dann eben ergänzt:

int a[]; // Beispielhaft mit einer bestimmten Anzahl an Elementen
int i, anzahl, min, min_b;

min = 0; // Zählung ab 0. Element, welches erstmal das Kleinste ist.
anzahl = sizeof(a) / sizeof(int); // Größe des Arrays durch die Größe eines Elementes ist die Anzahl der Elemente

for (i = 1; i < anzahl; i++) if (a[i] < a[min]) min = i;

if (min == 0) min_b = 1; // Falls das 0. Element tatsächlich das kleinste war.
else min_b = 0;

for (i = min_b+1; i < anzahl; i++) if ((a[i] < a[min_b]) && (min_b != min)) min_b = i;