Java

Sortowanie przez wybieranie – to jeden z podstawowych kroków w podróży każdego Junior Developera.
Zrozumienie i praktyczne zastosowanie podstawowych algorytmów sortowania (w tym również – sortowania przez wybieranie!) stanowi kluczowy element w rozwoju umiejętności każdego junior developera.
Chociaż w codziennej pracy profesjonalnych programistów rzadko zdarza się, aby implementowali oni algorytmy sortowania od podstaw, to zrozumienie ich działania i konstrukcji jest niezbędne.

W tym wpisie skupimy się na metodzie sortowania przez wybieranie (selection sort), pokazując krok po kroku, jak można ją zaimplementować i dlaczego jest to cenne ćwiczenie dla początkujących programistów.

Sortowanie przez wybieranie – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest sortowanie przez wybieranie?
• Jak zaimplementować algorytm sortowania przez wybieranie?
• Dlaczego warto zainteresować się Selection Sort?

Sortowanie przez wybieranie (ang. Selection Sort)

Sortowanie przez wybieranie (ang. Selection Sort) – jest jednym z najprostszych algorytmów sortowania. Pomimo swojej prostoty, jest on skuteczny i znajduje zastosowanie, zwłaszcza w przypadku niewielkich list elementów.

Działa on w następujący sposób:

1. Przechodzi przez całą listę elementów.
2. Znajduje element o najmniejszej wartości.
3. Zamienia ten element z pierwszym elementem na liście.
4. Powtarza ten proces, wybierając teraz element o najmniejszej wartości spośród pozostałych elementów.
5. Kontynuuje takie zamiany aż do momentu, gdy cała lista jest posortowana.

 

Algorytm sortowania przez wybieranie

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Sortowanie przez wybieranie – kluczowe aspekty

Jednym z popularniejszych algorytmów sortowania jest sortowanie przez wybieranie.

Dlaczego warto się nim zainteresować?

• Prostota – Sortowanie przez wybieranie jest jednym z najprostszych algorytmów sortowania i łatwo go zrozumieć oraz zaimplementować.
• Brak dodatkowej pamięci – Jest to algorytm in-place, co oznacza, że nie wymaga dodatkowej pamięci do przechowywania sortowanych elementów.
• Skuteczność dla małych zbiorów – W przypadku niewielkich list elementów, sortowanie przez wybieranie jest bardzo skuteczne i działa wydajnie.

Istnieją jednak pewne czynniki, które warto wziąć pod uwagę:

• Złożoność czasowa – Ma złożoność czasową O(n^2), co sprawia, że jest niewydajny dla dużych list elementów.
• Niestabilność – Algorytm nie jest stabilny, co oznacza, że nie gwarantuje utrzymania pierwotnej kolejności elementów o tej samej wartości.

➡ ZOBACZ 👉: Java | Sortowanie szybkie – Quick Sort

Java – Sortowanie przez wybieranie – podsumowanie

Sortowanie przez wybieranie to prosty i skuteczny algorytm sortowania, który może być przydatny w wielu sytuacjach. Choć ma swoje ograniczenia, zwłaszcza dla dużych list, warto zrozumieć jego działanie i zaimplementować go w swoim kodzie.

Najdłuższy wspólny prefiks i najdłuższy wspólny podciąg to dwa istotne pojęcia w dziedzinie algorytmów i przetwarzania ciągów znaków.

Najdłuższy wspólny prefiks i najdłuższy wspólny podciąg – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest najdłuższy wspólny prefix?
• Co to jest drzewo typu Trie?
• Jak zaimplementować algorytm znajdujący najdłuższy wspólny prefix?
• Czym jest najdłuższy wspólny podciąg?

Najdłuższy wspólny prefiks

Najdłuższy wspólny prefiks to najdłuższy początkowy fragment dwóch lub więcej ciągów znaków.
Na przykład, dla ciągów „program” i „projekt”, najdłuższy wspólny prefiks to „pro”.

Najdłuższy wspólny prefiks jest używany np. aby zidentyfikować wspólną część początkową w ciągach, co jest przydatne w zadaniach, takich jak porównywanie ciągów znaków, analiza słów kluczowych itp.

Podczas wyliczania najdłuższego wspólnego prefiksu możemy wykorzystać drzewo Trie (nie mylić z tree!).

Drzewo Trie

Drzewo Trie (zwane również drzewem prefixowym lub cyfrowym) jest strukturą danych specjalnie zaprojektowaną do przechowywania i przeszukiwania zestawów ciągów znaków.

Zaletą drzewa Trie jest to, że pozwala na wydajne znajdowanie wspólnego prefiksu ciągów znaków, ponieważ przechowuje je w formie drzewa, gdzie wspólny prefiks dla wielu ciągów jest wspólną ścieżką w drzewie.

Algorytmy oparte na drzewach Trie często mają lepszą wydajność niż podejścia oparte na porównywaniu znak po znaku.

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord = false;
}

class TrieNodeMain {
    public static String findLongestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        TrieNode root = new TrieNode();

        for (String str : strs) {
            TrieNode node = root;
            for (char c : str.toCharArray()) {
                node.children.putIfAbsent(c, new TrieNode());
                node = node.children.get(c);
            }
            node.isEndOfWord = true;
        }

        StringBuilder prefix = new StringBuilder();
        TrieNode node = root;

        while (node.children.size() == 1 && !node.isEndOfWord) {
            Map.Entry<Character, TrieNode> entry = node.children.entrySet().iterator().next();
            prefix.append(entry.getKey());
            node = entry.getValue();
        }

