Koniec wakacyjnej przerwy! Ten artykuł miał zostać opublikowany ponad tydzień temu – ale wiecie jak to jest z wakacjami 😉 czasem po prostu trzeb a zluzować troszkę! Ale wracam z naładowanymi bateriami! Dziś zajmiemy się implementacją QuickSortu!

Pod poprzednim artykułem, czytelnik zadał pytanie czy istnieje już biblioteka która posiad implementację quicksortu? – jak się można spodziewać, odpowiedź na to pytanie brzmi – oczywiście 😊 żeby było lepiej, implementacja QuickSortu znajduje się w samej Javie! 😊 (od wersji 1.2)

import java.util.Arrays;
...
Arrays.sort(array);

I w zasadzie to wystarczy 😊

Nasza własna implementacja nie jest najbardziej optymalną wersją – jest wersją przedstawionej wcześniej teorii. Opisana implementacja pokrywa się w 100% z opisaną teorią z poprzedniego wpisu, dzięki czemu można porównać co się dokładnie dzieje.

Po pierwsze mamy jeden punkt wejściowy do którego przesyłamy naszą nieposortowaną tablicę:

public static void sort(int[] array) {
  quickSort(array, 0, array.length-1);
}

W ciele metody robimy odesłanie do naszej głównej metody quickSort:

private static void quickSort(int[] array, int firstIndex, int lastIndex) {
  if(firstIndex < lastIndex) {
    int partitionIndex = partition(array, firstIndex, lastIndex);
    quickSort(array, firstIndex, partitionIndex-1);
    quickSort(array, partitionIndex+1, lastIndex);
  }
}

Pierwszym krokiem jest sprawdzenie na jakich pozycjach są ustawione indexy, index początkowy musi być mniejszy od ostatniego indexu – w przeciwnym wypadku nie podejmujemy żadnych działań.

Główną metodą jest metoda partition która dokonuje sortowania przesłanej tablicy względem pivotu, oraz zwraca również index podziału – dzięki czemu mamy podział na lewą i prawą część tablicy.

Jak możesz zauważyć metoda quickSort, jest metodą rekurencyjną (wywołuje sama siebie), pokrywa się to z sortowaniem lewej oraz prawej części tablicy 😊

Metoda partition wygląda następująco:

private static int partition(int[] array, int firstIndex, int lastIndex) {
  int pivot = array[lastIndex];
  int pIndex = firstIndex;

  for (int i = firstIndex; i < lastIndex; i++) {
    if(array[i] <= pivot) {
      swap(array, i ,pIndex);
      pIndex++;
    }
  }
  swap(array, pIndex, lastIndex);
  return pIndex;
}

Jest to metoda która sortuje względem wybranego pivotu, oraz zwraca index podziału. Metoda swap jest metodą pomocniczą która zamienia dwa wskazane elementy:

private static void swap(int[] array, int index1, int index2) {
  int tmp = array[index1];
  array[index1] = array[index2];
  array[index2] = tmp;
}

Metody sortowania mogą być kłopotliwe do zrozumienia, pamiętaj że cały kod dostępny jest na GitHubie! Ściągnij kod – poeksperymentuj z nim, pomoże Ci to w zrozumieniu tego co się dzieje!

Kolejny wpis z cyklu JavaByExample. W poprzednim wpisie rozpisałem jak wygląda rekurencja – jeśli potrzebujesz to wróć do tego wpisu, dziś po raz kolejny użyjemy tej techniki!

Dzisiejsze zadanie jest kolejnym klasykiem – algorytmami sortującymi wykładowcy meczą studentów od zawsze, i pewnie już nigdy nie przestaną 😉

Zaimplementuj algorytm sortujący QuickSort

Okej, jak wygląda ten algorytm? Powiem szczerze – jest naprawdę wiele wersji tego algorytmu. Jest ich tak wiele ze względu na proces optymalizacji jaką przechodził ten algorytm. My zajmiemy się dziś jedną z podstawowych wersji algorytmu QuickSort 😊

