Kleinster Wert aus Array

[newkid]

fuer die mathematiker unter euch

also ist nicht ganz die komplesitaet von O( n log n ) weil man ja n mal macht ( n in diesem fall 200 )

also ist es

n mal n log n

[GeorgeHomes]

Ich weiß ja das Quicksort verdammt schnell ist, aber effektiv gesehen muß er doch auch jedes Element midnestens einmal vergleichen um es einordnen zu können, also müsste das doch auf jeden fall langsamer sein als die Lineare durchsuchvariante. Ich sehe da schwarz.

Das einzige was du machen kannst, ist die Suche beim fund eines minimalwertes (z.B. 0) zu beenden.

[Andorxor]

Du kannst den Vergleich ja beim Füllen des Arrays machen da musst du doch sowieso alle Elemente durchlaufen.

[newkid]

ZITAT:
also müsste das doch auf jeden fall langsamer sein als die Lineare durchsuchvariante
ZITAT ENDE:

lesen bildet

http://www.quick-sort.de/refqsort_2.htm

ganz gut

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm

heisst auch "teile und hersche" deswegen hat O(n log n) also nichts mit auf jeden fall langsamer

natürlich im worstcase O(.....) ( sag ich jetzt lieber nicht )

-----------------

das ganze ist natürlich dumm, wenn das array nicht sortiert werden darf.

ausser man sortiert und merkt sich was vertauscht worden ist ( mehr speicheraufwand )

und macht dann in einer ruhigen min alle rückgaängig, hehe ( ich hoff den letzen teil nimmt jetzt niemand zu ernst )

[newkid]

GeorgeHomes schrieb:

Das einzige was du machen kannst, ist die Suche beim fund eines minimalwertes (z.B. 0) zu beenden.

meine lieblingsstelle von dir

was wenn es sich um kontostände ect. handelt.
darfs da keine negativen zahlen geben?

ok, du schriebst ja auch z.b. ( aber trozdem )

[das_brot]

Moin,

Hab's mal so versucht:

int array [200][200];

void CTestDlg::OnButton1() // array mit zufallszahlen füllen
{

for(int a = 0; a<200;a++)
{
	for(int b = 0; b<200; b++)
	{
		array [a][b] = rand();
	}
}
}

void CTestDlg::OnButton2() //kleinsten wert finden und ausgeben
{

int f1 = 0;
int f2 = 0;
int CH = array [0][0];

	for(int a = 0; a<200;a++)
	{
		for(int b = 0; b < 200; b++)
		{
			if(array [a][b] < CH)
			{
				CH = array [a][b];
				f1 = a;
				f2 = b;
			}
		}
	}

CString sa;
sa.Format("%d in [%d][%d]",array[f1][f2],f1,f2);
MessageBox(sa);
}

Ergebnis: Er findet den Wert in weniger als einer Sekunde,
entweder hab' ich einen Fehler im Code gemacht, oder diese Lösung ist brauchbar

Gruss

[edit]
so, jetzt sollte der Code sogar stimmen...
[/edit]

[newkid]

was an deinem code mir merkwürdig erscheint, ist die tatsache das du

f1,f2,ch deklarieren tust, aber keine werte initialisierst.

dann machst du 2 for schleifen
und in der 2ten prüfst du

ausserdem auch noch falsch, da ( array [a][b] > CH ) also sprich immer wenn im array ein groesserer wert steht, es muss aber ein kleinerer wert sein

also weiter, du prüfst dann

array [a][b] und dies hat einen wert. CH hat bis jetzt noch keinen wert.

da wahrscheinlich CH am anfang irgendwas mit minus n ( n sehr gross ) springt er rein.
ich häts anders gemacht in der 2ten for schleife

CH = array [0][0];  // jetzt hat CH den ersten wert.

//1.te for schleife

//2.te for schleife dann

if(array [a][b] < CH)   // kleiner zeichen (  nicht groesser !!!  )
{
    CH = array [a][b];
    f1 = a;
    f2 = b;
}

probierst jetzt mal aus. aber wie gesagt. diese linerare suche muss schnell sein beim heutigen PC. weiss auch nicht warum der so zeitkritisch programmieren will.

[GeorgeHomes]