        return prefix.toString();
    }
}

Powyższa metoda przyjmuje jako argument tablicę String. Po sprawdzeniu, czy tablica jest pusta inicjuje węzeł drzewa Trie. W kolejnym etapie iteruje po dostarczonych ciągach znaków, a następnie po znakach w bieżącym ciągu. Dalej w pętli dodawany jest nowy węzeł dla każdego znaku jeśli taki jeszcze nie istnieje. Tworzy obiekt StringBuilder do przechowywania wynikowego prefiksu. Na koniec w pętli while szuka najdłuższego prefixu.

➡ ZOBACZ 👉: StringBuilder: czy zawsze taki szybki? | String vs StringBuilder vs StringBuffer

Algorytm znajdujący najdłuższy wspólny prefix

Do znalezienia najdłuższego wspólnego prefixu możemy wykorzystać alternatywne rozwiązania. O to jedno z nich.

    public static String findLongestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }

Tutaj podobnie jak w poprzedniej implementacji na start dostarczamy tablicę z ciągami znaków.
Rozpoczynamy od pierwszego ciągu, a następnie stopniowo skracamy go, porównując z pozostałymi ciągami, aż znajdziemy wspólny początek.
Ewentualnie zwrócimy pusty ciąg, jeśli nie ma wspólnego fragmentu.

➡ ZOBACZ 👉: String – najważniejszy typ danych

Najdłuższy wspólny podciąg

Najdłuższy wspólny podciąg (ang. Longest Common Subsequence, LCS) to najdłuższy ciąg znaków, który występuje w tej samej kolejności w obu łańcuchach. Znaki te mogą być rozdzielone w każdym z łańcuchów innymi znakami.

[LCS] to nie tylko teoretyczny problem algorytmiczny. Rozumienie tego zagadnienia ma praktyczne zastosowania.
Pozwala między innymi na porównywanie tekstów, znajdowanie wspólnych sekwencji w danych genetycznych czy śledzenie zmian w dokumentach.

    public static String lcs(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                } else if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        int lcsLength = dp[m][n];
        char[] lcs = new char[lcsLength];
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                lcs[lcsLength - 1] = s1.charAt(i - 1);
                lcsLength--;
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        return new String(lcs);
    }

Powyższy fragment kodu źródłowego oblicza najdłuższy wspólny podciąg między dwoma ciągami znaków text1 i text2 przy użyciu programowania dynamicznego. Algorytm przechodzi przez oba ciągi znaków, tworząc tablicę dp do przechowywania wyników pośrednich. Następnie odtwarza najdłuższy wspólny podciąg, korzystając z tablicy dp.

➡ ZOBACZ 👉: String – konwertowanie i zamiana typów: Array, ArrayList, Char, Int, Integer

Najdłuższy wspólny prefiks | Najdłuższy wspólny podciąg – podsumowanie

Powyższe algorytmy mogą być użyteczne w rozwiązywaniu problemów, takich jak porównywanie dokumentów tekstowych, analiza sekwencji DNA, zarządzanie wersjami oprogramowania i wiele innych. Dodatkowo [LCS] może być stosowany w różnych dziedzinach, w których istnieje potrzeba znajdowania wspólnych sekwencji między dwoma ciągami znaków. Algorytm ten jest efektywny i ma wiele praktycznych zastosowań.

Sortowanie przez Scalanie (ang. Merge Sort) – Jednym z podstawowych zagadnień w programowaniu jest sortowanie danych. Bez względu na to, czy jesteś początkującym programistą, czy po prostu chcesz dowiedzieć się więcej o algorytmach sortowania, w tym artykule zgłębimy temat Merge Sort, czyli Sortowania przez Scalanie.

Merge sort – wprowadzenie

Z tego materiału dowiesz się:

• Co to jest oraz jak działa Merge Sort?
• Na czym polega koncepcja dziel i zwyciężaj?
• Jak zaimplementować sortowanie Merge Sort?

Merge Sort – Sortowanie przez Scalanie

Merge Sort – to jeden z efektywnych algorytmów sortowania, który bazuje na koncepcji „Dziel i Zwyciężaj”.
Algorytm ten jest powszechnie stosowany w praktyce, ze względu na swoją wydajność i stabilność.

Dziel i zwyciężaj

Koncepcja „dziel i zwyciężaj” (ang. „divide and conquer”) to algorytmiczna strategia, która polega na podziale złożonego problemu na mniejsze, dające się lepiej zarządzać części. Podproblemy rozwiązywane są niezależnie, a następnie łączymy wyniki, aby uzyskać rozwiązanie problemu macierzystego.

Merge Sort – mechanizm działania

1. Dzielenie (ang. Divide) – W pierwszym kroku tablicę dzieli się na dwie równe części, tj. lewą i prawą część. Środkowy indeks tablicy jest obliczany jako (lewy + prawy) / 2, gdzie „lewy” to indeks początku, a „prawy” to indeks końca tablicy.
2. Sortowanie (ang. Conquer) – Następnie rekurencyjnie sortuje się obie części tablicy, tj. lewą i prawą, aż do momentu, gdy pozostają pojedyncze elementy. Sortowanie to jest wykonywane w sposób rekurencyjny.
3. Scalanie (ang. Merge): Po uzyskaniu pojedynczych elementów w wyniku sortowania, scalane są one w jedną posortowaną tablicę. W tym kroku porównuje się elementy z lewej i prawej strony i umieszcza się je w odpowiedniej kolejności w wynikowej tablicy.

