Hallo,
ich schreibe demnächst eine Prüfung, in der auch der Bubble Sort vorkommt. Vermutlich werden da so Geschichten, wie wie oft wird bei einem Bubble Sort verglichen usw abgefragt. Deshalb dachte ich mir, dass ich mir vielleicht ja ein paar Formeln merke, mit denen ich das einfach bestimmen kann.
Hier habe ich einen Bubble Sort geschrieben:
Die Anzahl der Tauschvorgänge kann man ja mit Hilfe von Inversion relativ einfach bestimmen.
Bei der Anzahl der Vergleiche, die Durchgeführt werden, habe ich folgende Formel gefunden: (n^2-n) /2
Und bei der Anzahl der Durchläufen (also die erste for Schleife) das: n-1
Bei der Formel (n^2-n) /2 und n -1 habe ich nur das Problem, das eben nicht berücksichtigt wird, dass der Bubble Sort ja schon fertig sein kann. (Das prüfe ich ja mit diesem swaped bool). Deshalb wollte ich mal fragen, ob es dafür denn auch eine Formel gibt, die mir das Leben in der Prüfung erleichtert, falls nach der Mindestanzahl der Vergleiche gefragt wird.
Vielen Dank schonmal.
ich schreibe demnächst eine Prüfung, in der auch der Bubble Sort vorkommt. Vermutlich werden da so Geschichten, wie wie oft wird bei einem Bubble Sort verglichen usw abgefragt. Deshalb dachte ich mir, dass ich mir vielleicht ja ein paar Formeln merke, mit denen ich das einfach bestimmen kann.
Hier habe ich einen Bubble Sort geschrieben:
Java:
;
public class HelloWorld
{
public static void Main(string[] args)
{
int[] numbers = {3, 56, 47, 546, 756, 72, 342, 35, 36};
SortArray(numbers);
PrintSortedArray(numbers);
}
public static void SortArray(int[] numbers)
{
int count = 0;
bool swaped = false;
for (int i = 0; i < numbers.Length - 1; i++)
{
swaped = false;
for (int j = 0; j < numbers.Length - (1 + i); j++)
{
count++;
Console.WriteLine("Geprüft: " + count + " mal");
if (numbers[j] > numbers[j + 1])
{
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
swaped = true;
}
if(!swaped) {
break;
}
}
}
}
public static void PrintSortedArray(int[] numbers)
{
foreach (int number in numbers)
{
Console.WriteLine(number);
}
}
}Die Anzahl der Tauschvorgänge kann man ja mit Hilfe von Inversion relativ einfach bestimmen.
Bei der Anzahl der Vergleiche, die Durchgeführt werden, habe ich folgende Formel gefunden: (n^2-n) /2
Und bei der Anzahl der Durchläufen (also die erste for Schleife) das: n-1
Bei der Formel (n^2-n) /2 und n -1 habe ich nur das Problem, das eben nicht berücksichtigt wird, dass der Bubble Sort ja schon fertig sein kann. (Das prüfe ich ja mit diesem swaped bool). Deshalb wollte ich mal fragen, ob es dafür denn auch eine Formel gibt, die mir das Leben in der Prüfung erleichtert, falls nach der Mindestanzahl der Vergleiche gefragt wird.
Vielen Dank schonmal.
