Jak sortować tablicę w Javie

Sortowanie jest jedną z najczęstszych i niezbędnych operacji w programowaniu. Reprezentuje uporządkowanie pewnego zestawu elementów w określonej kolejności. Ten artykuł dotyczy standardowych metod sortowania tablic w Javie.

Krótko o sortowaniu

Sortowanie to zatem porządkowanie zbioru danych. W naszym przypadku tablice. Celem sortowania tablic lub innych struktur danych jest ułatwienie wyszukiwania, manipulowania lub analizowania danych w kolekcji. Programiści potrzebują sortowania tak często, że każdy język programowania zawiera wbudowane metody sortowania tablic, list i innych uporządkowanych struktur danych. Aby skorzystać z takich metod, zadzwoń do nich. Operacja jest maksymalnie uproszczona. Zwykle metody wbudowane są maksymalnie zoptymalizowane; w większości przypadków dobrym pomysłem jest użycie ich w pracy lub projektach. Jednak niemal każdy programista w trakcie studiów musi samodzielnie wdrożyć algorytmy sortowania. Dlatego te doskonałe ćwiczenia uczą Cię rozumieć samą istotę programowania. Ponadto czasami w pracy potrzebne są niestandardowe metody sortowania. Istnieje wiele algorytmów sortowania. Mają mocne i słabe strony, w zależności od rodzaju i rozmiaru zbiorów danych. Standardowe algorytmy sortowania obejmują sortowanie bąbelkowe, sortowanie przez wybór, sortowanie przez wstawianie, sortowanie przez scalanie i sortowanie szybkie.

Wbudowana metoda sortowania tablic w Javie: Arrays.sort

Zacznijmy od najprostszego. Ktoś już napisał dla nas metodę sortowania tablic w Javie. Metoda ta znajduje się w klasie Arrays , a dokładniej java.util.Arrays . Ta klasa zawiera różne metody pracy z tablicami, takie jak sortowanie i wyszukiwanie. Metoda Arrays.sort zapewnia wygodny sposób sortowania tablic w Javie niezależnie od tego, czy zawierają one ciągi znaków, liczby całkowite czy inne elementy. W Javie istnieje kilka odmian metody Arrays.sort . Oto kilka powszechnie używanych metod sortowania z klasy Arrays :

• Arrays.sort(Array) : użyj go do sortowania tablic typów pierwotnych lub obiektów w porządku rosnącym. Wykorzystuje naturalny porządek elementów.
• Arrays.sort(Array, fromIndex, toIndex) : Ta przeciążona metoda sortowania umożliwia sortowanie tylko części tablicy określonej przez parametry fromIndex i toIndex.
• Arrays.sort(Array, comparator) : ten służy do sortowania tablic obiektów przy użyciu niestandardowego komparatora. Komparator określa kolejność elementów.
• Arrays.parallelSort(Array) : Ta wersja metody sortuje Array równolegle, wykorzystując wiele wątków w celu zwiększenia wydajności. Jest to korzystne przy sortowaniu dużych tablic.
• Arrays.parallelSort(Array, fromIndex, toIndex) : Ta przeciążona wersja metody równoległej umożliwia sortowanie określonego zakresu elementów w Array .

Pozwalają na szybkie uporządkowanie elementów w oparciu o ich naturalną kolejność lub za pomocą niestandardowego komparatora. Przyjrzyjmy się tej metodzie na dwóch przykładach, z których jeden dotyczy ciągów znaków.

Przykład 1: Sortowanie ciągów

Załóżmy, że mamy szereg smyczkowych instrumentów muzycznych: „skrzypce”, „altówka”, „wiolonczela” i „kontrabas”. Do uporządkowania ich alfabetycznie możemy użyć metody Array.sort .

import java.util.Arrays;
//Arrays.sort example
public class StringSortExample {
    public static void main(String[] args) {
        String[] instruments = {"violin", "viola", "cello", "double bass"};

        Arrays.sort(instruments);

        System.out.println("Sorted Instruments:");
        for (String instrument : instruments) {
            System.out.println(instrument);
        }
    }
}

Dane wyjściowe są tutaj: W tym programie najpierw importujemy klasę java.util.Arrays , aby uzyskać dostęp do metody Array.sort . Następnie tworzymy tablicę ciągów zwaną instrumentami zawierającą nazwy instrumentów muzycznych. Następnie wywołujemy Arrays.sort(instruments) . Zatem ta metoda pobiera tablicę, sortuje elementy w porządku rosnącym w oparciu o ich naturalne uporządkowanie (alfabetyczne). Na koniec przeglądamy posortowaną tablicę i wypisujemy każdy instrument.

Przykład 2: Sortowanie liczb całkowitych