Ogólna założenia algorytmu: Wybierany jest element  według którego sortujemy (pivot), wszystkie elementy mniejsze, umieszczamy po jego lewej stronie a elementy większe – po jego prawej stronie.
Następnie powtarzamy tą czynność dla lewej i prawej strony, do momentu aż wszystkie elementy będą posortowane.

Daną wejściową jest nieposortowana tablica np.:

Pierwszym krokiem jest wybór elementu według którego będziemy sortować, potocznie ten element jest nazywany pivotem – dla uproszczenie można wybrać ostatni index tablicy wejściowej.

Zaczynamy nasze sortowanie. Iterujemy w pętli po elementach na pozycjach mniejszych niż nasz pivot. Będziemy potrzebować dodatkowego wskaźnika który będzie nam wskazywać na element z którym będziemy przestawiać elementy, nazwijmy sobie go pIndex.

Mamy nasze początkowe ustawienie. Sprawdzamy czy element na który wskazuje index pętli jest mniejszy od naszego pivot’u (4), jeśli tak zamieniamy element na który wskazuje index pętli z elementem na który wskazuje pIndex. Po zamianie zwiększamy pIndex.

W naszym przypadku 7 jest większy od wybranego pivotu (4) – nie podejmujemy żadnej akcji, przechodzimy w pętli do kolejnego elementu:

Czy element na który wskazuje index pętli (2) jest mniejszy od naszego pivotu (4) jest mniejszy? Tak! Zamieniamy zatem elementy znajdujące się na miejscach na który wskazuje index pętli oraz wskaźnik pIndex

Po zamianie zwiększamy pIndex:

Przestawiliśmy jeden element. Jedziemy dalej według tego samego schematu 😉

Przestawiamy elementy -> zwiększamy pIndex -> przchodzimy do kolejnego elementu w pętli

Przedstawiamy elementy -> zwiększamy pIndex -> index pętli nie zostanie zwiększony, doszliśmy do ostatniego sprawdzanego elementu:

W momencie gdy doszliśmy do ostatniego sprawdzanego elementu, dokonujemy dodatkowej zamiany, pIndexu z naszym pivotem:

Ufffff! Właśnie ustawiliśmy pierwszy element! Wszystkie elementy mniejsze od naszego wybranego pivotu znajdują się po jego lewej stronie, a wszystkie większe elementy po jego prawej stronie! Teraz to samo robimy z lewą stroną oraz prawą stroną 🙂

Ze względu że artykuł wyszedł dość obszerny, został podzielony na dwie części – teoria, dostępna w tym wpisie, oraz implementację – która zostanie omówiona w kolejnym wpisie. Jeśli chcesz sprawdzić implementację już teraz, jest ona dostępna na GitHubie!

Dziś kolejne zadanie z cyklu JavaByExample. Dziś będziemy omawiać ciąg Fibonacciego. W poprzedniej lekcji z serii omawialiśmy przykład zliczania poszczególnych znaków z daniu. Dostałem na ten temat komentarz, iż zadania da się rozwiązać znacznie łatwiej niż zostało to przeze mnie przedstawione, używając Stremów. Bardzo dziękuję za ten komentarz! Poprzednie zadanie zostało zaktualizowane o rozwiązanie oparte na Streamach! Update znajdziecie we wpisie, jak i na GitHubie! 😊

Dzisiejsze zadanie jest naprawdę klasykiem! 😊 Mała ciekawostka, kiedyś dostałem zadanie związane z ciągiem Fibonacciego na rozmowie rekrutacyjnej, jako zadnie na rozgrzewkę 😊 Warto zapoznać się o co chodzi 😊

Napisz program który policzy podany przez użytkownika element ciągu Fibonacciego.