Algorytm Merge Sort jest stabilny, co oznacza, że nie zmienia kolejności równych elementów w wyniku sortowania. Jest to również algorytm „out-of-place”, co oznacza, że tworzy nową tablicę na posortowane dane, nie nadpisując oryginalnej tablicy.

➡ ZOBACZ 👉: Java | Biblioteka Arrays
➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Merge Sort – Algorytm

    public static void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }

        int middle = array.length / 2;
        int[] left = new int[middle];
        int[] right = new int[array.length - middle];

        for (int i = 0; i < middle; i++) {
            left[i] = array[i];
        }
        for (int i = middle; i < array.length; i++) {
            right[i - middle] = array[i];
        }

        mergeSort(left);
        mergeSort(right);

        merge(array, left, right);
    }

Metoda przyjmuje jako argument tablicę liczb całkowitych. Obliczamy środek tablicy. Tworzymy dwie tablice, lewą, do której kopiujemy elementy od początku tablicy do środka i prawą, od środka do końca. Następnie wywołujemy rekurencyjnie mergeSort() dla lewej i prawej podtablicy.

➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie

Na koniec wywołujemy metodę merge() która sortuje elementy i scala je do nowej tablicy.

    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        while (i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }

        while (i < left.length) {
            array[k++] = left[i++];
        }

        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

Java – Merge Sort – podsumowanie

Merge Sort jest algorytmem sortowania, który ma szerokie zastosowanie w różnych dziedzinach programowania i informatyki. Jego efektywność i stabilność czynią go atrakcyjnym wyborem w przypadku sortowania danych. W praktyce jest wykorzystywany w sortowaniu list obiektów, operacjach na grafach, systemach baz danych oraz we wbudowanych funkcjach sortujących wielu języków programowania i frameworków. Dzięki temu zrozumienie Merge Sort jest wartościowym aktywem dla każdego programisty.

➡ ZOBACZ  👉: Java | Sortowanie przez wybieranie

➡ ZOBACZ 👉: Java | Sortowanie szybkie – Quick Sort

➡ ZOBACZ 👉: Java | Sortowanie bąbelkowe – Bubble Sort

Klasa Arrays, to jeden z tych „kombajnów”, po który sięgamy gdy chcemy zrobić „coś” z naszą tablicą.
Przykładowo – chcesz zrobić „coś” z tablicą, ale nie wiesz nawet jak to nazwać 🙃, a tym bardziej, jak to znaleźć? To zacznij poszukiwania właśnie od tej klasy pomocniczej – jest duża szansa, że znajdziesz to czego akurat teraz potrzebujesz! 🚀

Java – Arrays – wprowadzenie

Z tego materiału dowiesz się:

• Jakie są podstawowe funkcjonalności klasy pomocniczej Arrays?
• Jak wykorzystać klasę Arrays w codziennej pracy?
• Jakie algorytmy sortowania kryją się pod Arrays.sort()?

Java – Arrays – podstawowe funkcjonalności

Skupimy się na podstawowych funkcjonalnościach klasy Arrays.

Za przykład posłuży nam prosta tablica liczb całkowitych.

int[] numbers = {4, 8, 5, 99, 34};

➡ ZOBACZ 👉: Typy proste | Kurs Java

Przyda nam się również dwuwymiarowa tablica Stringów.

➡ ZOBACZ 👉: String – najważniejszy typ danych

String[][] cities = {{"Warszawa", "Gdansk"}, {"Poznan", "Lodz", "Krakow"}};

➡ ZOBACZ 👉: Java tablice | Kurs Java

Wyświetlanie Tablicy

Żeby wyświetlić tablicę, możemy przeiterować się po tablicy za pomocą pętli for.

➡ ZOBACZ 👉: Iteracja, iteracje – powtarzanie w programowaniu vs Rekurencja ➿, Iteracja, iteracje

Jednak nie musimy robić tego ręcznie!
Alternatywnie możemy skorzystać z gotowych już metod toString() oraz deepToString().

System.out.println(Arrays.toString(numbers));

System.out.println("cities = " + Arrays.deepToString(cities));

➡ ZOBACZ 👉: Pętla (for, while, do while, foreach) pętle | Kurs Java
➡ ZOBACZ 👉: Java tablice | Kurs Java

Kopiowanie Tablicy

Jeżeli potrzebujesz stworzyć kopię tablicy, biblioteka Arrays również Ci w tym pomoże.

int[] copyNumbers = Arrays.copyOf(numbers, numbers.length);

Porównywanie Tablic

Czasem konieczne jest porównanie dwóch tablic.

boolean isEqual = Arrays.equals(numbers, copyNumbers);

Zwróć uwagę, że w tym wypadku porównujemy poszczególne elementy tablicy, nie sam obiekt tablicy (jak robi to operator ==).
➡ ZOBACZ 👉: Operatory relacyjne | Kurs Java
➡ ZOBACZ 👉: hashCode i equals – co grozi Ci za złamanie kontraktu między metodami equals i hashCode?

Wyszukiwanie Elementu

Potrzebujesz sprawdzić, czy dany element znajduje się w tablicy?

Musimy jednak pamiętać, że metoda binarySearch() oczekuje posortowanej tablicy.
Jeżeli jej wcześniej nie posortujesz, możesz spodziewać się błędnych wyników. 🙃

Arrays.sort(numbers);

int index = Arrays.binarySearch(numbers, 8);

Wypełnianie Tablicy

