Hej, tak jak w temacie :) Może mi ktoś wytłumaczyć dlaczego w BubbleSort w java musimy zastosować dwie pętle for aby ono zadziałało ?
Dlaczego BubbleSort musi mieć dwa for'y ?
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Łódź
- Postów: 541
0
Żeby przejść przez wszystkie elementy, tyle razy ile jest tych elementów.
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: XML Hills
1
dlaczego w BubbleSort w java
To nie ma nic wspólnego z Javą.
musimy zastosować dwie pętle for aby ono zadziałało
Bo w jednej pętli możemy zrobić co najwyżej n-1 transpozycji sąsiednich elementów, a to zwykle nie wystarcza.
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: U krasnoludów - pod górą
- Postów: 4712
4
Kurcze taka ładna pogoda, siedze sobie nad jeziorkiem , a tu takie wyzwanie. Obale jakąś flaszkę, a potem pojade do domu i obale tą teorię z dwoma forami :)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 263
0
W żadnym wypadku nie musimy wykorzystywać dwóch forów.
Nie trzeba nawet jednego.
Można użyć dwa while'y :P.
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: U krasnoludów - pod górą
- Postów: 4712
13
Dobra - dobrałem się do kompa i powstaje takie eleganckie rozwiązanie:
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] array = {9, 5, 7, 1, 3, -1, 2, 8, 0};
try {
throw new ExceptionNotThrownException(0, array);
} catch (Exception e) {
System.out.println(Arrays.toString(array));
}
}
private static class ExceptionNotThrownException extends Exception {
public ExceptionNotThrownException(int i, int[] tablyca) throws ExceptionNotThrownException {
try {
int el = tablyca[tablyca.length-i-1];
try {
throw new ExceptionThrownException(0, tablyca);
} catch (ExceptionThrownException e) {}
throw new ExceptionNotThrownException(i + 1, tablyca);
} catch (ArrayIndexOutOfBoundsException auc) {}
}
}
private static class ExceptionThrownException extends Exception {
public ExceptionThrownException(int i, int[] tablyca) throws ExceptionThrownException {
try {
int el = tablyca[i];
int a = el - tablyca[i + 1];
tablyca[i] = tablyca[i + 1] / -(-(a-((a)&((a)>>31))) >> 31) ;
tablyca[i + 1] = el;
throw new ExceptionThrownException(i + 1, tablyca);
} catch (ArithmeticException ae) {
throw new ExceptionThrownException(i + 1, tablyca);
} catch (ArrayIndexOutOfBoundsException aoe) {}
}
}
}
Czuje, że da się to jeszcze objechać z wykorzystaniem generyków i dziedziczenia, ale przeleciałem poza Peak i już nie dam rady chyba.
(btw. rozwiązanie to mój tzw. klasyk).
- Rejestracja: dni
- Ostatnio: dni
- Postów: 5226
0
jarekr000000 napisał(a):
Kurcze taka ładna pogoda, siedze sobie nad jeziorkiem , a tu takie wyzwanie. Obale jakąś flaszkę, a potem pojade do domu i obale tą teorię z dwoma forami :)
Racja, po co komu pętle.
Wystarczy program do pisania kodu (advanced AI !!!) i lecimy każdą kolekcję :D
arr.ToList()
.ForEach
(
x => Console.WriteLine
(
$"if (arr[{arr.ToList().FindIndex(y => x == y)}] "
+ $"> arr[{arr.ToList().FindIndex(y => x == y) + 1}])"
+ Environment.NewLine
+ $"swap({arr.ToList().FindIndex(y => x == y)},"
+ $"{arr.ToList().FindIndex(y => x==y)+1});"
)
);
int[] arr = new int[4]{3,2,1,0}
int counter = 0;
Repeat:
if (arr[0] > arr[1])
swap(0,1);
if (arr[1] > arr[2])
swap(1,2);
if (arr[2] > arr[3])
swap(2,3);
counter++;
if (counter<arr.Count()-1)
goto Repeat;
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: Futurama
- Postów: 887
0
Pamiętaj, że bubblesort jest niefajny bo ma złożoność O(n^2)
Następnym razem polecam rzucić okiem na Visualgo, fajna reprezentacja graficzna wielu podstaw algorytmicznych oraz struktur danych.
Btw moim ulubionym jest brute force sorting, polecam bo rośnie wykładniczo, a my lubimy jak coś szybko rośnie, bo duże jest fajne ;)
- Rejestracja: dni
- Ostatnio: dni
- Postów: 263
1
Korzystając z dobrodziejstw Javy 8 udało mi się zrobić funkcyjnie, równolegle i super efektowne sortowanie przez wybieranie! Teraz już nigdy nie spojrzę na imperatywny kod tak samo. Jestem pewien, że to rozwiązanie jest warte pewnych niedogodności (tzn., że nie działa dla powtarzających się liczb).
List<Integer> numbs = Arrays.asList(10,9,8,7,6,5,4,3,2,1);
List<Integer> sorted = new ArrayList();
numbs.forEach( x ->
sorted.add(
numbs
.stream()
.parallel()
.mapToInt( y -> y)
.filter( z -> !sorted.contains(z))
.min()
.orElse(0)
)
);
System.out.println(sorted);
- Rejestracja: dni
- Ostatnio: dni
- Lokalizacja: U krasnoludów - pod górą
- Postów: 4712
2
Zobacz jak quicksort(*) ładnie w Javie wygląda funkcyjny. **List **jest z VAVRa.
import io.vavr.collection.List;
[...]
private List<Integer> qsort(List<Integer> input) {
if (!input.isEmpty()) {
final int middle = input.head();
final List<Integer> left = input.tail().filter( x -> x <= middle);
final List<Integer> right = input.tail().filter( x -> x > middle);
return qsort(left).appendAll(qsort(right).prepend(middle));
} else {
return input;
}
}
(* - to taki nie do końca quicksort, bo nie spełnia wymogu inplace - ale przymykamy na to oko, to ważne, żeby oczy miały czasem odpoczynek)