hallo,
ich habe folgende aufgabe gestellt bekommen...
ich habe dann also folgendes programmiert...
ich habe eine methode sort welche meinen sortierverfahren durchführt und einmal die methode bubblesort welche eben den bubblesort macht.
am anfang des programmes erstelle ich ein array mit der länge n,
und fülle dann dieses array zufällig mit irgendwelchen zahlen die größer 0 und kleiner/gleich n sind.
dann sortiere ich dieses array und gebe mir in ms aus wie lange ich dafür gebraucht habe.
in dem code oben ist n = 200000 (size) und es wird die methode sort ausgeführt.
ich habe mir eigentlich gedacht das es nichts wildes ist doch irgendwie habe ich ein ziemlich komisches gefühl...
vor allem wegen dem beispiel diagramm welches mit der aufgabe ausgegeben wurde:
(leider ohne achsen beschriftung -.-)
okay also wenn ich das diagramm mir so anschaue dann hat er da für 100000 zahlen fast 0 ms gebraucht und für 200000 ca 200 ms (ich gehe mal davon aus das es ms sind...) usw...
so aber wenn ich jetzt mein programm laufen lasse...
dann kommen folgende sachen raus:
bubblesort
n = 100000 -› 104483 ms
n = 200000 -› 506135 ms
sort
n = 100000 -› 46630 ms
n = 200000 -› 268897 ms
mehr als 200000 habe ich nicht gemacht weil mir das einfach zu lange dauert und ich irgendwie das gefühl habe das es nicht stimmen kann...
warum habe ich das gefühl?
naja also erst mal weil mein bubblesort einfach so lange braucht und zweitens das mein eigener sortieralgorithmus viel schneller ist als der bubblesort... aber trozdem lange braucht...
was sagt ihr dazu?
kann das wirklich sein?
vor allem die werte sind ja x mal größer als die auf dem beispieldiagramm...
ich habe folgende aufgabe gestellt bekommen...
ich habe dann also folgendes programmiert...
Java:
public class Main {
public static void main(String[] args) {
long start;
long end;
int size = 200000;
Integer[] array = new Integer[size];
for (int i = 0; i < array.length; i++) {
array[i] = ((int) (Math.random() * size) + 1);
}
start = System.currentTimeMillis();
sort(array);
end = System.currentTimeMillis();
System.out.println("Start: " + start);
System.out.println("End: " + end);
System.out.println("Time: " + (end - start));
}
public static void sort(Integer[] unsorted) {
Integer[] sorted = new Integer[unsorted.length];
Integer least = null;
Integer position = null;
for (int i = 0; i < sorted.length; i++) {
for (int j = 0; j < unsorted.length; j++) {
if (least == null || (unsorted[j] != null && unsorted[j] < least)) {
least = unsorted[j];
position = j;
}
}
unsorted[position] = null;
sorted[i] = least;
least = null;
}
}
public static void bubbleSort(Integer[] unsorted) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < unsorted.length - j; i++) {
if (unsorted[i] > unsorted[i + 1]) {
tmp = unsorted[i];
unsorted[i] = unsorted[i + 1];
unsorted[i + 1] = tmp;
swapped = true;
}
}
}
}
}ich habe eine methode sort welche meinen sortierverfahren durchführt und einmal die methode bubblesort welche eben den bubblesort macht.
am anfang des programmes erstelle ich ein array mit der länge n,
und fülle dann dieses array zufällig mit irgendwelchen zahlen die größer 0 und kleiner/gleich n sind.
dann sortiere ich dieses array und gebe mir in ms aus wie lange ich dafür gebraucht habe.
in dem code oben ist n = 200000 (size) und es wird die methode sort ausgeführt.
ich habe mir eigentlich gedacht das es nichts wildes ist doch irgendwie habe ich ein ziemlich komisches gefühl...
vor allem wegen dem beispiel diagramm welches mit der aufgabe ausgegeben wurde:
(leider ohne achsen beschriftung -.-)
okay also wenn ich das diagramm mir so anschaue dann hat er da für 100000 zahlen fast 0 ms gebraucht und für 200000 ca 200 ms (ich gehe mal davon aus das es ms sind...) usw...
so aber wenn ich jetzt mein programm laufen lasse...
dann kommen folgende sachen raus:
bubblesort
n = 100000 -› 104483 ms
n = 200000 -› 506135 ms
sort
n = 100000 -› 46630 ms
n = 200000 -› 268897 ms
mehr als 200000 habe ich nicht gemacht weil mir das einfach zu lange dauert und ich irgendwie das gefühl habe das es nicht stimmen kann...
warum habe ich das gefühl?
naja also erst mal weil mein bubblesort einfach so lange braucht und zweitens das mein eigener sortieralgorithmus viel schneller ist als der bubblesort... aber trozdem lange braucht...
was sagt ihr dazu?
kann das wirklich sein?
vor allem die werte sind ja x mal größer als die auf dem beispieldiagramm...
