3th/n-th größte Zahl in einem Array

Hallo Leute,

ich suche einen Alghorithmus um z.b das 3te größte Zahl in einem Array zu finden oder auch die n-te größte Zahl.
Ich kann das Array der Größe nach sortieren, was mich eine Laufzeit von n*log(n) kostet. In meinem Fall, ist es kein Array, sondern eine doppelt verkettete Liste. Ich müsste also erstmal ein Array der Länge an Elementen in der verketteten Liste allozieren, diese dann sortieren und dann die jeweilige Zahl raussuchen. Meist brauch ich nur die größten 4 Zahlen in diesem Array.

Ich habe einen Alghorithmus entwickelt der mir die 4 größten Zahlen in einem Array liefert, jedoch ist die Laufzeit schlecht(n = Länge des Array, m größte Zahlen => n*m vermute n²).

Kennt jemand einen Alghorithmus, wo ich das Array nur einmal durchlaufe und die 4 größten Zahlen erhalte?

Hier ein bisheriger Alghorithmus.

#include <stdio.h>
#include <stdlib.h>

int getMax(int *arr, size_t size, int max) {
	int i, maxVal = arr[0];
	for (i = 0; i < size; i++) {
		if (arr[i] > maxVal && arr[i] < max)
			maxVal = arr[i];
	}

	return maxVal;
}

int main(int argc, char **argv) {
	int arr[] = { 4, 5, 0, 44, 12, 41, 22, 3, 4 };
	int i, max = INT_MAX;

	for (i = 0; i < 4; i++) {
		max = getMax(arr, sizeof(arr) / sizeof(arr[0]), max);
		if (i)
			printf("%it ", i+1);
		printf("Groeste Zahl : %i\n", max);
	}

	return 0;
}

du nimmst dir n variablen, die du mit 0 (oder int-min) initialisierst, und durchläufst dann ganz normal das array und prüfst, ob das momentane element größer ist, als die n-größte variable (wenn ja ersetzen), dann ob sie auch noch größer ist, als die (n-1)-größte variable (wenn ja tauschen) usw und das dann für alle elemente.

wenn ich mich nicht irre ist das O(n).

Danke für die Lösung. Hier mein Code. Falls jemand was zu optimieren hat, bin ich für Anmerkungen dankbar.

#include <stdio.h>
#include <stdlib.h>

#define N 4

#define SWAP(type, a, b) \
{ \
	type __swap_temp; \
	__swap_temp = (b); \
	(b) = (a); \
	(a) = __swap_temp; \
}

int main(int argc, char **argv) {
	int i, j, arr[] = { 4, 5, 0, 44, 12, 41, 22, 3, 4 };
	int m[N] = { INT_MIN };

	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
		m[N - 1] = arr[i];
		for (j = N - 1; j > 0; j--) {
			if (m[j - 1] < m[j])
				SWAP(int, m[j - 1], m[j]);
		}
	}

	for (i = 0; i < N; i++)
		printf("%i\n", m[i]);

	return 0;
}

Hab eine Zeile vergessen.
Hier nun der richtige Code.

int main(int argc, char **argv) {
	int i, j, arr[] = { 4, 5, 0, 44, 12, 41, 22, 3, 4 };
	int m[N] = { INT_MIN };

	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
		if (arr[i] > m[N - 1]) {
			m[N - 1] = arr[i];
			for (j = N - 1; j > 0; j--) {
				if (m[j - 1] < m[j])
					SWAP(int, m[j - 1], m[j]);
			}
		}
	}

	for (i = 0; i < N; i++)
		printf("%i\n", m[i]);

	return 0;
}

Kleine Optimierung.

#include <stdio.h>
#include <stdlib.h>

#define N 4

#define SWAP(type, a, b) \
{ \
	type __swap_temp; \
	__swap_temp = (b); \
	(b) = (a); \
	(a) = __swap_temp; \
}

int main(int argc, char **argv) {
	int i, j, arr[] = { 4, 5, 0, 44, 12, 41, 22, 3, 4 };
	int m[N] = { INT_MIN };

	for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
		if (arr[i] > m[N - 1]) {
			m[N - 1] = arr[i];
			for (j = N - 1; j > 0 && m[j - 1] < m[j]; j--) {
				SWAP(int, m[j - 1], m[j]);
			}
		}
	}

	for (i = 0; i < N; i++)
		printf("%i\n", m[i]);

	return 0;
}

SeppJ

Funktion daraus machen.
Nicht mit INT_MIN initialisieren, sondern mit den ersten N Werten. Dann funktioniert das mit beliebigen Datentypen.