Algorytmy sortowania w Verse

Sortowanie to prosta, ale potężna funkcja. Dysponując nieuporządkowaną listą elementów, możesz użyć algorytmu, aby posortować je w określonej kolejności. Chociaż pomysł ten może wydawać się podstawowy, sortowanie jest wszechobecne w informatyce w różnych jego aspektach i formach. Jednym z najważniejszych zastosowań jest przyspieszenie wyszukiwania. Na przykład komputer sortuje pliki według nazwy i rozmiaru, dzięki czemu możesz szybko znaleźć ten, którego potrzebujesz. UEFN pozwala sortować obiekty w Outlinerze według Typu, aby umożliwić grupowanie elementów i porządkowanie projektu. W Fortnite gracze na tablicy wyników w grze są sortowani według wielu różnych statystyk, takich jak eliminacje i czas okrążenia, dzięki czemu wiadomo, kto jest na pierwszym miejscu.

Zastosowanie sortowania do kodu Verse może pomóc ci podnieść poziom rozgrywki i ulepszyć aspekty tworzenia gier. Co powiesz na przykład na uporządkowanie tablicy graczy według ich wyników w turnieju, w którym gracze, którzy uzyskali najmniej punktów w każdej rundzie, zostają wyeliminowani? Sortując taką tablicę po zakończeniu każdej rundy, możesz szybko wyszukać graczy z najniższą liczbą punktów i ustawić ich jako widzów. Z drugiej strony możesz równie szybko ustalić graczy z najlepszym wynikiem i przyznać im premię w następnej rundzie. Możesz nawet użyć tej posortowanej listy do utworzenia trwałych lokalnych rankingów, aby gracze wiedzieli, na kogo uważać podczas gry. A jeśli masz listę osób, które chcesz powitać na swojej wyspie, możesz posortować ich nazwy alfabetycznie, aby ułatwić ich wyświetlanie.

Każdy z tych przykładów wykorzystuje sortowanie na różne sposoby, ale do osiągnięcia swojego celu wszystkie wykorzystują algorytm sortowania. Algorytmy sortowania implementują logikę, która sortuje listy; istnieje wiele różnych typów do wyboru w zależności od potrzeb. Choć sortowanie jest potężnym narzędziem, ważne jest, aby zrozumieć, jak działa, jeśli chcesz zintegrować je w swoich projektach. Ta strona opisuje główne idee stojące za sortowaniem i wyjaśnia, jak wybrać algorytm, który najlepiej sprawdzi się w danym projekcie. Aby uzyskać implementacje konkretnych algorytmów sortowania, kliknij link na końcu tej strony.

Sortowanie przez scalanie

Sortowanie przez scalanie to algorytm sortujący typu „dziel i zwyciężaj”. Oznacza to, że dzieli on grupę elementów, które mają zostać posortowane, na mniejsze grupy i sortuje mniejsze grupy. Następnie łączy mniejsze grupy, wiedząc, że są one już posortowane.

Implementowanie sortowania przez scalanie

Poniższa implementacja wywołuje samą siebie, aby przeprowadzić sortowanie przez scalanie podzielonych tablic, co oznacza, że jest to funkcja rekurencyjna. Podczas korzystania z funkcji rekurencyjnej musisz określić przypadek bazowy, aby zapobiec nieskończonej rekurencji. Ten algorytm za każdym razem dzieli tablice na pół, dlatego przypadkiem bazowym jest sytuacja, gdy tablica ma tylko jeden element, więc jest uznawana za posortowaną. Następnie można ją połączyć z inną jednoelementową tablicą i tak dalej, aż z powrotem do pełnej tablicy elementów.

Poniższa implementacja ma charakter ogólny, ponieważ wykorzystuje parametryczne typy dla swoich parametrów. Oznacza to, że możesz użyć dowolnego typu dla elementów i własnej funkcji porównania jako argumentów. Możesz więc posortować tablicę liczb całkowitych lub tablicę bardziej złożonego typu, jak np. klasa, którą również możesz sortować. Funkcja Compare jest kolejnym parametrem, do którego możesz przekazać własne niestandardowe funkcje. Jeśli chcesz sortować elementy od najmniejszego do największego lub według określonych pól klasy, możesz określić to w funkcji niestandardowej, bez modyfikowania implementacji tej funkcji ogólnej.

Postępuj zgodnie z poniższą instrukcją, aby zaimplementować sortowanie przez scalanie w Verse:

1. Zacznijmy od napisania przypadku bazowego: tylko jeden element w tablicy. Jeśli w tablicy znajduje się nie więcej niż jeden element, zwróć argument tablicy, który został przekazany do funkcji.

    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy.
        else:
            # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy.
            Tablica
   Copy full snippet

   MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy. else: # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy. Tablica

