Problem z algorytmem quicksort

0

Ktoś jest w stanie mi powiedzieć, czemu ten algorytm nie działa? Tablica jest zapełniana liczbami losowymi.```

#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstdio>
 
#define N 100
 
using namespace std;
 
void quicksort(int *arr,int left,int right)
{
    int i=left;
    int j=right;
    int pivot=arr[(left+right)/2];
    cout<<pivot<<endl;
    cout<<endl;
    do{
        while(arr[i]<pivot)
            i++;
        while(arr[j]>pivot)
            j--;
        if(i<=j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }while(i<=j);
    //if( left < j )  quicksort( arr, left, j );
    //if( right > i ) quicksort( arr, i, right );
 
 
}
 
int main()
{
    int left=0; int right=N-1;
    srand(time(NULL));
    int arr[N];
    for(int i=0; i<N; i++)
    {
        arr[i]=rand()%1000000+1;
    }
    quicksort(arr,left,right);
    for(int i=0; i<N; i++)
    {
        cout<<arr[i]<<endl;
    }
    return 0;
}
0

Chodzi mi tak właściwie o samo partycjonowanie, tutaj przykład: screenshot-20201204215622.png

0

Nie wiem jak się testuje C, ale u ciebie na screen to wygląda jak jakiś wydruk

Powinieneś przetestować od najprostszych przypadków
Działa? Zielony OK. Nie działa? Czerwony, to debugger i lecisz krok po kroku. Zacznij od partycji

https://en.wikipedia.org/wiki/Unit_testing
Some languages without built-in unit-testing support have very good unit testing libraries/frameworks. Those languages include:
C++
C#

Zobacz co to takiego i czy nie warto testować na początek: [],[1], [1,2],[2,1],[1,2,3],[3,2,1],[3,1,2] itd

0

@BraVolt: Kod się kompiluje i o dziwo sortowanie nawet przebiega prawidłowo, ale samo partycjonowanie nie, co jest nielogiczne, bo wynik jest dobry

0

@Kuba Wandelt:

Zatem przetestuj samo tworzenie partycji dla tablic jedno, 2, 3 elementowych (posortowanych, nieposortowanych) itd

Spróbuj znaleźć błąd samemu z użyciem prostych testów.

PS
https://www.geeksforgeeks.org/quick-sort/

0

@BraVolt: Kolejnym problemem jest to, że to partycjonowanie raz działa, raz nie

@Kuba Wandelt: I nie widzę tam żadnych zalezności

0

Prosty QuickSort
W C nie piszę ale z tego co pamiętam składnię C z pierwszego roku to powinieneś dać sobie radę z kodem Kava

package pl.bv.p58;

public abstract class QuickSort {

    public static void sort(Integer[] arr) {

        recQuickSort(arr, 0, arr.length);
    }

    private static void recQuickSort(Integer[] arr, int left, int right) {

        if (right - left < 2) {
            return;
        }

        int pivot = makePartitions(arr, left, right);

        recQuickSort(arr, left, pivot);
        recQuickSort(arr, pivot + 1, right);
    }

    private static int makePartitions(Integer[] arr, int left, int right) {

        int pivot = left;

        for (int i = pivot + 1; i < right; i++) {
            if (arr[i] <= arr[left]) {
                swap(arr, ++pivot, i);
            }
        }

        swap(arr, pivot, left);

        return pivot;
    }

    private static void swap(Integer[] arr, int a, int b) {

        int temp = arr[b];
        arr[b] = arr[a];
        arr[a] = temp;
    }
}

partycjonowanie to jedna pętla ze swap

int makePartitions(Integer[] arr, int left, int right) {

        int pivot = left;

        for (int i = pivot + 1; i < right; i++) {
            if (arr[i] <= arr[left]) {
                swap(arr, ++pivot, i);
            }
        }

        swap(arr, pivot, left);

        return pivot;
  }

zwraca index-pivot w tablicy
a cały quicksort to

  recQuickSort(arr, left, pivot);
  recQuickSort(arr, pivot + 1, right);

z wcześniejszym sprawdzeniem rozmiaru tablicy (tablica jednoelementowa jest z definicji - na logikę - posortowana)

0

@Kuba Wandelt: Na pewno "problemem" jest to, jak traktujesz pivot. Po partycjonowaniu na danym poziomie nie ląduje on pomiędzy mniejszymi a większymi tylko "gdzieś".
Przykład na podstawie screenu:
arr = {1, 10, 2, 4, 5, 6, 7 };

  • Wywołujesz quicksort(arr, 0, 6).
  • Zostaje wybrany pivot: 4
  • Wskaźnik i mija 1 (jako mniejsze od 4) i trafia na 10,
  • Wskaźnik j mija 7,6,5 (jako większe od 4) i trafia na 4.
  • Zamiana miejscami 10 i 4 -> arr == {1, 4, 2, 10, 5, 6, 7}.
  • W tym miejscu i wskazuje za 4: 2, j wskazuje przed 10: 2 -> i == j i koniec pętli partycjonowania. Następnie sortujesz 2 podtablice: {1, 4, 2} i { 10, 5, 6, 7}.
  • Powyższe podtablice nadal spełniają niezmiennik: wszystkie elementy w lewej podtablicy są mniejsze bądź równe pivotowi, natomiast wszystkie elementy prawej podtablicy są większe.
    Wygląda na to, że Twoja implementacja bazuje na tym niezmienniku, dzięki czemu sam wynik jest poprawny. Wygląda na to, że taki pivot i elementy mniejsze bądź równe zawsze trafią do lewej podtablicy (po zatrzymaniu indeksów i oraz j. Wynikowa tablica będzie posortowana.
1

Jeżeli tablica jest losowa, a pivot raz działa, raz nie działa, to wypisuj tablice źródłową (nieposortowaną) i zapamiętaj ją dla przypadków, w których nie działa. Potem użyj tych konkretnych zapełnień tablicy do testowania i szukania przyczyny niedziałania pivot w tych przypadkach.

1 użytkowników online, w tym zalogowanych: 0, gości: 1