Metoda fill() umożliwia jednoczesne wypełnienie wszystkich elementów tablicy określoną wartością.
To przydatne narzędzie, gdy chcemy zainicjować naszą tablicę.

        int[] array = new int[5];
        Arrays.fill(array, 33);

Arrays strumienie

Dzięki klasie Arrays możemy wywołać strumień (ang. stream) na tablicy.

Umożliwia nam to eleganckie przetwarzanie danych. Jest to szczególnie przydatne, gdy chcemy wykonywać bardziej złożone operacje na elementach tablicy.

Dla przykładu zsumujemy wszystkie elementy tablicy mniejsze od 10.

int sum = Arrays.stream(numbers).filter(value -> value < 10).sum();

Algorytmy Sortowania

Metoda Arrays.sort() w Javie używa różnych algorytmów sortowania w zależności od sytuacji.

Implementacja algorytmu sortowania zależy od typu danych i rozmiaru tablicy. Oto kilka informacji na ten temat:

1. Dla typów prostych: Dla tablic zawierających typy proste, takie jak int, long, char, float, itp., Arrays.sort() używa modyfikacji algorytmu Dual-Pivot Quicksort. Jest to ulepszona wersja tradycyjnego algorytmu Quicksort.
   

   ---

   ➡ ZOBACZ 👉: Sortowanie szybkie – Quick Sort

2. Dla obiektów: Dla tablic obiektów, Arrays.sort() używa algorytmu TimSort. TimSort jest hybrydowym algorytmem sortowania, który łączy elementy MergeSort i InsertionSort. Jest efektywny w przypadku danych częściowo posortowanych lub małych danych.
   

   ---

   ➡ ZOBACZ 👉: Sortowanie przez Scalanie – Merge Sort
   ➡ ZOBACZ 👉: Sortowanie przez wstawianie, Insertion Sort

3. Dla dużych tablic obiektów: W przypadku dużych tablic obiektów, TimSort wykorzystuje metodę Comparable lub Comparator do porównywania elementów i ustalania ich kolejności.

Warto zauważyć, że implementacje mogą się różnić w zależności od wersji Javy i konkretnego dostawcy JVM.
Jednak w przypadku standardowej Javy (Oracle/OpenJDK), powyższe informacje są odpowiednie dla wersji Java 7 i nowszych do 21.

Generalnie rzecz biorąc, implementacja Arrays.sort() jest zoptymalizowana pod kątem różnych przypadków użycia, co sprawia, że jest elastyczna i wydajna.

Java – Arrays – podsumowanie

Klasa Arrays w Javie to doskonałe narzędzie do efektywnego zarządzania danymi w tablicach. Dzięki niej sortowanie, kopiowanie czy przeszukiwanie elementów staje się prostsze i bardziej wydajne, co pozwala programiście zoptymalizować operacje na danych. Nie zapomnij, że prawidłowe sortowanie danych jest kluczowe dla poprawnego działania funkcji wyszukiwania, a znajomość różnych algorytmów sortowania daje możliwość wyboru optymalnego rozwiązania dla konkretnej sytuacji. Warto także eksplorować funkcje strumieniowania (Arrays.stream()), aby elegancko manipulować danymi w tablicach, tworząc bardziej czytelny i wydajny kod.

➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie

Sortowanie szybkie (ang. Quick Sort) – jest jednym z najpopularniejszych i najbardziej efektywnych algorytmów sortowania. Dowiesz się, dlaczego Quick Sort jest tak ważny, jak działa oraz kiedy warto go stosować.

Java – Quick Sort – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Quick Sort?
• Jak działa Quick Sort?
• Jak zaimplementować algorytm Quick Sort?
• Jakie są zalety i wady Quick Sort?
• Jak Java korzysta z algorytmu Quick Sort?

Quick Sort – Sortowanie szybkie

Quick Sort wykorzystuje prostą, ale potężną koncepcję. Algorytm dzieli zestaw danych na mniejsze podzbiory, sortuje każdy z nich i łączy wyniki w jedną uporządkowaną całość. Należy jednak pamiętać, że Quick Sort nie jest stabilnym algorytmem sortowania. Oznacza to, że elementy o tych samych wartościach mogą zmienić swoją względną kolejność w wynikowym zbiorze (wrócimy do tego tematu jeszcze za chwilę).

Quick Sort – Zasada działania

Idea „dziel i zwyciężaj” polega na podziale problemu na mniejsze podproblemy, rozwiązaniu ich i połączeniu wyników w rozwiązanie ogólnego problemu. W przypadku Quick Sort oznacza to wybór elementu jako „pivot” (punkt odniesienia), podział zbioru danych na dwie grupy (mniejsze i większe od „pivota”), sortowanie tych dwóch grup i łączenie ich w jedną, uporządkowaną listę.

Algorytm Quick Sort

Przedstawiony poniżej algorytm sortuje liczby całkowite dostarczone w tablicy.

static void quickSort(int[] arr) {
	if (arr == null || arr.length == 0) {
		return;
	}

	int high = arr.length - 1;
	quickSort(arr, 0, high);
}

static void quickSort(int[] arr, int begin, int end) {
	if (begin < end) {
		int pivotIndex = partition(arr, begin, end);

		quickSort(arr, begin, pivotIndex - 1);
		quickSort(arr, pivotIndex + 1, end);
	}
}

static int partition(int[] arr, int begin, int end) {
	int pivot = arr[end];
	int i = (begin - 1);

	for (int j = begin; j < end; j++) {
		if (arr[j] <= pivot) {
			i++;

			int swapTemp = arr[i];
			arr[i] = arr[j];
			arr[j] = swapTemp;
		}
	}

	int swapTemp = arr[i + 1];
	arr[i + 1] = arr[end];
	arr[end] = swapTemp;

	return i + 1;
}