2. Następnie podziel tablicę na pół.

    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy.
            Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy.
            Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1.
            Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy.
        else:
            # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy.
            Tablica
   Copy full snippet

   MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy. Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy. Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1. Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy. else: # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy. Tablica

3. Wywołaj MergeSort na każdej połowie początkowej tablicy, a następnie wywołaj Merge, aby scalić obie połówki razem.

    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy.
            Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy.
            Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1.
            Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy.
        then:
            # Wywołaj MergeSort na lewej połowie tablicy.
            LeftSorted:[]t = MergeSort(Left, Compare)
   
            # Wywołaj MergeSort na prawej połowie tablicy.
            RightSorted:[]t = MergeSort(Right, Compare)
   
            # Połącz dwie tablice i zwróć wynik.
            Merge(LeftSorted, RightSorted, Compare)
        else:
            # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy.
            Tablica
   Copy full snippet

   MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy. Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy. Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1. Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy. then: # Wywołaj MergeSort na lewej połowie tablicy. LeftSorted:[]t = MergeSort(Left, Compare) # Wywołaj MergeSort na prawej połowie tablicy. RightSorted:[]t = MergeSort(Right, Compare) # Połącz dwie tablice i zwróć wynik. Merge(LeftSorted, RightSorted, Compare) else: # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy. Tablica

4. Podczas scalania dwóch połówek z powrotem porównaj elementy z każdej tablicy i dodaj je do wynikowej tablicy, aż wszystkie elementy z obu tablic zostaną dodane. W tym celu przygotuj zmienną indeksu do śledzenia pozycji w każdej tablicy. Za każdym razem, gdy funkcja Compare się powiedzie, element lewej tablicy powinien zostać dodany, a jego zmienna indeksu przesunięta do następnej pozycji w tablicy, w przeciwnym razie to samo powinno zostać wykonane dla elementu prawej tablicy. Po dodaniu wszystkich elementów z jednej z tablic, dodaj pozostałe elementy z drugiej tablicy, ponieważ została już ona posortowana.

    # Funkcja pomocnicza dla MergeSort, która łączy podzielone tablice w kolejności opartej na funkcji Compare.
    Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        var LeftIndex:int = 0
        var RightIndex:int = 0
        var MergedArray:[]t = array{}
       
        # Wykonaj pętlę przez wszystkie elementy w tablicach, aby dodać je do zmiennej MergedArray.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # Sprawdź element w lewej tablicy względem elementu w prawej tablicy.
                # Używa funkcji Compare przekazanej jako argument
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # W tym momencie zostały dodane wszystkie elementy z jednej z tablic.
                # Teraz sprawdź, która tablica ma jeszcze elementy do scalenia, i dodaj wszystkie pozostałe elementy.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}
                # Wyjdź z pętli, ponieważ dodawanie wszystkich elementów zostało zakończone.
                break
   
        # Zwróć scaloną tablicę.
        MergedArray
   Copy full snippet

   # Funkcja pomocnicza dla MergeSort, która łączy podzielone tablice w kolejności opartej na funkcji Compare. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Wykonaj pętlę przez wszystkie elementy w tablicach, aby dodać je do zmiennej MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Sprawdź element w lewej tablicy względem elementu w prawej tablicy. # Używa funkcji Compare przekazanej jako argument if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # W tym momencie zostały dodane wszystkie elementy z jednej z tablic. # Teraz sprawdź, która tablica ma jeszcze elementy do scalenia, i dodaj wszystkie pozostałe elementy. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Wyjdź z pętli, ponieważ dodawanie wszystkich elementów zostało zakończone. break # Zwróć scaloną tablicę. MergedArray

Kompletny skrypt

    # Algorytm sortujący typu „dziel i zwyciężaj”, który dzieli układ na dwie części, sortuje podzielony układ, następnie scala oba układy.
    # Jest to implementacja rekurencyjna, w której funkcja wywołuje samą siebie, aby przeprowadzić sortowanie przez scalanie podzielonych tablic.
    # Przypadek bazowy (warunek zatrzymania rekurencji) jest taki, że tablica ma tylko jeden element.
    # Jest to ogólna implementacja wykorzystująca typy parametryczne, więc możesz podać własny typ i własną funkcję porównania jako argumenty.
    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy.
            Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy.
            Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1.
            Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy.
        then:
            # Wywołaj MergeSort na lewej połowie tablicy.
            LeftSorted:[]t = MergeSort(Left, Compare)

            # Wywołaj MergeSort na prawej połowie tablicy.
            RightSorted:[]t = MergeSort(Right, Compare)

            # Połącz dwie tablice i zwróć wynik.
            Merge(LeftSorted, RightSorted, Compare)
        else:

            # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy.
            Tablica

    # Funkcja pomocnicza dla MergeSort, która łączy podzielone tablice w kolejności opartej na funkcji Compare.
    Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        var LeftIndex:int = 0
        var RightIndex:int = 0
        var MergedArray:[]t = array{}

        # Wykonaj pętlę przez wszystkie elementy w tablicach, aby dodać je do zmiennej MergedArray.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # Sprawdź element w lewej tablicy względem elementu w prawej tablicy.
                # Używa funkcji Compare przekazanej jako argument
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # W tym momencie zostały dodane wszystkie elementy z jednej z tablic.
                # Teraz sprawdź, która tablica ma jeszcze elementy do scalenia, i dodaj wszystkie pozostałe elementy.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}
                # Wyjdź z pętli, ponieważ dodawanie wszystkich elementów zostało zakończone.
                break

        # Zwróć scaloną tablicę.
        MergedArray