Jak wygląda ten cały ciąg? Pierwsze dwie liczby to 1,1 a kolejna to suma dwóch poprzednich, czyli kolejnym elementem jest liczba 2! Mamy zatem 1,1,2 – kolejnym elementem jest 1+2 = 3 mamy teraz 1,1,2,3 – kolejny element 2+3=5 itd. Tak przedstawiają się kolejne elementy tego ciągu:

1,1,2,3,5,8,13,21,34,55,89… i tak w nieskończoność 😉

Przykład 1:
Użytkownik podaje liczbę: 6
Odpowiedź programu: 8

Przykład 2:
Użytkownik podaje liczbę: 10
Odpowiedź programu: 55

Przede wszystkim – postaraj się rozwiązać to zadanie samodzielnie. Poniżej znajdziesz moje rozwiązanie, opis wraz z całym kodem źródłowym!

Przed rozpoczęciem mojego rozwiązania chciałbym przypomnieć o jednej bardzo ważnej sprawie. Pamiętaj o tym że nie ma jednego konkretnego sposobu na napisanie programu który rozwiązuje dany problem. Jak to powtarzał jeden z moich profesorów, konkretny program możemy napisać na milion sposobów i każdy z nich może być poprawny!

STOP -Poniżej znajdziesz moje rozwiązanie tego zadania – postaraj się rozwiązać najpierw samemu! W razie problemów możesz przeczytać moje rozwiązanie oraz zajrzeć na GitHuba!

Zadanie można rozwiązać na wiele sposobów 😊 Naprawdę! Zadanie jest naprawdę klasyczne 😊 Wykładowcy lubią męczyć nim adeptów programowania, dziś przedstawię wam 3 różne sposoby rozwiązania, klasyczny z użyciem pętli, z użyciem rekurencji oraz z użyciem Stremów.

public static long fibClassic(int n) {
  long x1 = 1;
  long x2 = 1;
  for (int i = 3; i <= n; i++) {
    long temp = x1 + x2;
    x1 = x2;
    x2 = temp;
  }
  return x2;
}

Opis: Tworzymy dwie zmienne którym nadajemy wartość 1, zgodnie z pierwszymi elementami ciągu. Zaczynamy pętle, początek pętli ustalamy na 3, pierwsze dwa elementy są znane, wiec sens wykonywania jakichkolwiek obliczeń mamy dopiero od trzeciego elementu. W pętli tworzymy tymczasową zmienną do której przypisujemy wynik sumy dwóch poprzednich elementów. Następnie dokonujemy „przesunięcia” nasze x1 dostaje wartość obecnego x2, natomiast x2 dostaje wyliczoną wartość. Użytkownikowi zwracamy x2 😊 będzie on miał przypisaną ostatnią wyliczoną wartość 😊

public static long fibRecursive(int n) {
  if(n <= 1) return n;
  return fibRecursive(n-2)+fibRecursive(n-1);
}

Yeah, piękno rozwiązań rekursywnych 😉 Całe ciało metody zamknięte dosłownie w dwóch linijkach! Jeśli nigdy wcześniej nie spotkałeś się z metodami rekursywnymi już tłumaczę o co chodzi. W prostych słowach polega to na tym że metoda wywołuje sama siebie 😊 Metody rekursywne mają wiele pułapek, i łatwo stworzyć nieskończoną pętlę, trzeba ich używać ze szczególną ostrożnością.

Opis: Jeśli metoda dostanie liczbę 1 lub mniejszą, zwróci tą liczbę, jeśli dostanie liczbę większą od jeden zwraca sumę z wykonania metody dla dwóch poprzednich elementów (n-2 oraz n-1). Dla osób początkujących może być to ciężko do wyobrażenia więc spieszę z pomocnym rysunkiem! 😊 Żeby aż tak wiele nie rysować, przyjmiemy że użytkownik poprosił o 6 element ciągu (wynik 8) :

Okej! Rozrysowałem tylko jedną stronę 😉 ale myślę że z tego rysunku możecie sobie wyobrazić jak wygląda pozostała część 😊 Po prostu nie zmieściło mi się na rysunku 😊