Rozważmy inny przykład, w którym sortujemy tablicę liczb całkowitych w porządku rosnącym.

import java.util.Arrays;

public class IntegerSortExample {
    public static void main(String[] args) {
        int[] numbers = {8, 2, 7, 3, 1, 5};
//sort an array using Arrays.sort
        Arrays.sort(numbers);

        System.out.println("Sorted Numbers:");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Wyjście: Tutaj tworzymy tablicę liczb całkowitych zwaną liczbami z kilkoma nieposortowanymi elementami. Następnie wywołujemy Arrays.sort(numbers), aby posortować tablicę w porządku rosnącym. Należy zauważyć, że metoda Array.sort modyfikuje lokalnie oryginalną tablicę. Aby więc zachować oryginalną Array , wykonaj kopię przed sortowaniem.

Przykład 3: kolejność malejąca

A co z sortowaniem malejącym? Dzięki Arrays.sort jest to również łatwe . Po prostu użyj niestandardowego komparatora. Oto przykład:

import java.util.Arrays;
import java.util.Comparator;
//Arrays.sort with custom comparator example
public class DescendingSortExample {
    public static void main(String[] args) {
        Integer[] numbers = {8, 2, 7, 3, 1, 5};
        //sort an Array using Arrays.sort
        Arrays.sort(numbers, Comparator.reverseOrder());

        System.out.println("Sorted Numbers (Descending):");
        for (int number : numbers) {
            System.out.println(number);
        }
    }
}

Dane wyjściowe są następujące: Tutaj mamy tablicę liczb całkowitych nazwanych liczbami. Przekazując Comparator.reverseOrder() jako drugi argument metody Arrays.sort , określamy niestandardowy komparator, który sortuje elementy w kolejności malejącej. Metoda Comparator.reverseOrder() zwraca komparator, który odwraca naturalną kolejność elementów. Należy zauważyć, że tutaj używamy klasy opakowania Integer zamiast pierwotnego typu int, ponieważ metoda Comparator.reverseOrder() wymaga obiektów. Jeśli masz tablicę pierwotnych wartości int, przed użyciem tego podejścia musisz także przekonwertować je na obiekty typu Integer . Używając niestandardowego komparatora, możesz łatwo sortować tablice w kolejności malejącej, używając metody Arrays.sort w Javie.

Napisane samodzielnie klasyczne algorytmy sortowania w Javie

Jeśli studiujesz informatykę samodzielnie lub na uniwersytecie, widziałeś już zadania sortowania tablicy . Istnieje wiele różnych algorytmów sortowania, a niektóre z nich zaimplementujemy w tym artykule. Ogólnie rzecz biorąc, im łatwiejszy jest algorytm do wdrożenia, tym jest mniej wydajny. Programiści mierzą efektywność algorytmów poprzez czas ich działania i ilość pamięci wydawanej na zasoby. Nie jest to tematem naszego artykułu, ale wspominamy, że Arrays.sort w Javie jest skutecznym algorytmem.

Sortowanie bąbelkowe

Zacznijmy od najpopularniejszego wśród studentów algorytmu: sortowania bąbelkowego. To proste: algorytm porównuje dwa elementy, a następnie zamienia je, jeśli są w niewłaściwej kolejności, i tak dalej, aż do końca tablicy. Okazuje się, że mniejsze elementy „unoszą się” do końca Array , niczym bąbelki w napoju gazowanym wyskakują do góry.

public class BubbleSort {

       public static void bubbleSort(int[] myArray) {
           int n = myArray.length;
           for (int i = 0; i < n - 1; i++) {
               for (int j = 0; j < n - i - 1; j++) {
                   if (myArray[j] > myArray[j + 1]) {
                       // Swap myArray[j] and myArray[j+1]
                       int temp = myArray[j];
                       myArray[j] = myArray[j + 1];
                       myArray[j + 1] = temp;
                   }
               }
           }
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 7, 90, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           bubbleSort(arr);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

W tym przypadku metoda przyjmuje jako dane wejściowe tablicę liczb całkowitych. Zewnętrzna pętla przechodzi od 0 do n-1. Tutaj n jest rozmiarem tablicy. Wewnętrzna pętla porównuje sąsiednie elementy. Jeśli kolejność jest błędna, metoda zamienia je. Procedurę tę powtarza się, aż cała tablica zostanie posortowana. Oto wynik naszego programu:

Sortowanie przez wybór

Algorytm selekcji sortuje tablicę, wielokrotnie znajdując najmniejszy element z nieposortowanej części i umieszczając go na początku. Napiszmy to w Javie:

public class SelectionSort {
   public static void selectionSort(int[] myArray) {
       int n = myArray.length;

       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;

           // Find the index of the minimum element in the unsorted part of the array
           for (int j = i + 1; j < n; j++) {
               if (myArray[j] < myArray[minIndex]) {
                   minIndex = j;
               }
           }

           // Swap the minimum element with the first element of the unsorted part
           int temp = myArray[minIndex];
           myArray[minIndex] = myArray[i];
           myArray[i] = temp;
       }
   }

   public static void main(String[] args) {
       int[] arr = {18, 28, 45, 2, 90, 7};

       System.out.println("Array before sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }

       selectionSort(arr);

       System.out.println("\nArray after sorting:");
       for (int num : arr) {
           System.out.print(num + " ");
       }
   }
}

Oto wynik programu: Wyjaśnijmy to krok po kroku. Zewnętrzna pętla wykonuje iterację od początku tablicy do przedostatniego elementu (aż do n-1). Ta pętla wybiera każdy element jeden po drugim jako punkt początkowy nieposortowanej części Array . Wewnątrz zewnętrznej pętli inicjujemy minIndex bieżącym indeksem i , zakładając, że jest to indeks najmniejszego elementu w nieposortowanej części Array . Wewnętrzna pętla zaczyna się od i+1 i prowadzi do ostatniego elementu Array . Wyszukuje indeks najmniejszego elementu w nieposortowanej części tablicy, porównując każdy element z bieżącym elementem minimalnym ( arr[minIndex] ). Jeśli znajdziemy element mniejszy niż bieżący element minimalny, aktualizujemy minIndex do indeksu nowego elementu minimalnego. Po zakończeniu wewnętrznej pętli znaleźliśmy indeks minimalnego elementu w nieposortowanej części Array . Następnie zamieniamy element minimalny z pierwszym elementem nieposortowanej części, używając tymczasowej zmiennej temp. Zewnętrzna pętla trwa do momentu posortowania wszystkich elementów, stopniowo rozszerzając posortowaną część Array . Na koniec posortowana tablica jest drukowana w metodzie głównej przed i po wywołaniu metody choiceSort .

Sortowanie przez scalanie

Sortowanie przez scalanie to algorytm dziel i zwyciężaj, który rekurencyjnie dzieli tablicę na mniejsze podtablice, sortuje je, a następnie łączy w celu uzyskania posortowanej tablicy. Sortowanie przez scalanie jest stabilne i szeroko stosowane, zwłaszcza gdy wymagana jest stabilność i gwarantowana złożoność czasowa w najgorszym przypadku.

public class MergeSort {

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

        int mid = myArray.length / 2;
        int[] left = new int[mid];
        int[] right = new int[myArray.length - mid];

        System.arraycopy(myArray, 0, left, 0, mid);
        System.arraycopy(myArray, mid, right, 0, myArray.length - mid);

        mergeSort(left);
        mergeSort(right);

        merge(myArray, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0; // index for left subarray
        int j = 0; // index for right subarray
        int k = 0; // index for merged array

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

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

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

    public static void main(String[] args) {
        int[] arr = {18, 2, 28, 7, 90, 45};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        mergeSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dane wyjściowe to: Wyjaśnijmy dokładniej jak to działa. Algorytm dzieli tablicę na dwie części rekurencyjnie, aż do osiągnięcia przypadku podstawowego (kiedy tablica ma jeden lub zero elementów). Następnie łączy posortowane połówki z powrotem, korzystając z metody scalania. Metoda scalania przyjmuje jako dane wejściowe trzy tablice: oryginalną Array oraz lewą i prawą podtablicę (lewą i prawą). Porównuje elementy z lewej i prawej podtablicy i łączy je w oryginalną tablicę w posortowanej kolejności.

Sortowanie przez wstawianie

Sortowanie przez wstawianie polega na wielokrotnym wstawianiu elementu z nieposortowanej części we właściwe miejsce w posortowanej części. Działa dobrze w przypadku małych zestawów danych lub prawie posortowanych danych.

public class InsertionSort {
    public static void insertionSort(int[] myArray) {
        int n = myArray.length;

        for (int i = 1; i < n; i++) {
            int key = myArray[i];
            int j = i - 1;

            while (j >= 0 && myArray[j] > key) {
                myArray[j + 1] = myArray[j];
                j--;
            }

            myArray[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {18, 90, 7, 28, 45, 2};

        System.out.println("Array before sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

        System.out.println("\nArray after sorting:");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

Dane wyjściowe programu są takie same jak zwykle: Tutaj metoda InsertionSort implementuje algorytm sortowania przez wstawianie. Iteruje po tablicy i traktuje każdy element jako klucz. Porównuje klucz z elementami znajdującymi się przed nim i przesuwa je o jedną pozycję do przodu, jeśli są większe, skutecznie przesuwając elementy, aby zrobić miejsce dla klucza we właściwej pozycji. Zewnętrzna pętla iteruje od drugiego elementu ( i = 1 ) do ostatniego elementu Array. Wewnętrzna pętla zaczyna się od bieżącego elementu ( arr[i] ) i cofa się ( j = i-1 ), aż znajdzie właściwą pozycję dla klawisza lub dotrze do początku Array . Wewnątrz wewnętrznej pętli, jeśli element ( arr[j] ) jest większy niż klucz, jest przesuwany o jedną pozycję do przodu ( arr[j + 1] = arr[j] ), aby zrobić miejsce na klucz. Proces ten trwa do momentu znalezienia prawidłowego położenia klucza. Po zakończeniu wewnętrznej pętli klawisz jest umieszczany we właściwej pozycji ( arr[j + 1] = key ). W metodzie main tworzona jest przykładowa tablica, która jest drukowana przed i po sortowaniu metodą InsertionSort .

Szybkie sortowanie

Szybkie sortowanie to algorytm typu „dziel i zwyciężaj”, który wybiera element przestawny i dzieli tablicę wokół tego elementu. Z reguły sortowanie szybkie jest szybsze niż sortowanie przez scalanie w przypadku małych i średnich zbiorów danych ze względu na niskie stałe współczynniki.

public class QuickSort {

       public static void quickSort(int[] myArray, int low, int high) {
           if (low < high) {
               int pivotIndex = partition(myArray, low, high);
               quickSort(myArray, low, pivotIndex - 1);
               quickSort(myArray, pivotIndex + 1, high);
           }
       }

       public static int partition(int[] arr, int low, int high) {
           int pivot = arr[high];
           int i = low - 1;

           for (int j = low; j < high; j++) {
               if (arr[j] <= pivot) {
                   i++;
                   swap(arr, i, j);
               }
           }

           swap(arr, i + 1, high);
           return i + 1;
       }

       public static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }

       public static void main(String[] args) {
           int[] arr = {18, 28, 2, 90, 7, 45};

           System.out.println("Array before sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }

           quickSort(arr, 0, arr.length - 1);

           System.out.println("\nArray after sorting:");
           for (int num : arr) {
               System.out.print(num + " ");
           }
       }
}

Dane wyjściowe są tutaj: Mamy więc trzy metody implementacji szybkiego sortowania. Metoda QuickSort przyjmuje trzy parametry: Array , który ma zostać posortowany, niski indeks podtablicy i wysoki indeks podtablicy. Początkowo sprawdza, czy podtablica zawiera więcej niż jeden element. Jeśli tak, wybiera element przestawny przy użyciu metody partycjonowania, rekurencyjnie sortuje podtablicę przed elementem przestawnym i rekurencyjnie sortuje podtablicę po przestawie. Metoda partycji wybiera element przestawny jako ostatni element podtablicy ( arr[high] ). Ustawia indeks podziału (i) na dolny indeks minus 1. Następnie wykonuje iterację od niskiego indeksu do wysokiego indeksu - 1 i sprawdza, czy każdy element jest mniejszy lub równy osi obrotu. Jeśli tak, zamienia element z elementem o indeksie partycji (i) i zwiększa indeks partycji. Na koniec zamienia element obrotowy z elementem o indeksie partycji + 1 i zwraca indeks partycji. Metoda partycji wybiera element przestawny jako ostatni element podtablicy ( arr[high] ). Ustawia indeks podziału (i) na dolny indeks minus 1. Następnie wykonuje iterację od niskiego indeksu do wysokiego indeksu - 1 i sprawdza, czy każdy element jest mniejszy lub równy osi obrotu. Jeśli tak, zamienia element z elementem o indeksie partycji (i) i zwiększa indeks partycji. Na koniec zamienia element obrotowy z elementem o indeksie partycji + 1 i zwraca indeks partycji. Metoda wymiany to metoda narzędziowa używana do zamiany dwóch elementów w Array . W metodzie main tworzona jest przykładowa tablica, która jest drukowana przed i po sortowaniu metodą QuickSort .

Wnioski

Z tego artykułu dowiesz się, jak sortować tablicę w języku Java. Możesz użyć wbudowanej metody Arrays.sort lub napisać własne implementacje popularnych metod sortowania, takich jak sortowanie bąbelkowe, sortowanie przez scalanie i tak dalej. Możesz także spróbować zaatakować własną metodę sortowania. To zależy od Twojego zadania. Jeśli chcesz szybko rozwiązać problem z sortowaniem, po prostu skorzystaj z wcześniej napisanej metody. Jeśli uczysz się programowania i starasz się być w tym lepszy, naprawdę dobrym pomysłem jest samodzielne napisanie kilku metod sortowania.