Copy full snippet

# Algorytm sortujący typu „dziel i zwyciężaj”, który dzieli układ na dwie części, sortuje podzielony układ, następnie scala oba układy. # Jest to implementacja rekurencyjna, w której funkcja wywołuje samą siebie, aby przeprowadzić sortowanie przez scalanie podzielonych tablic. # Przypadek bazowy (warunek zatrzymania rekurencji) jest taki, że tablica ma tylko jeden element. # Jest to ogólna implementacja wykorzystująca typy parametryczne, więc możesz podać własny typ i własną funkcję porównania jako argumenty. MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Sprawdź, czy w tablicy znajduje się więcej niż jeden element, a jeśli nie, otrzymujemy przypadek bazowy. Mid:int = Floor(Length / 2) # Pobierz środkowy indeks tablicy. Left:[]t = Array.Slice[0, Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od początku do indeksu Mid - 1. Right:[]t = Array.Slice[Mid] # Podziel tablicę na pół. Ta część przechowuje elementy od indeksu Mid do końca tablicy. then: # Wywołaj MergeSort na lewej połowie tablicy. LeftSorted:[]t = MergeSort(Left, Compare) # Wywołaj MergeSort na prawej połowie tablicy. RightSorted:[]t = MergeSort(Right, Compare) # Połącz dwie tablice i zwróć wynik. Merge(LeftSorted, RightSorted, Compare) else: # Zwróć przekazaną tablicę, ponieważ osiągnięto przypadek bazowy. Tablica # Funkcja pomocnicza dla MergeSort, która łączy podzielone tablice w kolejności opartej na funkcji Compare. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Wykonaj pętlę przez wszystkie elementy w tablicach, aby dodać je do zmiennej MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Sprawdź element w lewej tablicy względem elementu w prawej tablicy. # Używa funkcji Compare przekazanej jako argument if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # W tym momencie zostały dodane wszystkie elementy z jednej z tablic. # Teraz sprawdź, która tablica ma jeszcze elementy do scalenia, i dodaj wszystkie pozostałe elementy. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Wyjdź z pętli, ponieważ dodawanie wszystkich elementów zostało zakończone. break # Zwróć scaloną tablicę. MergedArray

Wybór algorytmu

Chociaż wiele algorytmów sortowania opiera się na podobnych założeniach, istnieje kilka elementów wyróżniających każdy z nich, które mogą mieć duży wpływ na działanie algorytmu.

Złożoność czasowa

Algorytmy potrzebują czasu, a im więcej zadań mają do wykonania, tym dłużej to potrwa. Na złożoność problemu, który algorytm próbuje rozwiązać, wpływa wiele czynników, a ilość czasu potrzebnego na jego rozwiązanie nazywana jest złożonością czasową.

Ponieważ obliczenie dokładnego czasu potrzebnego na ukończenie algorytmu jest prawie niemożliwe ze względu na różne czynniki, takie jak sprzęt komputerowy, inny uruchomiony kod lub rodzaj danych, z którymi pracujesz, złożoność czasowa jest zamiast tego mierzona w operacjach lub liczbie działań, które algorytm musi wykonać, aby się zakończyć. Każdy algorytm jest inny, zatem czas potrzebny na przetworzenie zbioru danych jest reprezentowany za pomocą notacji dużego O. Notacja dużego O nie opisuje dokładnej liczby wymaganych operacji, ale opisuje, jak liczba ta zmienia się wraz ze wzrostem rozmiaru listy, którą wprowadzasz do algorytmu.

Przypuśćmy na przykład, że piszesz algorytm mający na celu znalezienie najmniejszej liczby na liście. Nie wiesz, czy lista jest uporządkowana, więc twój algorytm musi sprawdzić każdą liczbę, aby dowiedzieć się, czy jest najmniejsza. Jeśli na liście znajdują się trzy elementy, algorytm wykonuje trzy sprawdzenia, a jeśli jest ich dziesięć – wykonuje dziesięć sprawdzeń. Liczba operacji wzrasta liniowo wraz z rozmiarem wejściowym listy, więc złożoność czasowa jest liniowa lub wynosi O(n), gdzie n jest liczbą elementów na liście. Jeśli algorytm musiałby wykonać dwie operacje na element, takie jak skopiowanie każdego elementu na inną listę po każdym sprawdzeniu, złożoność czasowa wyniosłaby O(2n), ponieważ liczba operacji wynosi 2 * NumberOfItems.