@littlekid
Jetzt glaub ichs aber langsam. Wenn du auch mal eine Sekunde darüber nachdenkst, wirst du wohl auch darauf kommen das kein Sortieralgorytmus in der Lage ist mit Weniger Vergleichen auszukommen als Elemente vorhanden sind. Es muß jedes Element midestens einmal verarbeitet werden, um es einsortieren zu können. Das bedeutet eine absolute Minimalzahl von n Vergleichen. Dies wiederum ist die konstante der Linearen Methode, sprich, sie ist unter keinen Umständen schneller. Im allerbesten Fall wäre Sie genauso schnell.

[fletscheru]

GeorgeHomes schrieb:

@littlekid
Jetzt glaub ichs aber langsam. Wenn du auch mal eine Sekunde darüber nachdenkst, wirst du wohl auch darauf kommen das kein Sortieralgorytmus in der Lage ist mit Weniger Vergleichen auszukommen als Elemente vorhanden sind. Es muß jedes Element midestens einmal verarbeitet werden, um es einsortieren zu können. Das bedeutet eine absolute Minimalzahl von n Vergleichen. Dies wiederum ist die konstante der Linearen Methode, sprich, sie ist unter keinen Umständen schneller. Im allerbesten Fall wäre Sie genauso schnell.

du bist ein echt ein noob ( anfänger )

newkid hat recht !

hast du schon mal was von TEILE UND HERSCHE gehört???

Sagt dir Rekursion was???? weisst was das ist???

kauf dir ein buch über "algorithmen und datenstrukturen"

dann kannste mitreden.

bei Quicksort wird auch jedes element verglichen, ABER REKURSIV ! das ist der unterschied.

deswegen ist es ( bei unsortierten elementen und zufälligen PIVOT element ) schneller als linear.

aber das verstehst du nicht.

wie gesagt kauf dir ein buch und lies erstmal, bevor du hier irgendwelchen "inteligente" sachen posten tust.

checks mal ab

[fletscheru]

ok will mal nicht so sein und ich geb dir ein tipp

eine übersicht

ersetzt kein gutes buch.

http://www.math.tu-freiberg.de/~ernst/Lehre/AD/adKapitel5.pdf

wenn dir das zu hoch ist dann kauf dir

ALGORITHMEN UND DATENSTRUKTUREN oder ( untertitel )
algo was?? for dummies band 1-8

[GeorgeHomes]

Warum soll eine Funktion die sich selbst bis zum auftreten einer Abbruchbedingung aufruft, weniger Vergleich brauchen als eine die das nicht tut?

Es geht ja nicht darum, die Liste Linear zu sortieren sodern bloß darum, alle Werte mit jeweils einem anderen zu vergleichen.

Du hast doch selbst gesagt

bei Quicksort wird auch jedes element verglichen, ABER REKURSIV ! das ist der unterschied.

Das ist sind doch dann im minimalfall n vergleiche. Wo ist dann mein Denkfehler? Wie zum verrecken soll irgendetwas das auch mindestens 40000 vergleiche braucht, schneller sein als:

int array[40000];
int value;
for (int i=0;i<40000;i++)
{
  if (array[i]<value) ...
}

Nein, da muß ich dir zustimmen, das verstehe ich beim besten willen nicht.

Dann zeig mir doch einfach mal ein Codebeispiel, das mit sortieren aus einem Array schneller das kleinste Element ermittelt als das nachfolgende. Wenn ihr das könnt, bin ich ganz ruhig und fange schon mal an zu schmökern.

void Min(int* pArray, int iElementCount, int &iOutMin, int &iOutMinPos)
{
  iOutMinPos = 0;
  iOutMin = pArray[0];
  for (int i=1; i<iElementCount; i++)
  {
    if (pArray[i]<iOutMin)
    {
      iOutMin = pArray[i];
      iOutMinPos = i;
    }
  }
}

[fletscheru]

sag mal ehrlich

hast den link überhaupt angeschaut????

lol sag ich nur

ok hier mal ne aufgabenstellung

http://pimpf.pi.informatik.tu-darmstadt.de/loop/aufgaben/fischer/own/sort/quick/

und hier die lösung

hier mal ein ZITAT von der nachfolgenden site ( die ich gleich nenne werde )

*****************
Quicksort ist wahrscheinlich der komplizierteste der 4 Algorithmen. Dennoch ist es gut, wenn man ihn versteht, denn er heißt nicht umsonst Quicksort. Jedenfalls werden wir Schritt für Schritt vorgehen, weil es unter Umständen nicht ganz so leicht ist. Im Folgenden sind also die wichtigsten Schritte des Quicksort Algorithmus aufgelistet:
********************************

