Merge Sort z Insertion Sort

Hej, próbuję w celach doświadczalnych zrealizować Hybrid Sort na bazie Merge Sort + Insertion Sort. Chcę uruchomić Insertion Sort dla ostatnich 10 elementów w tablicy, niestety algorytm nie działa prawidłowo. Można prosić o pomoc?

void insertionSort(int* table, int start, int end)
{
    int temp, i, j;
    // Zaczynamy pętlę od wartości, która nas interesuje
    // Kończymy ją na ostatniej wartości w tablicy
    for (i = start; i < end; i++)
    {
        temp = table[i];
        for (j = i - 1; j >= 0 && table[j] > temp; j--)
        {
            table[j + 1] = table[j];
        }
        table[j + 1] = temp;
    }
}

void hybridSort(int* table, int H1, int H2)
{
    int H;
    if (H1 < H2)
    {
        H = (H1 + H2) / 2;
        // Jeśli pozostała ilość elementów odjęta od całości 
        // elementów w tablicy <= 10, to wykonaj insertSort
        if (H2 - H1 <= 10)
        {
            insertionSort(table, H1, H2);
        }
        else
        {
            hybridSort(table, H1, H);
            hybridSort(table, H + 1, H2);
        }
        hybrid(table, H1, H2, H);
    }
    return;
}

// int* table, int left, int right, int middle
void hybrid(int* table, int H1, int H2, int H)
{
    int midTable[100005];

    int left, right, middle;
    left = H1;
    middle = H1;
    right = H + 1;

    // Wykonuj się tak długo aż nie skończą się elementy z 1 i 2 tablicy
    while (left <= H && right <= H2)
    {
        // Porównujemy elementy z tablicy[i] (H)
        // I tablicy[j] (H+1)
        if (table[left] < table[right])
        {
            // Jeśli tablica 'left' jest mniejsza od 'right'
            // Wrzucamy wartość do tablicy pomocnicznej 'midTable'
            midTable[middle] = table[left];
            left++;
        }
        else
        {
            // Jeśli tablica 'right' jest mniejsza od 'left'
            // Wrzucamy wartość do tablicy pomocnicznej 'midTable'
            midTable[middle] = table[right];
            right++;
        }
        // Inkrementujemy index tablicy
        middle++;
    }

    while (left <= H)
    {
        // Skopiuj wszystkie pozostałe elementy z lewej tablicy 'left'
        // do tablicy pomocniczej 'midTable'
        midTable[middle] = table[left];
        middle++;
        left++;
    }

    while (right <= H2)
    {
        // Skopiuj wszystkie pozostałe elementy z prawej tablicy 'right'
        // do tablicy pomocniczej 'midTable'
        midTable[middle] = table[right];
        middle++;
        right++;
    }

    // H + 1 żeby sortowanie nie wyskakiwało poza tablicę
    for (left = H1 + 1; left < middle; left++)
    {
        // Wrzuć wszystkie posortowane elementy do oryginalnej tablicy
        table[left] = midTable[left];
    }
}

        else
        {
            hybridSort(table, H1, H);
            hybridSort(table, H + 1, H2);
        }
        hybrid(table, H1, H2, H);

to ostatnie powinno raczej też być w else

enedil napisał(a):

        else
        {
            hybridSort(table, H1, H);
            hybridSort(table, H + 1, H2);
        }
        hybrid(table, H1, H2, H);

to ostatnie powinno raczej też być w else

Dodane, dziękuję. Natomiast problem z działaniem sortowania dalej istnieje

Kolejny błąd:

        for (j = i - 1; j >= 0 && table[j] > temp; j--)

a dokładniej warunek j >= 0 powinien być jednak inny.

Wyjaśnię problem jeszcze raz, teraz powinno być jaśniej. Realizuję Hybrid sort przy użyciu Merge i Insertion sort.

Idea: wywoływana jest procedura Merge Sort, aż do otrzymania
podzbiorów o małej liczebności, a następnie te małe zbiory o rozłącznych wartościach są sortowane jednym z prostych algorytmów
sortowania czyli w tym przypadku Insert Sort, które chociaż mają złożoność obliczeniową rzędu O(n2),
to dla zbiorów o niewielkim rozmiarze działają relatywnie szybko. W moim przypadku sortowanie jest bardzo wolne

Niestety nie jestem pewny, czy dobrze zrealizowałem takie sortowanie. Moja aktualna wersja wygląda następująco:
Wydaje mi się, że problem może robić funkcja insertionSortHybrid do której przekazujemy całą tablicę zamiast fragmentu 10 elementów

void insertionSortHybrid(int* table, int start, int end)
{
    int temp, i, j;
    // Zaczynamy pętlę od wartości, która nas interesuje
    // Kończymy ją na ostatniej wartości w tablicy
    for (i = start; i < end; i++)
    {
        temp = table[i];
        for (j = i - 1; j >= 0 && table[j] > temp; j--)
        {
            table[j + 1] = table[j];
        }
        table[j + 1] = temp;
    }
}

void hybridSort(int* table, int H1, int H2)
{
    int H;
    if (H1 < H2)
    {
        H = (H1 + H2) / 2;
        hybridSort(table, H1, H);
        hybridSort(table, H + 1, H2);
        hybrid(table, H1, H, H2);
    }
    return;
}