A co, jeśli algorytm chciałby tylko sprawdzić, czy na liście znajdują się jakieś elementy? Ponieważ algorytm wykonuje tylko jedną operację niezależnie od rozmiaru danych wejściowych, złożoność czasowa byłaby stała, czyli O(1). Istnieje wiele innych przykładów, takich jak czas kwadratowy (O(n^2)) lub czas silniowy (O(n!)), ale ważne jest to, że każdy z nich opisuje, w jaki sposób liczba wykonywanych operacji rośnie wraz z rozmiarem danych wejściowych.

Złożoność w sortowaniu

Pomiar złożoności czasowej algorytmów sortowania staje się o wiele bardziej skomplikowany ze względu na różne stany, w jakich może znajdować się lista przed sortowaniem. Co, jeśli jest już posortowana? Co, jeśli jest posortowana w odwrotnej kolejności? Wydajność algorytmu sortowania może się znacznie różnić w zależności od tych czynników, dlatego algorytmy sortowania są zwykle mierzone na podstawie ich najlepszej, najgorszej i średniej złożoności czasowej.

Dla przykładu spójrzmy na algorytm sortowania bąbelkowego. W najlepszym przypadku, biorąc pod uwagę już posortowaną listę, sortowanie bąbelkowe musi tylko sprawdzić każdą parę elementów, ale nie będzie musiało dokonywać żadnych zamian! Oznacza to, że w najlepszym przypadku złożoność czasowa wyniesie O(n), co jest świetnym wynikiem! Co jednak z przeciwnym scenariuszem, w którym lista jest posortowana w odwrotnej kolejności? W tej sytuacji sortowanie bąbelkowe będzie musiało wykonać n sprawdzeń i zamienić każdy element na liście n razy, co oznacza, że złożoność czasowa w najgorszym przypadku wyniesie n * n lub O(n^2). W porównaniu do innych algorytmów sortowania, ten jest uważany za powolny i może bardzo szybko wymknąć się spod kontroli, ponieważ algorytm potrzebowałby co najmniej stu operacji, aby przetworzyć listę składającą się z dziesięciu elementów. Wyobrażasz sobie, ile operacji wymagałoby sto elementów? A tysiąc?

Zamiast najlepszego i najgorszego przypadku, algorytmy sortowania zwykle działają w sposób zbliżony do ich średniego przypadku. Na przykład średnia złożoność przypadku sortowania przez scalanie wynosi O(nlogn). Jest to uważane za dobry punkt odniesienia, ponieważ wiele innych popularnych algorytmów sortowania ma najlepszą, najgorszą i średnią złożoność na tym poziomie lub bardzo blisko niego. Sortowanie bąbelkowe z powyższego przykładu ma średnią złożoność O(n^2), więc nawet w średnim przypadku nadal jest stosunkowo wolne.

Znajomość złożoności czasowej jest ważna przy wyborze algorytmu, ponieważ kod ma działać szybko i podobnie bez względu na rodzaj danych wejściowych. Aby zapoznać się z przykładami popularnych algorytmów sortowania o dużej wydajności, zapoznaj się z artykułami Merge Sort (Sortowanie przez scalanie) i Quicksort (Szybkie sortowanie). Oba te algorytmy w najlepszym, najgorszym i średnim przypadku mają taką samą złożoność O(nlogn) i są dobrym punktem wyjścia dla każdej sytuacji sortowania.

Złożoność przestrzenna

Oprócz złożoności czasowej, ważne jest również, aby wziąć pod uwagę, ile elementów musi utworzyć algorytm, aby zakończyć sortowanie. Jest to złożoność przestrzenna lub ilość dodatkowych danych tworzonych podczas uruchamiania algorytmu. Podobnie jak złożoność czasowa, złożoność przestrzenna jest mierzona za pomocą notacji dużego O, która różni się w zależności od algorytmu. Na przykład złożoność przestrzenna sortowania przez scalanie wynosi O(n), ponieważ dzieli ono listę na n podlist. Algorytmy, które sortują obiekty w miejscu (tzn. modyfikują tylko istniejące dane, a nie tworzą nowych), mają złożoność przestrzenną O(1). Jeśli pracujesz z bardzo dużymi listami, złożoność przestrzenna może być właśnie tym, na co warto zwrócić uwagę przy wyborze algorytmu.