Użytkownik podaje jako parametr wejściowy 6, zatem w zaczynamy naszą rekursywę fib(6-2)+fib(6-1). Czyli tak naprawdę fib(4)+fib(5). Rysunek przedstawia pełne drzewo dla fib(6-2) czyli dla fib(4), liczmy ostatnie gałęzie:

fib(4)= 0+1+1+0+1 = 3

Druga gałąź wyglądała by bardzo podobnie: fib(5)= fib(3)+fib(4) zwróć uwagę że fib(3) mamy policzone na rysunku i wynosi fib(3)=2, fib(4) również mamy policzone i wynosi fib(4)= 3, podstawiając liczby fib(5) = 2+3 = 5

Podstawiamy wszystkie policzone liczby fib(6) = fib(4) + fib(5) = 3+5 = 8

Uwaga! Rozwiązanie rekursywne jest bardzo wolne! Jest to spowodowane że niektóre wartości liczone są wielokrotnie.

public static long fibStream(int n) {
  return Stream.iterate(new int[]{1,1}, x -> new int[]{x[1], x[0]+x[1]})
      .limit(n)
      .map(x->x[0])
      .collect(Collectors.toList())
      .get(n-1);
}

Taka trochę ciekawostka że się po prostu da 😊 Nie uważam żeby to rozwiązanie było specjalnie atrakcyjne taka ciekawostka!

Ok! 3 całkowicie różne podejścia do rozwiązania danego problemu 🙂 Pamiętajcie że jeśli wasze może się różnić od mojego i nie ma w tym nic złego! Bonus! Na GitHubie dodałem porównanie wydajności poszczególnych metod, oraz jak Java radzi sobie z optymalizacją podobnych zadań 😉 fajnie to widać na Streamach!

Dziś oficjalnie rozpoczynamy serię Java By Example. Jestem przekonany że najlepszą nauką programowania jest po prostu praktyka. W serii Java By Example postawimy sobie jakiś problem który będziemy rozwiązywać, kody źródłowe będą dostępne oczywiście na GitHubie. Seria JavaByExample jest częścią kursu programowania w Javie.

Dzisiejsze zadanie jest zadaniem które pamiętam z podstaw programowanie:

Napisz program który wypisze liczbę występowania poszczególnych znaków, występujących we wprowadzonym przez użytkownika zdaniu.

Przykład 1:
Użytkownik wprowadza zdanie: ala
Odpowiedź programu: a -2 , l – 1

Przykład 2:
Użytkownik wprowadza zdanie: Ala ma kota
Odpowiedź programu: A – 1, a – 3, t – 1, k – 1, l – 1, m – 1, o – 1

Uwaga: Zwróć uwagę że wielka litera A jest liczona osobno od małej literki a

Przede wszystkim – postaraj się rozwiązać to zadanie samodzielnie. Poniżej znajdziesz moje rozwiązanie, opis wraz z całym kodem źródłowym!

Przed rozpoczęciem mojego rozwiązania chciałbym przypomnieć o jednej bardzo ważnej sprawie. Pamiętaj o tym że nie ma jednego konkretnego sposobu na napisanie programu który rozwiązuje dany problem. Jak to powtarzał jeden z moich profesorów, konkretny program możemy napisać na milion sposobów i każdy z nich może być poprawny!

STOP -Poniżej znajdziesz moje rozwiązanie tego zadania – postaraj się rozwiązać najpierw samemu! W razie problemów możesz przeczytać moje rozwiązanie oraz zajrzeć na GitHuba!

Ok – Czas pomyśleć nad rozwiązaniem. Zadanie możemy podzielić na 3 oddzielne elementy:

1) Pobranie od użytkownika wartości
2) Policzenie ile razy w zdaniu występuje konkretny znak
3) Wypisanie wyniku na ekranie