ok jetzt weisst das es gut ist ihn zu verstehen

und es wird auch ein bsp für REKURSION gennant am berühmten bsp der fakultät

also dann man dein versprehchen war wenn du das jetzt hier sehen tust ( mit c++ code )

http://www.zfx.info/Tutorials.php?ID=79

und wenn du es jetzt immer noch nicht schnallst dann ......

PS

was glaubst du warum es verschiedene sortieralgorithmen gibt???? wenn die lineare das beste ist und man nicht drunter kann. ALSO WARUM wird zeit und geld da reingesteckt??? sind alle doofer als du????

checks mal ab

machst ja eh nicht da du den ersten link ja nicht mal nachgegangen bist

[GeorgeHomes]

was glaubst du warum es verschiedene sortieralgorithmen gibt???? wenn die lineare das beste ist und man nicht drunter kann. ALSO WARUM wird zeit und geld da reingesteckt??? sind alle doofer als du????

Ich hatte doch nie vor die verdammte Liste zu sortieren. Ich habe auch nie behauptet, das Quicksort nicht schneller ist als ein Linearer Sortieralgorithmus. Mir ist bewusst das Quicksort einer der besten Sortieralgorythmen ist. Es geht doch überhaupt nicht darum ob Quicksort besser ist als ein anderer Soriteralgorythmus.

Es geht darum ob es sinn macht, überhaupt irgendeinen Sortieralgorythmus zu verwenden um den kleinsten Wert in einem Array ausfindig zu machen.

Entweder du zeigst mir jetzt eine Funktion die mit einem Sortieralgorythmus den Minimalen Wert eines Arrays schneller ermittelt als meine oben genannte Funktion oder du hörst endlich auf mich die ganze Zeit anzugreifen.

P.S.
Les du dir meine Posts bitte auch mal komplett durch.

[fletscheru]

also zum letzen male

deine lineare suche läuft darauf aus

das du bei array[200]

was machen musst?

eine schleife machen

int wert = array[0];
dann ne schleife wo du 199 male etwas machen musst. also 199 male vergleichen

ob der derzeitige wert array[i] kleiner ist als der akt. wert

wenn das der fall ist dann kriegt der wert den neuen wert.
diese zuweisung musst du in der regel ( durchschnitt ) ca. 100 mal machen.

also zum rekapitulieren

199 schleifen durchgänge ( 199 male etwas machen, die vergleiche eben ) und ca. 100 male den wert zuweisen. ich geh jetzt nicht von best oder worst case aus.

beim sortieren gehts is in der regel ( wieder nicht best oder worst case ) logarithmisch zu ( wegen der rekursion die drin steckt )

weisst du das die logarithmus funktion die umkehrfunktion der expon. fkt. ist?

also bei 200 werten musst du etwas dann ( aufgerundet ) 15 male machen. eben links recht pivot element ( so wie in den links beschrieben )

und am ende EINE zuweisung machen. FOLGENDE: int KleinsterWert = array[0];
da ganz links der kleinste wert ist.

also zum wiederholen ( im average case )

linear: 199 durchläufe und 100 zuweisungen
quicksort: 15 durchläufe 1 zuweisung

newkid sagte auch ( lies mal ), das das array dann sortiert ist. aber wenn du nur den kleinsten wert haben willst ( und das interesiert ja jetzt ) dann ist es schneller (idr ) als lineare suche

zudem du dann auch wenn du weitere male suchen willst

( z.b. grösstes element ) eine zuweisung nur machen musst.

jede andere zahl kann man mit der BINÄR SUCHE MACHEN

deswegen lohnt es sich auf ein array ( wo man öfters mal braucht ) das zuerst zu sortieren. dann kann man immer schneller suchen! und wenn sich werte verändern ( dazu kann mein ein flag setzen das status überprüft ) dann kann man bubblesort oder anders verfahren nehmen.

kapiert???
also wenn man ein array hat ( kleines ) z.b. array[10] dann macht man nicht extra den ganzen code rein zum sortieren und so.

wenn man ein grosses array hat, dann sortiert man ( ausser man darf es nicht, da die eihenfolge wichtig ist ) das array zuerst und hat dann den wert.

kapierst es jetzt

noch ein bsp.

array[10 000}