Verse jest językiem programowania funkcyjnego, dlatego operacje API struktury danych zwracają zmodyfikowane wersje oryginalnego elementu przekazanego jako dane wejściowe. Na przykład żadna z funkcji Insert() i RemoveElement() tablicy nie modyfikuje oryginalnej tablicy, ale zamiast tego tworzy i zwraca nową tablicę po wykonaniu funkcji. Może to prowadzić do wyższych wymagań w zakresie złożoności czasowej i przestrzennej, uwzględniających tworzenie tych nowych elementów.

Stabilność

Często podczas sortowania algorytm natrafia na remisy. Jeśli na przykład dwóch graczy ma po pięć punktów, jak algorytm powinien ich posortować? W tym scenariuszu stabilny algorytm zachowa kolejność, w jakiej równe elementy pojawiają się na liście po sortowaniu. Zatem jeśli gracz nr 1 był przed graczem nr 2 na liście przed sortowaniem, to na posortowanej liście nadal będzie on przed graczem nr 2.

Jednakże niestabilny algorytm nie zachowa tej kolejności, co oznacza, że gracz nr 2 może pojawić się przed graczem nr 1. Jest to ważne, jeśli twój kod ma zwracać uwagę na kilka pierwszych elementów na liście, na przykład jeśli chcesz pobrać trzech najlepszych graczy według wyniku, aby wyświetlić ich na tablicy wyników. W takiej sytuacji potrzebujesz stabilnego algorytmu, aby upewnić się, że gracz, który osiągnął ten wynik jako pierwszy, pozostanie na tablicy wyników.

Testowanie i profilowanie algorytmów

Chociaż dobrze jest wiedzieć, jak algorytm powinien działać, biorąc pod uwagę złożoność czasową i przestrzenną, ważniejsze jest zmierzenie, jak algorytm faktycznie działa na rzeczywistych danych wejściowych. Opracowywanie algorytmów sortowania może być trudne i czasem trudno określić, czy kod działa spójnie dla wszystkich danych wejściowych. To właśnie tutaj wkraczają testy. Konfigurując funkcję testowania, możesz zmierzyć dokładność swojego kodu i określić, jak zachowuje się on podczas jego rozwijania. Możesz także sprawdzić, czy zmodyfikowanie implementacji testowanego rozwiązania nie doprowadzi do obniżenia wydajności. Postępuj zgodnie z poniższą instrukcją, aby skonfigurować plik testowania algorytmów sortowania i uzyskać dane wyjściowe dotyczące ich wydajności:

1. Utwórz funkcję zawodną o nazwie RunArrayTest.

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest()<decides><transacts>:void=
   Copy full snippet

   # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest()<decides><transacts>:void=

2. Dodaj argument dla tablicy, na której chcesz uruchomić sortowanie, i funkcję porównania, której chcesz użyć.

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
        # Wykonaj sortowanie przez scalanie
        ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)
   Copy full snippet

   # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Wykonaj sortowanie przez scalanie ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

3. Teraz musisz porównać posortowaną tablicę z oczekiwanymi wartościami. Dodaj argument dla oczekiwanej tablicy, aby porównać ją z posortowaną tablicą rzeczywistą w celu sprawdzenia poprawności wyniku.

   Porównaj elementy w ResultArray z elementami w ExpectedArray. Funkcja RunArrayTest jest zawodna, więc gdy tylko element nie pasuje, funkcja testowania kończy się niepowodzeniem.

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
        # Wykonaj sortowanie przez scalanie
        ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)
   
        # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected
   Copy full snippet

   # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Wykonaj sortowanie przez scalanie ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected

4. Dodaj funkcję argumentu w celu wyświetlenia tablic przy każdym kroku, aby można było je porównać, jeśli test się nie powiedzie, i dowiedzieć się, jak naprawić testowany kod.

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
        # Wykonaj sortowanie przez scalanie
        ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)
   
        # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów.
        ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}")
        ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}")
        ProjectLog("Wynik: {ArrayToString(ResultArray)}")
   
        # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected
   Copy full snippet

   # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Wykonaj sortowanie przez scalanie ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów. ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}") ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}") ProjectLog("Wynik: {ArrayToString(ResultArray)}") # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected

5. Funkcja testowania sprawdza dokładność wyniku, ale z testu możesz także uzyskać więcej informacji. Za pomocą wyrażenia profilującego możesz zmierzyć wydajność swoich algorytmów, rejestrując czas potrzebny na ukończenie algorytmu.

   Jest to przydatne, jeśli chcesz porównać wydajność różnych algorytmów sortowania lub przetestować, jak działają algorytmy przy różnych danych wejściowych. Poszczególne algorytmy mogą działać bardzo różnie, biorąc pod uwagę najlepsze i najgorsze przypadki danych wejściowych, a profilowanie pozwala znaleźć i przetestować te przypadki, aby wiedzieć, na co zwrócić uwagę. Podczas wielu testów możesz ocenić średnią wydajność algorytmu i oszacować, jak będzie on działał na danych wejściowych o danym rozmiarze.