1. Metoda quickSort() jest punktem wejściowym dla użytkownika. Sprawdza, czy przekazana tablica nie jest pusta ani nie ma zerowej długości, a następnie wywołuje wersję tej samej metody z dodatkowymi parametrami.
2. Metoda ta implementuje rekurencyjny algorytm Quick Sort.
3. Warunek begin < end oznacza, że podtablica, którą sortujemy, zawiera więcej niż jeden element.
4. Wywołujemy metodę partition(), aby uzyskać indeks osi (pivotIndex), a następnie rekurencyjnie sortujemy dwie podtablice: od begin do pivotIndex -1 i od pivotIndex + 1 do end.
5. Metoda partition() wyznacza indeks osi (pivotIndex) dla danej podtablicy.
6. Używa dwóch wskaźników (i oraz  j), które przemieszczają się w stronę siebie, zamieniając elementy, jeśli są na niewłaściwych miejscach względem osi.
7. Po zakończeniu pętli zwraca indeks, który jest teraz pozycją osi w posortowanej tablicy.

W wyniku tego algorytmu, rekurencyjnie dzieląc i sortując tablicę, wszystkie elementy na lewo od osi będą mniejsze, a te po prawej stronie będą większe. Algorytm kończy działanie, gdy każda podtablica zawiera jeden element lub jest pusta.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Zalety i wady Quick Sort

Zalety:

• Optymalna średnia złożoność czasowa: QuickSort ma średnią złożoność czasową O(n log n), co czyni go jednym z najszybszych algorytmów sortowania dla ogólnej klasy problemów. To oznacza, że w większości przypadków, nawet dla dużych zbiorów danych, QuickSort działa wyjątkowo szybko.
• Dobre wykorzystanie pamięci podręcznej: QuickSort wykazuje lepsze wykorzystanie pamięci podręcznej procesora w porównaniu z innymi algorytmami sortowania, takimi jak Merge Sort czy Heap Sort. Dzieje się tak ze względu na lokalność odwołań, która jest wynikiem dzielenia danych na mniejsze podzbiory.
• Skalowalność: QuickSort jest bardzo skalowalny i efektywny dla dużych zbiorów danych. Jego zdolność do szybkiego sortowania dużych ilości danych czyni go użytecznym w zastosowaniach przemysłowych, takich jak bazy danych i systemy przetwarzania transakcji.
• Elastyczność w wyborze pivota: Możliwość wyboru różnych strategii dla wyboru pivota (np. pierwszy element, ostatni element, mediana, losowy element) pozwala na dostosowanie algorytmu do specyficznych wymagań danych wejściowych, co może zwiększać jego wydajność w różnych scenariuszach.
• Dobry do danych rozproszonych: QuickSort jest szczególnie efektywny w przypadku danych, które są rozproszone (nieuporządkowane) lub mają losowy rozkład, ponieważ takie warunki minimalizują ryzyko najgorszego przypadku działania algorytmu (O(n^2)).

Wady:

Pomimo licznych zalet algorytmu QuickSort, ważne jest również zwrócenie uwagi na potencjalne wady, takie jak:

• Problem uporządkowanych danych, czyli najgorszy przypadek złożoności czasowej O(n^2):
  W najgorszym scenariuszu, gdy dane wejściowe są już posortowane lub prawie posortowane (lub w każdym innym przypadku, gdy pivot jest wybierany niefortunnie), złożoność czasowa QuickSorta degraduje do O(n^2). Jest to znacznie mniej wydajne w porównaniu ze średnią złożonością O(n log n). Optymalna sytuacja dla QuickSort występuje, gdy pivot dzieli dane na dwie mniej więcej równe części, co zapewnia efektywność późniejszego sortowania. Jednak w przypadku danych, które są już częściowo lub całkowicie posortowane, wybór pivota może prowadzić do tworzenia bardzo nierównych podziałów. Na przykład, jeśli pivotem zostanie wybrany element z jednego z końców już posortowanego zbioru, jedna z części po podziale może zawierać większość elementów, a druga bardzo niewiele lub żadnych. Taka sytuacja prowadzi do niewydajności, ponieważ algorytm musi wykonać więcej rekurencyjnych wywołań dla większej części, co nie jest optymalne.
• Niestabilność algorytmu sortowania 
  Algorytm sortowania jest określany jako „niestabilny”, gdy kolejność równych elementów wejściowych może ulec zmianie po zastosowaniu algorytmu.
  Innymi słowy, jeśli mamy dwa elementy A i B o tej samej wartości klucza w oryginalnym zestawie danych, a algorytm sortowania zmienia ich wzajemne położenie, mówimy, że jest to algorytm niestabilny.
  W przypadku sortowania liczb całkowitych nie ma to większego znaczenia – liczba 1 jest zawsze liczbą 1 i nie ma znaczenia, czy zapiszemy to jako 11, czy jako 11 😉
  Może to mieć jednak znaczenie, gdy np. sortujemy naszych klientów po nazwisku i np. raz jako pierwszy na liście będzie Jan Kowalski z Gdańska, a innym razem Jan Kowalski z Warszawy.
• Brak gwarancji stałej wydajności: Ponieważ wydajność QuickSorta zależy od danych wejściowych i wyboru pivota, trudno jest zagwarantować stałą wydajność w różnych zastosowaniach. W niektórych przypadkach inne algorytmy sortowania mogą być bardziej przewidywalne i niezawodne.

