Qucik sort - poprawność algorytmu

0

http://www.algorytm.edu.pl/algorytmy-maturalne/quick-sort.html algorytm z tej strony:
//www.algorytm.edu.pl

#include<iostream>
using namespace std;

void quick_sort(int *tab, int lewy, int prawy)
{
    if(prawy <= lewy) return;

    int i = lewy - 1, j = prawy + 1, 
    pivot = tab[(lewy+prawy)/2]; //wybieramy punkt odniesienia

    while(1)
    {
        //szukam elementu wiekszego lub rownego piwot stojacego
        //po prawej stronie wartosci pivot
        while(pivot>tab[++i]);

        //szukam elementu mniejszego lub rownego pivot stojacego
        //po lewej stronie wartosci pivot
        while(pivot<tab[--j]);

        //jesli liczniki sie nie minely to zamień elementy ze soba
        //stojace po niewlasciwej stronie elementu pivot
        if( i <= j)
            //funkcja swap zamienia wartosciami tab[i] z tab[j]
            swap(tab[i],tab[j]);
        else
            break;
    }

    if(j > lewy)
    quick_sort(tab, lewy, j);
    if(i < prawy)
    quick_sort(tab, i, prawy);
}
int main()
{
    int *tab, n;

    //cout<<"Ile liczb będziesz chciał posortować? ";
    cin>>n;
    tab = new int [n]; //przydzielenie pamięci na elementy tablicy
    //wczytanie liczb
    for(int i=0;i<n;i++)
        cin>>tab[i];

    quick_sort(tab,0, n-1);

    //wypisanie posortowanych elementów
    for(int i=0;i<n;i++)
          cout<<tab[i]<<" ";

    cin.ignore();
    cin.get();
    return 0;
}

Czy on jest prawidłowy? Nie widzę warunku, który przerwie pętle inkrementacji/dekrementacji tablicy w przypadku, gdy warunek z pivotem nie zostanie spełniony.

1

Ile czasu zajmie napisanie kawałku kodu który dla każdej permutacji szeregu liczb od 1 do 16 odpali ten algorytm a potem sprawdzi czy posortowane poprawnie?

0

Robiłam testy poprawności, ale przecież różnie kompilatory reagują na wyjście poza zakres. Nie pytam, czy na wymyślonym przykładzie zadziała, tylko czy ten kod nie jest obarczony ryzykiem wyjście poza tablicę? Nie widzę tego zabezpieczenia, ale może coś przeoczyłam.

1

@pocasw:

pocasw napisał(a):

Nie pytam, czy na wymyślonym przykładzie zadziała, tylko czy ten kod nie jest obarczony ryzykiem wyjście poza tablicę?

Ogólnie nie testuje się na wymyślonym przykładzie tylko na warunkach brzegowych. Dla sortowania są to m.in.:

  • Liczby posortowane rosnąco
  • Liczny posortowane malejąco
  • Wszystkie liczby równe

BTW @_13th_Dragon nie zasugerował sprawdzania na wymyślonym przykładzie tylko na wszystkich przykładach z zakresu liczb (0-15)

0

Na przykładach działa, nie o to pytam. Ktoś jest mi w stanie wytłumaczyć dlaczego działa, skoro nie ma zabezpieczeń wyjścia poza tablicę (a przynajmniej ja ich nie widzę)? To bezpieczny kod?

0

Chyba, że nie musi być, bo zatrzymie się na pivocie w najgorszym wypadku.

0

Cały QuickSort to funkcja tworząca partycje

pisane na szybko

 void quickSort(int[] arr, int left, int right) {

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

**        int pivotIdx = makePartitions(arr, left, right);**

        recSort(arr, left, pivotIdx);
        recSort(arr, pivotIdx + 1, right);
    }

Przed pogrubieniem: tablica pusta lub o rozmiarze jest już posortowana.
Po pogrubieniu:
sortuj 'quick' rekurencyjnie na lewo od pivot liczby <= arr[pivot]
sortuj 'quick' rekurencyjnie na prawo od pivot liczby > arr[pivot]

W części niepogrubionej nie ma co się skopać. Natomiast makePartitions? To mogą być cuda i złożoność też 'cudowna'. BTW, dawniej to się chyba można było obronić z pracy na ten temat ;)

Co robić, co testować?
Można makePartitions zrobić jako funkcję w dowolny sposób, banalny, byle tylko robiła swoje, nie ważne jak.
Wrzucić taką implementację do quickSort.
Napisać testy. Sprawdzić, że działa:
proste makePartitions
quickSort

Przejść teraz do 'refactor' (red & green już mamy) i zająć się samą funkcją makePartitions.
Później przetestować jak nowsza makePartitions działa z quick sort.

Wiem, armata na wróbla, ale takie rozbijanie problemu pozwala się przy okazji nauczyć jak sobie radzić z czymś bardziej skomplikowanym, jak rozbijać problemy na mniejsze.