6. Dodaj argument pod postacią ciągu tekstowego o nazwie Description, który wyjaśnia, na czym koncentruje się test. Możesz dodać to do wyrażenia profile, aby zarejestrować opis z wartością czasową.

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
   
        # Wykonaj sortowanie przez scalanie i profiluj kod.
        ResultArray := profile(Description):
            SortingAlgorithms.MergeSort(ActualArray, Compare)
   
        # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów.
        ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}")
        ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}")
        ProjectLog("Wynik: {ArrayToString(ResultArray)}")
       
        # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected
   Copy full snippet

   # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Wykonaj sortowanie przez scalanie i profiluj kod. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów. ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}") ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}") ProjectLog("Wynik: {ArrayToString(ResultArray)}") # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected

Pisanie przypadków testowych

Zacznij od czegoś prostego. Wyizoluj to, co testujesz. Przetestuj tablicę liczb całkowitych, aby posortować od najmniejszej do największej wartości.

1. Utwórz funkcję porównania dla liczb całkowitych.

    # Funkcja porównania używana jako argument do sortowania liczb całkowitych od najmniejszej do największej.
    IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
        Left < Right
   Copy full snippet

   # Funkcja porównania używana jako argument do sortowania liczb całkowitych od najmniejszej do największej. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right

2. Utwórz funkcję pomocniczą do konwersji tablicy liczb całkowitych na ciąg tekstowy.

    # Funkcja pomocnicza do konwersji tablicy liczb całkowitych na ciąg tekstowy.
    IntArrayToString(Array:[]int)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"
   Copy full snippet

   # Funkcja pomocnicza do konwersji tablicy liczb całkowitych na ciąg tekstowy. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]"

3. Utwórz urządzenie Verse, aby uruchomić test.

    # Ten plik zawiera testy sprawdzające, czy algorytm sortowania zachowuje się zgodnie z oczekiwaniami.
    # Testy obejmują również profilowanie kodu w celu sprawdzenia wydajności algorytmu.
   
    using { /Fortnite.com/Devices }
    using { /UnrealEngine.com/Temporary/Diagnostics }
    using { /Verse.org/Simulation }
    using { /Verse.org/Random }
   
    my_log_channel<public> := class(log_channel):
   
    # "Rejestrator" na poziomie projektu, w którym rejestrowane będą komunikaty z funkcji, które nie należą do klasy dziennika.
    # Funkcja Print, która nie jest funkcją Logger, to <no_rollback>, więc nie można jej użyć w funkcji <transacts>.
    ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
        Logger := log{Channel := my_log_channel}
        Logger.Print(Message, ?Level := Level)
   
    # Urządzenie trybu kreatywnego utworzone w Verse, które można umieścić w poziomie.
    # Umieść w poziomie, aby uruchamiać testy i profilować kod.
    test_sorting := class(creative_device):
   
        # Działa po uruchomieniu urządzenia w aktywnej grze
        OnBegin<override>()<suspends>:void=
            # Przykładowe tablice do wykorzystania w teście.
            Test1ExpectedIntArray:[]int = array{}
            Test1ActualIntArray:[]int = array{}
   
            # Uruchom testy i zgłoś, czy zakończyły się niepowodzeniem czy powodzeniem.
            if:
                RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
            then:
                ProjectLog("Wszystkie testy zaliczone.")
            else:
                ProjectLog("Co najmniej jeden test nie powiódł się.")
   Copy full snippet

   # Ten plik zawiera testy sprawdzające, czy algorytm sortowania zachowuje się zgodnie z oczekiwaniami. # Testy obejmują również profilowanie kodu w celu sprawdzenia wydajności algorytmu. using { /Fortnite.com/Devices } using { /UnrealEngine.com/Temporary/Diagnostics } using { /Verse.org/Simulation } using { /Verse.org/Random } my_log_channel<public> := class(log_channel): # "Rejestrator" na poziomie projektu, w którym rejestrowane będą komunikaty z funkcji, które nie należą do klasy dziennika. # Funkcja Print, która nie jest funkcją Logger, to <no_rollback>, więc nie można jej użyć w funkcji <transacts>. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Urządzenie trybu kreatywnego utworzone w Verse, które można umieścić w poziomie. # Umieść w poziomie, aby uruchamiać testy i profilować kod. test_sorting := class(creative_device): # Działa po uruchomieniu urządzenia w aktywnej grze OnBegin<override>()<suspends>:void= # Przykładowe tablice do wykorzystania w teście. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Uruchom testy i zgłoś, czy zakończyły się niepowodzeniem czy powodzeniem. if: RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("Wszystkie testy zaliczone.") else: ProjectLog("Co najmniej jeden test nie powiódł się.")