Quick Sort – Java – Arrays.sort()

Na szczęście w świecie Javy zazwyczaj nie musisz samodzielnie implementować algorytmów sortowania, między innymi dzięki wbudowanej funkcji Array.sort().
Korzysta ona automatycznie z algorytmu Quick Sort, eliminując potrzebę ręcznej implementacji.

➡ ZOBACZ 👉: Arrays – Twój prywatny kombajn do zarządzania tablicami! 🚜👨‍🌾

Java – Quick Sort – Podsumowanie

Sortowanie szybkie, znane jako Quick Sort, to zaawansowany algorytm sortowania, który jest efektywny i przydatny w wielu sytuacjach. Niezależnie od poziomu  Twojego zaawansowania, warto poznać i zrozumieć ten algorytm, aby poszerzyć swoją wiedzę w zakresie algorytmów i sortowania danych.

Największy wspólny dzielnik (NWD) – to największa liczba, która dzieli dwie lub więcej innych liczb bez reszty. NWD jest używany w matematyce do upraszczania ułamków i rozwiązywania problemów związanych z podzielnością liczb.

Jednym z popularnych algorytmów obliczania NWD dwóch liczb jest algorytm Euklidesa.

Java – NWD – wprowadzenie

W tym materiale dowiesz się:

• Jak obliczyć NWD?
• Co to jest algorytm Euklidesa?
• Jak wygląda algorytm znajdujący NWD za pomocą odejmowania?
• Co to jest kalkulator NWD?

NWD – Największy wspólny dzielnik

NWD można obliczyć rozkładając liczby na czynniki pierwsze.

Rozkład liczby na czynniki pierwsze

1. Ustalamy czy liczba jest podzielna przez 2, jeśli tak obliczamy iloraz
2. Sprawdzamy, czy iloraz jest podzielny przez 2 i wykonujemy dzielenie powtarzając procedurę do chwili aż iloraz nie będzie podzielny przez 2
3. Jeśli liczba wyjściowa lub iloraz nie jest podzielny przez 2, kontynuujemy procedurę z liczbą 3 lub kolejnymi liczbami do momentu uzyskania ilorazu będącego liczbą pierwszą

➡ ZOBACZ 👉: Liczby pierwsze – Magia i Programowanie

Algorytm Euklidesa

Algorytm Euklidesa to jedna z najstarszych i najbardziej znanych metod obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych. Ten algorytm został nazwany na cześć starożytnego greckiego matematyka Euklidesa, choć sam algorytm był znany wcześniej.

Polega on na powtarzającym się dzieleniu większej liczby przez mniejszą liczbę i zastępowaniu większej liczby resztą z tego dzielenia, aż do momentu, gdy reszta stanie się równa zero. Wówczas ostatnia niezerowa reszta jest największym wspólnym dzielnikiem dwóch liczb.

Jak obliczyć NWD?

public int findNWD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

W powyższym rozwiązaniu mamy metodę, która przyjmuje dwie liczby całkowite a i b. Algorytm Euklidesa jest implementowany w pętli while dopóki b nie osiągnie zera. W każdej iteracji obliczamy resztę z dzielenia a przez b, a następnie zamieniamy a na b, a b na obliczoną resztę.

➡ ZOBACZ 👉: Iteracja, iteracje – powtarzanie w programowaniu vs Rekurencja ➿, Iteracja, iteracje
➡ ZOBACZ 👉: Pętla (for, while, do while, foreach) pętle

NWD za pomocą odejmowania

Algorytm znajdujący Największy Wspólny Dzielnik można dostarczyć na różne sposoby. Jeden z nich to implementacja za pomocą odejmowania. Algorytm polega na wielokrotnym odejmowaniu mniejszej z dwóch liczb od większej, aż obie liczby staną się równe.