// int* table, int left, int middle, int right
void hybrid(int* table, int H1, int H, int H2)
{
    int midTable[100005];

    int i = H1;
    int j = H + 1;
    int k = H1;

    // 1. Jeśli wynik H2 - H1 jest mniejszy lub równy 10 elementom, wykonaj insertionSort
    // 2. Jeśli wynik H2 - H1 nie jest mniejszy lub równy 10 elementom, wykonaj MergeSort
    if (H2 - H1 <= 10)
    {
        insertionSortHybrid(table, H1, H2);
    }
    else
    {
        while (i <= H && j <= H2)
        {
            if (table[i] <= table[j])
            {
                midTable[k] = table[i];
                i++;
            }
            else
            {
                midTable[k] = table[j];
                j++;
            }
            k++;
        }

        while (i <= H)
        {
            midTable[k] = table[i];
            i++;
            k++;
        }

        while (j <= H2)
        {
            midTable[k] = table[j];
            j++;
            k++;
        }

        for (i = H1; i <= H2; i++)
        {
            table[i] = midTable[i];
        }
    }
}```

No bo Twoja implementacja, zamiast O(n log n), jest sumarycznie O(n^3 log n). Zresztą już powiedziałem co nie działa.

enedil napisał(a):

No bo Twoja implementacja, zamiast O(n log n), jest sumarycznie O(n^3). Zresztą już powiedziałem co nie działa.

W takim razie proszę doprecyzuj. Twoja wcześniejsza sugestia na temat warunku j >= 0 kłóci się ze wszystkimi materiałami,
z których się uczyłem.

Twoja implementacja sortowania przez wstawianie sortuje całą tablicę (od indeksu 0 do indeksu end) za każdym razem, zamiast sortować tylko kawałek od start do end.

To co mogę doradzić patrząc powierzchownie na kod, to to, że powinieneś wywalić te wszystkie komentarze, bo przez nie nie da się go czytać.

Kod sam w sobie powinien być zrozumiały, a komentarze to znak, że nie wyraziłeś kodem swoich zamiarów.

struct HStr {
    int H = 0;
    int H1 = 0;
    int H2 = 0;
};

class HybridSort {
public:
    HybridSort(int *table, HStr hstr);
    
    void makeSorting();
         
private:
    int left;
    int middle;
    int right;
    int midTable[100005];
    int *table = nullptr;
    HStr hstr;
    
    void CompareEntireTableForCopyingToTempContainer();
    void CopyElementToTempTable(int *element, int &counter);
    void CopyOtherLeftElementsToTempTable();
    void CopyOtherRightElementsToTempTable();
    void PutAllSortedElementsToOriginTable();
    
};

HybridSort::HybridSort(int *table, HStr hstr) {
    this->hstr = hstr;
    this->table = table;
    left = hstr.H1;
    middle = hstr.H1;
    right = hstr.H1 + 1;
}

void HybridSort::makeSorting() {
    CompareEntireTableForCopyingToTempContainer();
    CopyOtherLeftElementsToTempTable();
    CopyOtherRightElementsToTempTable();
    PutAllSortedElementsToOriginTable();
}

void HybridSort::CompareEntireTableForCopyingToTempContainer() {
    while (left <= hstr.H && right <= hstr.H2) {
        if (table[left] < table[right]) {
            CopyElementToTempTable(&table[left], left);
        }
        else {
            CopyElementToTempTable(&table[right], right);
        }
        middle++;
    }
}

void HybridSort::CopyElementToTempTable(int *element, int &counter) {
    midTable[middle] = *element;
    counter++;
}

void HybridSort::CopyOtherLeftElementsToTempTable() {
    while (left <= hstr.H) {
        midTable[middle] = table[left];
        middle++;
        left++;
    }
}

void HybridSort::CopyOtherRightElementsToTempTable() {
    while (right <= hstr.H2) {
        midTable[middle] = table[right];
        middle++;
        right++;
    }
}

void HybridSort::PutAllSortedElementsToOriginTable() {
    // H + 1 żeby sortowanie nie wyskakiwało poza tablicę
    for (left = hstr.H1 + 1; left < middle; left++) {
        table[left] = midTable[left];
    }
}

Czy nie łatwiej się czyta taki kod? Jest on robiony trochę na szybko i jest tutaj co poprawiać, np. w funkcjach po cichu są np. zwiększane liczniki, coś tam można by było wywalić do bardziej ogólnej metody itp. itd.

Ale zobacz, że warto kod rozdzielać na mniejsze funkcje i klasy, bo wtedy dużo łatwiej znaleźć błąd i też więcej osób będzie chętnych Ci pomóc, jeśli nie będą musieli się wysilać w zrozumieniu jak to działa.

Nie testowałem tego, więc nie wiem czy działa jak bazowy.

Tak będzie, imo, zawsze wolno; jak Robisz sortowanie hybrydowe, to najpierw Skanuj tablicę, a potem Zapuszczaj odpowiednie sortowanie.

Dziękuję za pomoc. Ostatecznie problem leżał wyłącznie w źle zaprojektowanym warunku sprawdzającym ilość elementów w zbiorze. Zadanie rozwiązane i sprawdzone. Hybrid Sort działa jak miał działać :)