Jak czytać kod...

Mamy taki kod:

int func(int[] A,int p, int r) {
  int x = A[r];
  int i=p-1;
  for (int j=p; j<r; j++) {
    if (A[j]<=x) {
      i++;
      int tmp = A[i];
      A[i] = A[j];
      A[j] = tmp;
    }
  }
  int tmp = A[i+1];
  A[i+1] = A[r];
  A[r] = tmp;
  return i+1;
}

Umiecie patrząc tylko na ten kod, bez użycia kartki i pamięci ;-) stwierdzić co będzie wynikiem jego działania?

Ja nie do końca...

Najpierw rysuję sobie ten kod w głowie:



W rzeczywistości nie tyle sobie wyobrażam rysunek, co na moment "ślepnę" na pewne fragmenty kodu i staram się je analizować bez zbędnych warunków...

Zaczynam od analizy prostszego przypadku, czyli sytuacji gdy w warunku wewnątrz pętli wynikiem jest FALSE, czyli aktualny element fragmentu tablicy jest większy od ostatniego elementu:


Czyli puki A[j]>x to przechodzimy po kolejnych elementach tablicy...
Aż do momentu gdy aktualnie przetwarzany element jest mniejszy bądź równy ostatniemu elementowi tablicy...


Wtedy przesuwamy się o 1 do przodu po naszym dodatkowym indeksie i, który po tym manewrze zacznie wskazywać na 1 element tablicy, a w razie kolejnych przesunięć będzie wskazywał kolejne elementy... i zamieniamy ten wskazywany element z elementem, aktualnie przetwarzanym....

I tu się gubię ;-)

Niby już wiem co robi kod, ale trudno mi zgadnąć co się stanie z tablicą i co będzie opisywać wynik... [czyli indeks i zwiększony o 1].

Nawet analiza jak się będzie zachowywać tablica jest problemem gdy robi się to w głowie... Bo od biedy można operować powiedzmy tablicą 4, no może 5 elementów... do tego dochodzą 2 indeksy... A trzeba zapamiętać nie tylko wartości tych 6-7 liczb, ale jeszcze pozycję w tablicy...

Pomaga mi dopiero wizualizacja:



I wtedy widzę, że wartość zwrócona z tej funkcji to nic innego jak numer indeksu dzielącego tablicę na 2 części, w pierwsze części tablicy znajdują się elementy mniejsze od ostatniego elementu tablicy, a w drugiej większe bądź równe temu elementowi...

OK, to jest metoda partition wykorzystywana w qucik sort.

A teraz kluczowe pytanie ;-)

Macie pomysły, bądź sztuczki które pozwalają na przeczytanie takiego kodu/algorytmu bez babrania się w kartki i inne takie?

Mówiąc inaczej :-)

Ktoś chętny do podzielenia się swoim sposobem analizy kodu? :-)

Ja próbuję od jakiegoś czasu w wolnych chwilach, gdy nie mam innego pomysłu ;-) pisać sobie narzędzie do wizualizacji kodu [o którym już tu kiedyś pisałem].
Jak na razie efekty jego działania nie porażają ;-)



Docelowo chciałbym żeby wyglądało to mniej więcej tak:




Podobne posty^beta
HashMap - Z klawiaturą wśród struktur danych
Zdradliwa Java i 8 królowych ;-)
HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)
Spectre powinno działać nawet w Java'ie ;-)
Regresja liniowa w Google Docs