4. Teraz wypełnij tablice testowe wartościami.

    var ArrayLength:int = GetRandomInt(10, 100)
            Test1ExpectedIntArray:[]int =
                for (Count := 0..ArrayLength):
                	Licznik
            Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)
   Copy full snippet

   var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Licznik Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

5. Uruchom test, przeciągając urządzenie Verse do swojego poziomu

Poniżej znajdziesz więcej pomysłów na testy, które możesz przeprowadzić:

* Posortuj tablicę liczb całkowitych od największej do najmniejszej.

        # Funkcja porównania używana jako argument do sortowania liczb całkowitych od największej do najmniejszej.
        IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
            Left > Right
Copy full snippet

# Funkcja porównania używana jako argument do sortowania liczb całkowitych od największej do najmniejszej. IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int= Left > Right

* Posortuj tablicę liczb całkowitych, która zawiera powtarzające się wartości.

        Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
        Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
Copy full snippet

Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3} Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

* Posortuj klasę według jednego z jej pól.

        # Przykładowa klasa do testowania sortowania.
        player_stats := class<unique>:
            Wins:int = 0
            RoundsPlayed:int = 0

        # Funkcja porównania używana jako argument do sortowania liczby wygranych od najmniejszej do największej.
        IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
            Left.Wins < Right.Wins
            Lewa strona

        # Funkcja pomocnicza do konwersji wartości porównania statystyk gracza na ciąg tekstowy.
        PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
            var ConvertedToString:string = "["

            for (Index -> Element : Array):
                set ConvertedToString += "{Element.Wins}"
                if (Index < Array.Length - 1):
                    set ConvertedToString += ", "
            set ConvertedToString += "]"
Copy full snippet

# Przykładowa klasa do testowania sortowania. player_stats := class<unique>: Wins:int = 0 RoundsPlayed:int = 0 # Funkcja porównania używana jako argument do sortowania liczby wygranych od najmniejszej do największej. IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats= Left.Wins < Right.Wins Lewa strona # Funkcja pomocnicza do konwersji wartości porównania statystyk gracza na ciąg tekstowy. PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element.Wins}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]"

Kompletny skrypt

    # Ten plik zawiera testy sprawdzające, czy algorytm sortowania zachowuje się zgodnie z oczekiwaniami.
    # Testy obejmują również profilowanie kodu w celu sprawdzenia wydajności algorytmu.

    using { /Fortnite.com/Devices }
    using { /UnrealEngine.com/Temporary/Diagnostics }
    using { /Verse.org/Simulation }
    using { /Verse.org/Random }

    my_log_channel<public> := class(log_channel):

    # "Rejestrator" na poziomie projektu, w którym rejestrowane będą komunikaty z funkcji, które nie należą do klasy dziennika.
    # Funkcja Print, która nie jest funkcją Logger, to <no_rollback>, więc nie można jej użyć w funkcji <transacts>.
    ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
        Logger := log{Channel := my_log_channel}
        Logger.Print(Message, ?Level := Level)

    # Urządzenie trybu kreatywnego utworzone w Verse, które można umieścić w poziomie.
    # Umieść w poziomie, aby uruchamiać testy i profilować kod.
    test_sorting := class(creative_device):

        # Działa po uruchomieniu urządzenia w aktywnej grze
        OnBegin<override>()<suspends>:void= 

            # Przykładowe tablice do wykorzystania w teście.
            var ArrayLength:int = GetRandomInt(10, 100)

            Test1ExpectedIntArray:[]int =
                for (Count := 0..ArrayLength):
                	Licznik

            Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)

            Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
                ArrayLength - Count

            Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)

            Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}

            Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)
            Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
                player_stats:
                    Wins := ArrayLength - Count
                    RoundsPlayed := GetRandomInt(Count, Count * 30)

            Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)

            # Uruchom testy i zgłoś, czy zakończyły się niepowodzeniem czy powodzeniem.
            if:
                RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest["Tablica liczb całkowitych w kolejności od największej do najmniejszej", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
                RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej z powtórzeniami", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest["Tablica statystyk graczy w kolejności od największej liczby zwycięstw do najmniejszej", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
            then:
                ProjectLog("Wszystkie testy zaliczone.")
            else:
                ProjectLog("Co najmniej jeden test nie powiódł się.")

    # Przetestuj funkcję sortowania tablic i profilowania kodu.
    RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=

        # Wykonaj sortowanie przez scalanie i profiluj kod.
        ResultArray := profile(Description):
            SortingAlgorithms.MergeSort(ActualArray, Compare)

        # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów.
        ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}")
        ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}")
        ProjectLog("Wynik: {ArrayToString(ResultArray)}")

        # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected

    # Funkcja pomocnicza do konwersji tablicy liczb całkowitych na ciąg tekstowy.
    IntArrayToString(Array:[]int)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # Funkcja pomocnicza do konwersji wartości porównania statystyk gracza na ciąg tekstowy.
    PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element.Wins}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # Funkcja porównania używana jako argument do sortowania liczb całkowitych od najmniejszej do największej.
    IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
        Left < Right

    # Funkcja porównania używana jako argument do sortowania liczb całkowitych od największej do najmniejszej.
    IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
        Left > Right

    # Przykładowa klasa do testowania sortowania.
    player_stats := class<unique>:
        Wins:int = 0
        RoundsPlayed:int = 0

    # Funkcja porównania używana jako argument do sortowania liczby wygranych od najmniejszej do największej.
    IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins < Right.Wins
        Lewa strona

    # Funkcja porównania używana jako argument do sortowania liczby wygranych od największej do najmniejszej.
    IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins > Right.Wins
        Lewa strona