public static int findNWD(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

NWD Kalkulator

Kalkulator największego wspólnego dzielnika to narzędzie, które pomaga obliczyć NWD dwóch lub więcej liczb całkowitych. Kalkulator NWD jest szczególnie przydatny w matematyce, algorytmach i rozwiązywaniu problemów związanych z liczbami całkowitymi.

W Javie taki kalkulator można stworzyć za pomocą poznanych wyżej metod.

Java – NWD – Podsumowanie

W tym materiale dowiedzieliśmy się czym jest największy wspólny dzielnik i jak go zaimplementować w Javie.
Jako kolejny krok warto zainteresować się algorytmem liczącym [NWW] Najmniejsza wspólna wielokrotność.

Najmniejsza Wspólna Wielokrotność (NWW) – to temat, który jest nie tylko ważny w matematyce i chociażby w naukach przyrodniczych, ale także odgrywa kluczową rolę w programowaniu.

Java – NWW – Wprowadzenie

Z tego materiału dowiesz się:

• Co to jest najmniejsza wspólna wielokrotność?
• Jakie jest zastosowanie NWW?
• Jak obliczyć NWW?
• Jak zaimplementować algorytm znajdujący NWW?

NWW – Najmniejsza wspólna wielokrotność – ciekawostka

Czy wiesz, że NWW jest często używana w problemach związanych z harmonią muzyczną? 🙂

W muzyce, gdy mamy dwie nuty o różnych częstotliwościach, ich wspólna wielokrotność czasu trwania może wpływać na sposób, w jaki odbieramy dźwięki. Jeśli długości nut są powiązane przez NWW, to dźwięki obu nut zbiegają się i tworzą harmonię. Zastosowanie NWW w muzyce jest jednym z przykładów, jak matematyka przenika różne dziedziny naszego życia.

NWW – Najmniejsza wspólna wielokrotność

Najmniejsza wspólna wielokrotność (NWW) –  jest to liczba całkowita, która jest najmniejszą wspólną wielokrotnością dwóch lub więcej innych liczb całkowitych. Oznacza to, że jest to najmniejsza liczba, którą można podzielić przez dane liczby.

Rozkład liczby na czynniki pierwsze

Kroki do obliczenia NWW liczb 12 i 18 za pomocą rozkładu na czynniki pierwsze:

• Rozłóż na czynniki pierwsze.

12 = 2² · 3¹

18 = 2¹ · 3²

• Najwyższe potęgi czynników pierwszych.

12 -> 2²

18 -> 3²

• Wyznacz NWW podanych liczb.

NWW(12, 18) = 2^{2 ·} 3² = 4 · 9 = 36

NWW – Algorytm znajdujący najmniejszą wspólną wielokrotność

Do obliczenia NWW najskuteczniejszą i zazwyczaj najlepszą metodą jest wykorzystanie w algorytmie największego wspólnego dzielnika (NWD).

NWW i NWD

➡ ZOBACZ 👉: Największy wspólny dzielnik, Algorytm znajdujący NWD

public int findNWW(int a, int b) {
    return a * (b / findNWD(a, b));
}

definiujemy funkcję findNWW(), która oblicza NWW dwóch liczb przy użyciu wzoru

Funkcja findNWD() oblicza największy wspólny dzielnik (NWD) dwóch liczb, co jest konieczne do obliczenia NWW.

Java – NWW – Podsumowanie

W tym materiale dowiedzieliśmy się jak obliczać NWW i jakie ma znaczenie. Pamiętaj, że NWW jest narzędziem matematycznym, które pojawia się w różnych kontekstach, a zrozumienie, jak go używać, może znacznie ułatwić rozwiązanie różnych problemów (również programistycznych).

Password generator  – „Wprowadź hasło” 🔓 – ten zwrot czytamy (jeżeli nie żyjemy w jaskini odcięci od świata) praktycznie codziennie. Hasło to forma uwierzytelnienia, która opiera się na czymś, co z założenia zna tylko użytkownik, czyli Ty lub Ja :). Hasło może być wymagane do komputera 💻, do konta w sklepie internetowym 🛒🛍️, ale również do banku 🏦. Czyli tak naprawdę jego rolą jest chronienie przed dostępem obcym, niepowołanym osobom do naszych poufnych prywatnych danych, ale również m.in. Twoich pieniędzy. Dlatego tak ważne jest, aby hasło było na tyle złożone, że będzie trudne do rozszyfrowania – W końcu nikt z nas nie chce, żeby obcy ludzie „dotykali” naszych rzeczy.

W tym materiale poopowiadam Ci o haśle, a w szczególności o cechach silnego hasła. Dowiesz się jak stworzyć swój własny generator silnego hasła.

Java – Password generator – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest hasło?
• Jakie cechy powinno mieć silne hasło?
• Czym jest generowanie haseł?
• Czym jest generator hasła?
• Co powinien robić dobry generator hasła?
• Jak wygląda algorytm generowania silnego hasła?

Hasło (ang. password)

Hasło to ciąg znaków używany do uwierzytelniania i przyznawania dostępu m.in. do systemu komputerowego, sieci WiFi lub konta bankowego. Jest to forma uprawnienia, która opiera się na czymś, co zna tylko użytkownik. Hasła mogą być tworzone przez m.in. użytkownika lub automatycznie generowane przez stronę, na której tworzymy konto. Hasło powinno być utrzymywane w tajemnicy, aby zapobiec nieautoryzowanemu dostępowi. Ważne jest, aby wybrać silne i unikalne hasło w celu ochrony informacji osobistych i danych przed ujawnieniem.

Silne hasło (ang. strong password)

Co to właściwie znaczy, że hasło powinno być silne 💪?

Najczęściej ustawiane hasła w Polsce to m.in.: 123456, qwerty i zaq123wsx, wiele z haseł zawiera imiona – ukochanej osoby, psa, mamy, swoje – Nie brzmi to, jak dobre zabezpieczenie Twoich danych? Czasem ktoś powie, ale to tylko do Netflixa, do maila mam silniejsze – A pamiętasz, że do platform streamingowych należy, podpiąć kartę kredytową? Czy hasło 123456 jest wystarczająco dobre i trudne do złamania, aby uniemożliwić wykradzenia danych Twojej karty?

Może trochę straszę 😱 :), ale obecne realia, są, jakie są i wykradanie danych jest już na porządku dziennym.

Wiemy, już jakie hasła nie są dobre 👍. To teraz sprawdźmy, co tak naprawdę powinno cechować silne hasło:

• Od 10 do 12 znaków — im więcej, tym lepiej.
• Różnorodne znaki — hasło nie powinno być znanym wyrazem np. imieniem lub miastem. Najlepiej sprawdzą się łańcuchy znaków. Wykorzystaj nie tylko litery, dodaj też liczby, znaki.
• Unikalne hasło do każdego konta — nie używaj tego samego hasła do różnych kont.
• Pamiętaj o regularnym zmienianiu haseł.

Entropia

Zagłębiając się w zagadnienie haseł, możesz natknąć się na takie pojęcie jak „entropia”.