PS
Dla sportu sprawdziłem sobie, jakbym napisał QuickSort gdybym musiał 'z palca' napisać.
I jaki sobie sposób partycjonowania wymyślę bez sięgania do Wiki.

Prosta Java, w C nie pisze - sorry, ale chyba da się zrozumieć działanie
void recQuickSort(Integer[] arr, int left, int right) {}
z punktu widzenia kodującego w C

package pl.bv.p58;

public abstract class QuickSort {

    private QuickSort(Integer[] arr) {

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

    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;
        }

        final 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 slider = left;

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

        swap(arr, slider, left);

        return slider;
    }

    private static void swap(Integer[] arr, int slider, int i) {

        int temp = arr[i];
        arr[i] = arr[slider];
        arr[slider] = temp;
    }
}

szybki test (dla porządku, bo wiem, że piszący w C niewiele z tym zrobi)

package pl.bv.p58;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

import static org.junit.Assert.*;
import static org.hamcrest.Matchers.*;

public class QuickSortTest {

    private Integer[] integers;
    private Integer[] sorted;

    @Before
    public void setUp() throws Exception {

        integers = new Integer[]{7, 1, 2, 4, 5, 2, 3, 4, 5, 79, 3, -3, 5, 0, 12, 1, 2, 56, 56, 34, 56};
        sorted = new Integer[integers.length];

        System.arraycopy(integers, 0, sorted, 0, integers.length);
        Arrays.sort(sorted);
    }

    @Test
    public void shoulSortEpmtyArray() {

        final Integer[] arr = new Integer[0];
        QuickSort.sort(arr);
        assertThat(arr.length, is(0));
    }

    @Test
    public void shoulSortOneElementArray() {

        final Integer[] arr = new Integer[]{7};
        QuickSort.sort(arr);
        assertThat(arr.length, is(1));
        assertThat(arr, arrayContaining(7));
    }

    @Test
    public void shouldSortUnsortedArray() {

        QuickSort.sort(integers);
        assertThat(integers, arrayContaining(sorted));
    }

    @Test
    public void shouldSortSortedArray() {

        Arrays.sort(integers);
        QuickSort.sort(integers);
        assertThat(integers, arrayContaining(sorted));
    }

    @Test
    public void shouldSortSameElementsArray() {

        integers = new Integer[]{7, 7, 7, 7, 7, 7, 7, 7, 7};
        sorted = new Integer[]{7, 7, 7, 7, 7, 7, 7, 7, 7};

        QuickSort.sort(integers);
        assertThat(integers, arrayContaining(sorted));
    }

}
0
pocasw napisał(a):

Na przykładach działa, nie o to pytam. Ktoś jest mi w stanie wytłumaczyć dlaczego działa, skoro nie ma zabezpieczeń wyjścia poza tablicę (a przynajmniej ja ich nie widzę)? To bezpieczny kod?

W sumie jak nie przeprowadzisz dowodu poprawności - to nie ma pewności.
Nawet jak dla wszystkich permutacji 1000 różnych liczb nie wyjdzie po za zakres, to i tak nie ma 100% pewności.
Z tym że jak dla wszystkich permutacji dla 16 liczb nie wyjdzie poza zakres to prawdopodobieństwo że będzie problem dla 1000 liczb jest wbrew pozorom bardzo małe.
Tak jak powiedział @KamilAdam przetestuj warunki graniczne, jak nie ma problemów to 99,99% jest git.
Jak chcesz 100% to tylko prawdziwy dowód poprawności da taką gwarancję.

1

Jeżeli szukać błędu, to jest on tutaj:

pivot = tab[(lewy+prawy)/2];

Załóżmy, że mamy tablicę dużą, prawie tak dużą jak zakres int : 2147483647
I wybieramy lewy troszkę mniejszy od 2147483647 i prawy troszkę mniejszy od 2147483647

lewy + prawy wyjdzie poza zakres int
poprawniej byłoby zamiast (lewy + prawy)/2 to lewy + (prawy - lewy)/2

Załóżmy nie int ale byte, od -128 do 127 (mam na myśli coś w rodzaju 'signed byte' )

lewy = 100, prawy = 120
(lewe+prawy)/2 = 220/2 = 110 - niby OK, ale 220 wyszło po drodze poza zakres 128

Natomiast lewy + (prawy - lewy)/2 = 100 + (120 - 100)/2 = 100 + 20/2 = 110 - wynik OK i po drodze nie było wyjścia poza zakres

Inny temat, to sprawdzenie dla jakiej wielkości tablicy na wejściu program jeszcze działa.
Temat: jak to skompilować w C żeby sortować duże tablice?


I jeszcze klasyk, Cormen, dowodzi poprawności QuickSort zakładając z góry poprawne działanie partitions(), samo partitions() dowodzi oddzielnie.

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