Copy full snippet

# Ten plik zawiera testy sprawdzające, czy algorytm sortowania zachowuje się zgodnie z oczekiwaniami. # Testy obejmują również profilowanie kodu w celu sprawdzenia wydajności algorytmu. using { /Fortnite.com/Devices } using { /UnrealEngine.com/Temporary/Diagnostics } using { /Verse.org/Simulation } using { /Verse.org/Random } my_log_channel<public> := class(log_channel): # "Rejestrator" na poziomie projektu, w którym rejestrowane będą komunikaty z funkcji, które nie należą do klasy dziennika. # Funkcja Print, która nie jest funkcją Logger, to <no_rollback>, więc nie można jej użyć w funkcji <transacts>. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Urządzenie trybu kreatywnego utworzone w Verse, które można umieścić w poziomie. # Umieść w poziomie, aby uruchamiać testy i profilować kod. test_sorting := class(creative_device): # Działa po uruchomieniu urządzenia w aktywnej grze OnBegin<override>()<suspends>:void= # Przykładowe tablice do wykorzystania w teście. var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Licznik Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) set ArrayLength = GetRandomInt(10, 100) Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength): ArrayLength - Count Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray) Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3} Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray) set ArrayLength = GetRandomInt(10, 100) Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength): player_stats: Wins := ArrayLength - Count RoundsPlayed := GetRandomInt(Count, Count * 30) Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats) # Uruchom testy i zgłoś, czy zakończyły się niepowodzeniem czy powodzeniem. if: RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] RunArrayTest["Tablica liczb całkowitych w kolejności od największej do najmniejszej", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString] RunArrayTest["Tablica liczb całkowitych w kolejności od najmniejszej do największej z powtórzeniami", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString] RunArrayTest["Tablica statystyk graczy w kolejności od największej liczby zwycięstw do najmniejszej", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString] then: ProjectLog("Wszystkie testy zaliczone.") else: ProjectLog("Co najmniej jeden test nie powiódł się.") # Przetestuj funkcję sortowania tablic i profilowania kodu. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Wykonaj sortowanie przez scalanie i profiluj kod. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Wyświetl tablice Actual, Expected i Result na potrzeby rozwiązywania problemów. ProjectLog("Rzeczywiste: {ArrayToString(ActualArray)}") ProjectLog("Oczekiwane: {ArrayToString(ExpectedArray)}") ProjectLog("Wynik: {ArrayToString(ResultArray)}") # Sprawdź, czy test zakończył się pomyślnie i posortował tablicę zgodnie z oczekiwaniami. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected # Funkcja pomocnicza do konwersji tablicy liczb całkowitych na ciąg tekstowy. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" # Funkcja pomocnicza do konwersji wartości porównania statystyk gracza na ciąg tekstowy. PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element.Wins}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" # Funkcja porównania używana jako argument do sortowania liczb całkowitych od najmniejszej do największej. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right # Funkcja porównania używana jako argument do sortowania liczb całkowitych od największej do najmniejszej. IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int= Left > Right # Przykładowa klasa do testowania sortowania. player_stats := class<unique>: Wins:int = 0 RoundsPlayed:int = 0 # Funkcja porównania używana jako argument do sortowania liczby wygranych od najmniejszej do największej. IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats= Left.Wins < Right.Wins Lewa strona # Funkcja porównania używana jako argument do sortowania liczby wygranych od największej do najmniejszej. IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats= Left.Wins > Right.Wins Lewa strona

We własnym zakresie

• Zaimplementuj inny algorytm sortowania. Dostępne są następujące implementacje algorytmów:

  • Quick Sort (Szybkie sortowanie)

  • Bubble Sort (Sortowanie bąbelkowe)

• Dodaj więcej przypadków testowych, aby zwiększyć zakres testowania. Czy znasz jakieś skrajne przypadki, których testy obecnie nie obejmują? A co z bardziej złożonymi typami danych?