Entropia jest miarą losowości i nieprzewidywalności, i jest krytycznym czynnikiem w generowaniu silnych haseł. Silne hasło powinno mieć wysoką entropię, aby utrudnić napastnikom jego odgadnięcie lub złamanie.

Im więcej możliwych kombinacji znaków w haśle, tym wyższa entropia i tym silniejsze hasło.

Jednym ze sposobów zwiększenia entropii przy generowaniu hasła jest użycie kombinacji dużych i małych liter, cyfr i znaków specjalnych. Na przykład hasło składające się z 8 losowych znaków (w tym dużych i małych liter, cyfr i znaków specjalnych) ma entropię około 52 bitów, co jest obecnie uważane za wystarczająco silne dla większości zastosowań.

Menedżery haseł i mierniki siły hasła często używają entropii do pomiaru siły hasła. Mogą one również zalecać określone wymagania dotyczące długości i składu hasła, aby zapewnić, że hasła mają wystarczającą entropię i są odporne na ataki.

Należy jednak pamiętać, że sama entropia nie wystarczy, aby zagwarantować bezpieczeństwo hasła. Inne czynniki, takie jak długość hasła, losowość znaków i częstotliwość zmian hasła, również odgrywają ważną rolę w określaniu ogólnego bezpieczeństwa hasła.

Menedżer haseł

Zaleca się mieć do każdego konta inne hasło. Ja obecnie mam mnóstwo kont, co tak naprawdę równa się = mnóstwo różnych haseł. Przy generowaniu haseł, szczególnie tych losowych — mogło to, by być naprawdę trudne. Całe szczęście, ktoś już rozwiązał ten problem i mamy do dyspozycji narzędzie zwane „menedżerem haseł”.

Menedżer haseł zapamiętuje i automatycznie podstawia w określone miejsca i szyfruje je. Menedżer wymaga zapamiętania tylko jednego głównego hasła do samego menedżera. Po zalogowaniu, menedżer haseł tworzy silne hasła dla wielu innych kont.

Strong password generator – Generator silnego hasła

Tworząc silne hasło trudne do złamania, możemy wspomóc się generatorem haseł. Generator haseł to  program lub skrypt, który tworzy losowe i unikalne kombinacje znaków. Działa on na podstawie algorytmów określających zasady tworzenia haseł.

Strong password generator – Cechy dobrego generatora

Skoro już wiemy, czym jest generator haseł, to teraz czas określić jakie cechy powinien mieć taki generator, aby nasze hasło było turbo silne. Generator powinien tworzyć hasło, które jest:

• Losowe: aby zminimalizować ryzyko odgadnięcia przez ataki słownikowe.
• Unikalne: każde nowo wygenerowane hasło powinno być inne od poprzednich.
• Zróżnicowane: wykorzystujące różne klasy znaków, takie jak litery, cyfry i znaki specjalne.
• Dostosowywalne: umożliwiające ustalanie długości i customowych wymagań dotyczących haseł.

Strong password generator – Krok po kroku

Zanim weźmiemy się za napisanie naszego generatora haseł, ustalmy plan działania – czyli określmy, co chcemy, aby nasz generator robił:

• Posiadał możliwość ustalenia wymagań hasła, tak aby program, tworzył hasła o dowolnej długości.
• Generował hasło — poprzez łączenie ze sobą różnych rodzai znaków, zostanie utworzony losowy i wyjątkowy ciąg znaków — nasze hasło.
• Prezentował wynik — wygenerowane hasło powinno zostać zaprezentowane użytkownikowi, który może skopiować je i użyć jako swoje nowe hasło.

Niektóre programy do generowania haseł oferują również dodatkowe usługi, takie jak: zapisywanie haseł w bezpiecznym sejfie lub informowanie o wycieku danych. My jednak skupimy się na podstawowych wyżej określonych funkcjach generatora haseł.

Strong password generator – Java

    private static final String CHAR_LOWER = "abcdefghijklmnopqrstuvwxyz";
    private static final String CHAR_UPPER = CHAR_LOWER.toUpperCase();
    private static final String NUMBER = "0123456789";
    private static final String SPECIAL_CHARACTERS = "!@#$%^&*()-_=+[{]};:'\",<.>/?\\|`~";

    public static void main(String[] args) {
        System.out.println(generatePassword(10));
    }

    public static String generatePassword(int length) {
        String characters = CHAR_LOWER + CHAR_UPPER + SPECIAL_CHARACTERS + NUMBER;
        Random random = new Random();
        char[] password = new char[length];

        for (int i = 0; i < length; i++) {
            password[i] = characters.charAt(random.nextInt(characters.length()));
        }
        return new String(password);
    }

• Stworzyliśmy łańcuch znaków składający z wielkich oraz małych liter, znaków specjalnych, a także liczb.
• W następnym kroku w pętli dodajemy losowe znaki z naszego łańcucha do tablicy znaków — wielkość tablicy jest zależna od wielkości, którą podaliśmy na wejściu.
• Utworzoną tablicę z różnymi znakami przekształcamy w Stringa — tak powstało nasze silne hasło :).

Strong password generator –Podsumowanie

W tym materiale zagłębiliśmy się w zagadnienie, jakim jest hasło. Wiemy już jakie cechy powinno mieć nasze hasło, aby było trudne do złamania.

Potrafimy już stworzyć silne hasło spełniające m.in. takie cechy jak losowość czy unikalność — To wszystko dzięki generatorowi haseł. Nigdy nie lekceważ tematu haseł — Te kilka znaków często chronią bardzo ważne zagadnienia, dlatego upewnij się, że hasła, jakie używasz, są dostatecznie silne.