linear 9 999 durchläufe
quicksort 100 durchläufe

was ist besser??? aber das verstehst du einfach nicht.

[fletscheru]

GeorgeHomes schrieb:

Entweder du zeigst mir jetzt eine Funktion die mit einem Sortieralgorythmus den Minimalen Wert eines Arrays schneller ermittelt als meine oben genannte Funktion oder du hörst endlich auf mich die ganze Zeit anzugreifen.

also angreifen tue ich dich nicht. ich will es für dich nur begreiflich machen

ich hab dir sogar den link gegeben wo der sortieralgo. drauf ist.

den findest idr auch bei MFC

jetzt mach mal ein sehr sehr grosses array. dann mach mal beide methoden und tue mal die zeit messen. MFC untersützt das doch oder? oder tue meinetwegen vorm suchbeginn eine variable die akt zeit ( mit microsec ) zuweisen und am schluss auch und dann haste die genaue differenz.

mach das doch mal. wie gesagt lohnt es sich bei grossen arrays. bei aray[2] ist es nicht so der hit. kapiert? ne gell. so das war mein letzter post. ausser du machst die versuche und machst screenshots und tust mich vom gegenteil überzeugen ( wegen beweiss ). alles andere ( deine erklärungsversuche ) die kannst behalten, genauso wie meine rechtschreibfehler.

[GeorgeHomes]

array[10 000}

linear 9 999 durchläufe
quicksort 100 durchläufe

Du redest die ganze Zeit über die Durchläufe, und ich über die Vergleiche. Nur weil ich weniger durchläufe habe, heist das ja nicht, das es schneller ist. Es kommt ja darauf an, was in jedem Durchlauf gemacht werden muß. In jedem der 9999 Durchläufe der linearen Methode muß ja nur ein Wert mit dem anderen verglichen, und eventuell getauscht werden.

Ich habe jetzt auch mal einen kleinen Code geschrieben, der die Geschwindigkeit der linearen Suche mit der des Quicksorts (ohne suche) vergleicht.

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <conio.h>

void Min(int* pArray, int iElementCount, int &iOutMin, int &iOutMinPos)
{
	iOutMinPos = 0;
	iOutMin = pArray[0];
	for (int i=1; i<iElementCount; i++)
	{
		if (pArray[i]<iOutMin)
		{
			iOutMin = pArray[i];
			iOutMinPos = i;
		}
	}
}

void QuickSort(int* pData, int iLow, int iHigh)
{
	int i=iLow;
	int j=iHigh;
	int x=pData[(iLow+iHigh)/2];

	// Aufteilung
	while (i<=j)
	{
		while (pData[i]<x) i++;
		while (pData[j]>x) j--;

		if (i<=j)
		{
			int iTemp = pData[i];
			pData[i] = pData[j];
			pData[j] = iTemp;
			i++;
			j--;
		}
	}

	if (iLow<j) QuickSort(pData, iLow, j);
	if (i<iHigh) QuickSort(pData, i, iHigh);
}

#define TESTCOUNT		100
#define ARRAYSIZE		100000

int main(int argc, char* argv[])
{
	srand( (unsigned)time( NULL ) );

	LARGE_INTEGER avgsort;
	LARGE_INTEGER avgsearch;

	avgsort.QuadPart = 0;
	avgsearch.QuadPart = 0;

	for (int i=0;i<TESTCOUNT;i++)
	{
		int pTest[ARRAYSIZE];
		for (int i=0; i<ARRAYSIZE; i++) pTest[i] = rand();

		LARGE_INTEGER time1;
		LARGE_INTEGER time2;
		LARGE_INTEGER sorttime;
		LARGE_INTEGER searchtime;

		QueryPerformanceCounter(&time1);
		int iMin;
		int iMinPos;
		Min(pTest, ARRAYSIZE, iMin, iMinPos);
		QueryPerformanceCounter(&time2);

		searchtime.QuadPart = time2.QuadPart - time1.QuadPart;
		avgsearch.QuadPart+=searchtime.QuadPart;

		QueryPerformanceCounter(&time1);
		QuickSort(pTest, 0, ARRAYSIZE-1);
		QueryPerformanceCounter(&time2);

		sorttime.QuadPart = time2.QuadPart - time1.QuadPart;
		avgsort.QuadPart+=sorttime.QuadPart;
	}

	avgsearch.QuadPart/=TESTCOUNT;
	avgsort.QuadPart/=TESTCOUNT;

	int iAvgSearch = avgsearch.QuadPart;
	int iAvgSort = avgsort.QuadPart;

	printf("Der Suchvorgang hat im Durchschnitt %i gedauert", iAvgSearch);
	printf("\nDer Sortiervorgang hat im Durchschnitt %i gedauert", iAvgSort);

	getch();

	return 0;
}