Podzielenie programu na osobne odpowiedzialności jest bardzo dobrą praktyką – każda część programu jest odpowiedzialna za tylko jedną funkcjonalność  – „Single responsibility principle”.

Ok! Zabieramy się za kodowanie. Pierwsza część programu jest prosta:

System.out.println("Input sentence: ");
Scanner scanner = new Scanner(System.in);
String userInput = scanner.nextLine();

Pobranie zdania od użytkownika mamy za sobą 🙂

Kolejna część jest tak naprawdę sercem naszego programu, musimy policzyć występowania poszczególnych znaków. Pobrane przez nas zdanie użytkownika jest przypisane do zmiennej typu String, żaden nasza metoda przyjmie String jako parametr. Metoda zwróci nam ma Mapę – jako klucz będzie znakiem, wartość liczbę która będzie reprezentować ile razy dany znak występował we wprowadzonym zdaniu.

public static Map<Character, Integer> countCharacters(String userInput) {
}

Cała metoda wygląda następująco:

public static Map<Character, Integer> countCharacters(String userInput) {
    if(userInput == null || userInput.isEmpty()) return Collections.emptyMap();

    Map<Character, Integer> characterCounter = new HashMap<>();
    for (char c : userInput.toCharArray()) {
        Integer value = characterCounter.get(c);
        if (value != null) {
            value++;
        } else {
            value = 1;
        }
        characterCounter.put(c,value);
    }

    return characterCounter;
}

Opis:
W pierwszym kroku sprawdzam co przyszło do metody, jeśli dostaliśmy nulla, lub pustego Stringa, nie ma sensu nic robić. Po prostu zwracamy pustą mapę. Jeśli jednak coś dostaliśmy od użytkownika do przetworzenia, mamy trochę roboty 😊

Tworzymy pustą mapę, oraz pętlę po wszystkich znakach z wprowadzonego zdania. W pętli staramy się pobrać z mapy wartość dla konkretnego znaku.

Jeśli dostaniemy wartość różną od null -> zwiększamy ją – znak wystąpił w zdani kolejny raz,  jeśli dostaniemy null, znaczy to że konkretnego znaku nie ma jeszcze w mapie – wartość ustawiamy na 1. W obu przypadkach dodajemy parę znak – ilość do mapy, w przypadku nowej wartości będziemy mieć kolejny element w mapie, w przypadku istniejącego już takiego klucza, zastąpimy go z nowa wartością.

Powyższa metoda w oparciu o pętlę, choć poprawna, to można ją zdecydowanie uprościć używając Streamów (Bardzo dziękuję czytelnikowi za zwrócenie uwagi!), streamy na blogu nie były jeszcze poruszane, ale warto zapoznać się również z tym rozwiązaniem:

public static Map<Character, Long> countCharactersStream(String userInput) {
  return userInput.chars().mapToObj(c -> (char) c)
      .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

Metoda jest teraz niezwykle prosta! Cały wprowone zdanie zamieniamy w Stream, oraz zbieramy wszystkie unikalne elementy, oraz zliczamy ich występowanie używając

Collectors.groupingBy(Function.identity(), Collectors.counting())

Pozostaje nam jeszcze ostatnia część zadania – Wypisanie wyniku:

public static void printCountedInput(Map<Character, ? extends Number> characterCounter) {
   for (Map.Entry<Character, ? extends Number> entry : characterCounter.entrySet()) {
      System.out.println("Sign: "+entry.getKey().toString()+" Count: "+entry.getValue());
   }
}

Cały kod:

System.out.println("Input sentence: ");
Scanner scanner = new Scanner(System.in);
String userInput = scanner.nextLine();
printCountedInput(countCharacters(userInput));

Pamiętaj o punkcie drugim w którym wspominałem że nie ma jednego dobrego rozwiązania 😊 to jest tylko moja propozycja! Cały kod do zadania jest dostępny na Githubie! Możesz ściągnąć cały kod i uruchomić go u siebie 😊