Ich habs mal durchlaufen lassen und bei mir kommt folgendes Ergebnis raus.

Der Suchvorgang hat im Durchschnitt 1336 gedauert
Der Sortiervorgang hat im Durchschnitt 84614 gedauert

Also ist die lineare Suche im Durschnitt 63x schneller als der Quicksort.

Es wurde ja auch schon gesagt, das sich der Quicksort vor allem lohnen würde, wenn man das ganze öfter machen muß und den Quicksort nur dann ausführt, wenn sich der Array geändert hat. Das ist aber irgendwie auch blödsinn, denn wenn sich der Array nicht verändert hat, hat sich der kleinste Wert mit Sicherheit auch nicht verändert.

[tobis79211]

Hi, ich möchte mich garnicht so sehr in Euren Kleinkrieg einmischen, aber ich würde gerne mal ein kleines Rechenbeispiel mit 2 Möglichkeiten machen... An sich möchte ich sagen, daß ich Mathe + Informatik studiere, als schon denke eine Ahnung über Exp.-Funktionen etc zu haben! Ich würde mich auch sehr freuen, wenn ihr Euch durchlest was ich schreibe, bevor ich irgendwie angegriffen werde:

- Ich geh hier einfach mal von 200 Elementen aus. Wie wir alle einsehen ist das leicht auf das 200*200-Problem übertragbar! Wer es nicht einsieht sollte anfangen zu studieren!

ok, dann los:

- Möglichkeit a) lineare Suche (NICHT "linear Sortieren", was immer das ist!)

Dies bedeutet, daß jedes Element mit dem "momentan kleinsten" verglichen wird, ergo: O(n) Vergleiche, also 200... eingesehen? denke schon!

- Möglichkeit b) QSort

Das Feld wird mit QSort sortiert und man merkt sich den kleinsten Wert!
So, zur Info: Welche Laufzeit hat QSort? O(nlogn), das kennen wir ja alle, nicht? Gut, dann setzen wir das mal ein: 200*log(200)=460.

Nun interpretieren wir das alle mal, bevor wir uns beschimpfen:

Vorteil von QSort ist, daß das Feld danach sortiert ist, man kann also weiter beliebige Werte in O(logn) suchen. Das ist ne tolle Sache, da der Aufwand bei n Elementen dann insgesamt O(nlogn + nlogn)=O(2nlogn), also natürlich kleiner als O(n*n)=O(n^2) bei linearer Suche ist! Bei NUR EINEM Element braucht man natürlich aber nlogn Vergleiche, wohingegen man bei linearer Suche nur n Vergleiche braucht!

Ergo: für die Suche nach EINEM kleinsten Element ist die lineare SUCHE am schnellsten! QSort benötigt O(logn-1) mal mehr Aufwand. Wird die Suche öfters wiederholt, dann sollte man natürlich wie beschrieben QSort verwenden und dann logarithmisch Suchen!

Gruß, Tobias

[as]

@newkid: O(n) ist weniger als O(n log n)

[GeorgeHomes]

@tobis79211
Da kann ich nur zu 100% zustimmen. Wie du schon sagtest, wenn man mehrere Werte suchen müsste hätte man mit QSort in Verbindung mit einer Binären suche ganz klar die bessere Lösung.

Normalerweise versuche ich bei Diskussionen auch sachlich zu bleiben und niemanden persönlich anzugreifen, aber da gibt es leider ein Problem. Was mich am meisten in Rage bringt, ist wenn ich für etwas zusammengeschissen werde, woran ich meiner Ansicht nach (Stimmt ja mit sicherheit nicht immer;)) nicht schuld bin. Oder eben wenn ich mich persönlich angegriffen Fühle, obwohl ich denke im Recht zu sein.

[newkid]

as schrieb:

@newkid: O(n) ist weniger als O(n log n)

stimmt

deswegen lag ich auch völlig falsch, da ich es mit logn verwechselt habe, sorry an allen. also bitte nicht sauer sein.