Tablice sortowanie przez wstawianie.

Witam. Jestem obecnie na rozdziale z tablicami w książce Alex Allain i mam kolejny problem a raczej taki zwyczajny mętlik w głowie i nie jestem w stanie zrozumieć zaprezentowanego tam przykładowego kodu który sortuje wartości w tablicach przez sortowanie i wstawianie. Niby wiadomo co należy zrobić ale nawet w momencie kiedy zacząłem sobie podstawiać te wartości które są podane w funkcji main do konkretnych funkcji w kodzie to i tak nie jestem w stanie tego pojąć. Czy pomoże mi ktoś wyjaśnić działanie poszczególnych elementów tego kodu w sposób prosty i zrozumiały, analizująca każdą funkcję po kolei ? Ja jestem nawet w stanie jeżeli znajdzie się taka osoba która ma czas żeby umówić się gdzieś zdalnie na sypie czy innym diskordzie umówić się na korepetycje gdyż zależy mi da dokładnym i dobrym zrozumieniu tematu.

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

int znajdzNajmniejszyPozostalyElement (int tablica[], int rozmiar, int indeks);
void zamien (int tablica[], int pierwszy_indeks, int drugi_indeks);

void sortuj (int tablica[], int rozmiar)
{
      for ( int i = 0; i < rozmiar; i++ )
      {
            int indeks = znajdzNajmniejszyPozostalyElement( tablica, rozmiar, i );
            zamien( tablica, i, indeks );
      }
}

int znajdzNajmniejszyPozostalyElement (int tablica[], int rozmiar, int indeks)
{
      int indeks_najmniejszej_wartosci = indeks;
      for (int i = indeks + 1; i < rozmiar; i++)
      {
            if ( tablica[ i ] < tablica[ indeks_najmniejszej_wartosci ] )
            {
                  indeks_najmniejszej_wartosci = i;
            }
      }
      return indeks_najmniejszej_wartosci;
}

void zamien (int tablica[], int pierwszy_indeks, int drugi_indeks)
{
      int tymczas = tablica[ pierwszy_indeks ];
      tablica[ pierwszy_indeks ] = tablica[ drugi_indeks ];
      tablica[ drugi_indeks ] = tymczas;
}

// nieduza funkcja pomocnicza wyswietlajaca tablice przed i po sortowaniu
void wyswietlTablice (int tablica[], int rozmiar)
{
      cout << "{";
      for ( int i = 0; i < rozmiar; i++ )
      {
            // z wzorcem tym bedziesz miec czesto do czynienia - sluzy on
            // do czytelnego formatowania list; kod sprawdza, czy jestesmy
            // juz poza pierwszym elementem i jesli tak, dolacza przecinek
            if ( i != 0 )
            {
                  cout << ", ";
            }
            cout << tablica[ i ];
      }
      cout << "}";
}

int main ()
{
      int tablica[ 10 ];
      srand( time( NULL ) );
      for ( int i = 0; i < 10; i++ )
      {
            // liczby beda latwiejsze do odczytania, gdy beda male
            tablica[ i ] = rand() % 100;
      }
      cout << "Tablica wyjsciowa: ";
      wyswietlTablice( tablica, 10 );
      cout << '\n';

      sortuj( tablica, 10 );
      cout << "Tablica posortowana: ";
      wyswietlTablice( tablica, 10 );
      cout << '\n';
}

Czy rozumiesz jak działa ten algorytm?

@_13th_Dragon: Nie, jedyne co jest dla mnie jasne w tym kodzie to to co dzieje się w mainie i to do momentu do pÓÓÓÓki nie zostają wywołane funkcje których logika działania została napisana wyżej. Tak jak napisałem potrzebował bym żeby ktoś wyjaśnił mi co kolejne funkcje robią krok po korku bo naprawdę chce to zrozumieć ale sam nie potrafię do tego dojść.

Ja nie pytam o funkcje, ja mówię generalnie, załóżmy daje ci do rąk karty do gry, i masz je posortować używając właśnie tego algorytmu.
Poradziłbyś sobie?

@_13th_Dragon: Jeżeli chodzi o samo założenie czyli dostaję od ciebie 3 karty asa, damę i króla i mam to zrobić w sposób w jaki zostało to przestawione w książce to oczywiście wiem że należy najpierw zamienić damę z asem w kolejności a następnie asa z królem. A jeżeli pytasz o powyższy kod/algorytm to po prostu nie rozumiem jego działania i nie ma szans żebym to zrobił.

Dodaj komentarz do każdego wiersza, odnosząc się do "rozdanych kart" załóżmy A,K,Q,J i wklej tu.
Jeszcze dodam ten sam algorytm nie rozbity na funkcje, może będzie łatwiej skojarzyć:

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main ()
{
	const int size=10;
    int tb[size];
	srand( time( NULL ) );
    for(int i=0;i<size;++i) tb[i]=rand()%100;
    cout<<"Tablica wyjsciowa: ";
    for(int i=0;i<size;++i) cout<<(","+!i)<<tb[i];
    cout<<endl;
    for(int minidx,minval,i=0;i<size;++i)
    {
    	minval=tb[minidx=i];
    	for(int k=i+1;k<size;++k) if(minval>tb[k]) minval=tb[minidx=k];
    	tb[minidx]=tb[i];
    	tb[i]=minval;
	}
    cout<<"Tablica posortowana: ";
    for(int i=0;i<size;++i) cout<<(","+!i)<<tb[i];
    cout<<endl;
    return 0;
}

@_13th_Dragon:
#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

int main ()
{
const int size=10;
int tb[size];
srand( time( NULL ) );
for(int i=0;i<size;++i) tb[i]=rand()%100; // Tutaj odbywa się przypisywanie liczb pseudolosowych do odpowiedniego indeksu tabeli tak ?
cout<<"Tablica wyjsciowa: ";
for(int i=0;i<size;++i) cout<<(","+!i)<<tb[i]; // W tej linii chyba po każdej liczbie ma się pojawić przecinek tak to przynajmniej rozumiem.
cout<<endl;
for(int minidx,minval,i=0;i<size;++i) // I od tego momentu nie wiem co się dzieje naprawdę staram się to zrozumieć ale nie wiem bo widzę pojawiają się tu w pętli dwie zmienne
// które potem przypisuje się do indeksu tabeli pewnie w tym momencie bredzę ale aż głowa mnie od tego boli :P
{
minval=tb[minidx=i];
for(int k=i+1;k<size;++k) if(minval>tb[k]) minval=tb[minidx=k];
tb[minidx]=tb[i];
tb[i]=minval;
}
cout<<"Tablica posortowana: ";
for(int i=0;i<size;++i) cout<<(","+!i)<<tb[i];
cout<<endl;
return 0;
}

Formatowanie, zaczynasz od wiersza: ```cpp kończysz wierszem: ``` i tyle
Nie do tego kodu dałeś komentarze, mój kod jest jak na razie zbyt skondensowany jak na ciebie, dodaj komentarze do tego co wkleiłeś wyżej.

@_13th_Dragon:
Dobra więc mam skomentować każdą linie, skopiowałem maina z pierwszego kodu jaki wstawiłem.

#include <cstdlib>
#include <ctime>
#include <iostream>

int main ()
{
      int tablica[ 10 ];   //Więc tu mam tablice o indeksie 10 czyli w przełożeniu na karty powiedział bym że mam talię kart i osoba tasująca karty ma mi dać ich 10.
      srand( time( NULL ) );  // Tutaj mam generator liczb pseudolosowych więc  można powiedzieć że osoba zaczyna tasować karty.
      for ( int i = 0; i < 10; i++ ) // Pętla która która wykonywać będzie się dopóki i jest mniejsze od 10 więc tu zaczyna się rozdawanie kart i ma się ono odbywać do momentu aż będę miał 10kart
      {
            // liczby beda latwiejsze do odczytania, gdy beda male
            tablica[ i ] = rand() % 100; // Tu mamy tablicę która do każdej szufladki ma przypisać wylosowaną wartość więc każdą kartę układam na planszy do gry w odpowiedniej kolejności.
      }
      cout << "Tablica wyjsciowa: ";
      wyswietlTablice( tablica, 10 ); //Tu wyświetla się nieposortowana tablica czyli na polach od 0 do 9 mam nieposortowane karty.
      cout << '\n'; 

      sortuj( tablica, 10 ); //A tu są funkcje których jak rozumiem miałem nie poruszać.
      cout << "Tablica posortowana: ";
      wyswietlTablice( tablica, 10 );
      cout << '\n';
}

#include <cstdlib>
#include <ctime>
#include <iostream>

int main ()
{
      int tablica[ 10 ];   // Raczej tyle ci się zmieści na na planszy do gry.
      srand( time( NULL ) );  // To nie sam generator, lecz tylko jego inicjalizacja.
      for ( int i = 0; i < 10; i++ ) // Powiedziałby że tu wskazujesz palcem `i` gdzie dealer ma położyć kolejną kartę na płansze
      {
            tablica[ i ] = rand() % 100; // Właśnie tu rozdający wybiera kartę i wkłada do wskazanego palcem miejśca
      }
      cout << "Tablica wyjsciowa: ";
      wyswietlTablice( tablica, 10 ); //Tu wyświetla się zawartość planszy tak jak jest, czyli nieposortowana
      cout << '\n'; 

      sortuj( tablica, 10 ); //Tu wywoływana jest funkcja sortująca która też miałeś skomentować.
      cout << "Tablica posortowana: ";
      wyswietlTablice( tablica, 10 ); //Tu wyświetla się zawartość planszy tak jak jest, czyli już posortowana
      cout << '\n';
}

@_13th_Dragon:
Okej więc tu jest ta funkcja sortująca.

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

void sortuj (int tablica[], int rozmiar)  // Ta funkcja przyjmuje dwa argumenty tablicę i liczbę całkowitą o nazwie rozmiar. Więc mam tu planszę do gry na której zmieści mi się dana ilość kart i parametr którego nie umiem określić.
{
      for ( int i = 0; i < rozmiar; i++ ) // To tu analogicznie do tego co napisałeś wyżej mam wskazać jak dealer ma posortować karty ?
      {
            int indeks = znajdzNajmniejszyPozostalyElement( tablica, rozmiar, i ); // A tu nie mam pojęcia co odbywa bo z zmienna indeks przyjmuje wartość znajdzNajmniejszyPozostalyElement 
            (tablica, rozmiar, i ) ale jak to ma się w przełożeniu na karty to nie mam zielonego pojęcia.
            zamien( tablica, i, indeks );
      }
}

void sortuj (int tablica[], int rozmiar)  // Więc mam tu "planszę do gry" na której zmieści mi się "dana ilość kart", jaki jeszcze parametr tu widzisz?
{
      for ( int i = 0; i < rozmiar; i++ ) // Tak analogicznie, ale nie ma już tu dialera, jedynie wskazujesz palcem kolejne miejsce na plansze
      {
            int indeks = znajdzNajmniejszyPozostalyElement( tablica, rozmiar, i ); // Wywoływana funkcja która ma za zadanie jak w nazwie, oprócz planszy i rozmiaru dostaje jako parametr miejsce gdzie trzymam palec, zwraca `indeks` - jak wynika z nazwy funkcji ma to być indeks najmniejszej karty od "palca" do końca
            zamien( tablica, i, indeks ); // Tu też musisz dać komentarz.
      }
}

@_13th_Dragon:

#include <cstdlib>
#include <ctime>
#include <iostream>
using namespace std;

void sortuj (int tablica[], int rozmiar)  // Wybacz nie zauważyłem że wartość dla int rozmiar została zadeklarowana w mainie i też nie pomyślałem o tym że "rozmiar" oznacza daną ilość kart.
{
      for ( int i = 0; i < rozmiar; i++ ) // Ok pokazuję palcem miejsca na planszy.
            int indeks = znajdzNajmniejszyPozostalyElement( tablica, rozmiar, i ); // Więc mam to rozumieć tak że int idneks wywołuję funkcję znajdzNajmniejszyPozostalyElement( tablica, rozmiar, 
            i ) czyli załóżmy karty mam na polach ustawione następująco as,jop,król,dama czyli "palec" wskazuje jopa ?
            zamien( tablica, i, indeks );// a tu powiedział bym że wywoływana jest funkcja zamień która ma za zadanie hymmm na planszy tak jak napisałem wyżej palec wskazuje jopa a 
            następnie przesuwam go na sam koniec do damy i zamieniam miejscami damę z królem tylko nie wiem jak by potem miała nastąpić zamiana asa z resztą kart tak by wylądował na 
            ostatnim polu.
      }
}

void sortuj (int tablica[], int rozmiar)oznacza daną ilość kart.
{
      for ( int i = 0; i < rozmiar; i++ ) // Ok pokazuję palcem miejsca na planszy.
            int indeks = znajdzNajmniejszyPozostalyElement( tablica, rozmiar, i ); // wywołujesz funkcję znajdzNajmniejszyPozostalyElement() przekazując planszę oraz ilość kart, funkcja zwraca pozycję najmniejszej karty (szukając od palca w prawo) - indeks to inny palec którym ustawiamy na to co zwróci funkcja.
            zamien( tablica, i, indeks );// Tu wywołujemy funkcję zamien() przekazując planszę oraz pozycji dwóch palców (pozycja bieżącą oraz  najmniejsza po bierzącej)
      }
}

@_13th_Dragon:

Okej teraz chciałbym przejść do funkcji zamień.

#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

void zamien (int tablica[], int pierwszy_indeks, int drugi_indeks)  // Więc powiedział bym że ta funkcja jako swoje argumenty przyjmuje wielkość planszy oraz dwa palce które które wskazują 
                                                                                                      // położenie dwóch kart znajdujących się na tej planszy
{
      int tymczas = tablica[ pierwszy_indeks ]; // tu jest zmienna int tymczas która przyjmuje wartość pierwszego indeksu tablicy. To w przełożeniu na karty powiedział bym że w tym momencie 
                                                                      // wskazuje tą pierwszą najmniejszą napotkaną wartość tak ?
      tablica[ pierwszy_indeks ] = tablica[ drugi_indeks ]; // Tu powiedział bym że trzymam palce na dwóch polach jeden na pierwszej najmniejszej wartości a drugi na następnej najmniejsze 
                                                                                        //napotkanej wartości od pierwszego palca
      tablica[ drugi_indeks ] = tymczas; // A tutaj zamieniam miejscami obie karty które wskazwałem palcami miejscami ?
}

@Maciejsan: Zupełnie od czapy

void zamien (int tablica[], int pierwszy_indeks, int drugi_indeks)  // Jest tu tylko plansza oraz dwa palce które które wskazują ... gdzie tu widzisz rozmiar?
{
      int tymczas = tablica[ pierwszy_indeks ]; // skoro tablica to plansza z kilkoma miejscami na kartę to pojedyncza zmienna to pojedyncze miejsce na kartę
// (np twoja ręka) czyli bierzesz do ręki kartę na którą wskazywał pierwszy palec.
      tablica[ pierwszy_indeks ] = tablica[ drugi_indeks ]; // na miejsce karty na którą wskazywał pierwszy palec wkładasz kartę na którą wskazywał drugi.
      tablica[ drugi_indeks ] = tymczas; // na miejsce karty na którą wskazywał drugi palec wkładasz kartę z twojej ręki do której wziąłeś pierwszą kartę
}

@_13th_Dragon:

To teraz załóżmy że tablica[] czyli plansza do gry przyjmuje określoną wielkość czy powiedzmy będzie to tablica[10] więc na planszy jest 10 miejsc na karę oraz dwa palce które mają wskazywać.
I teraz tak piszesz że " skoro tablica to plansza z kilkoma miejscami na kartę to pojedyncza zmienna to pojedyncze miejsce na kartę (np twoja ręka) czyli bierzesz do ręki kartę na którą wskazywał pierwszy palec". Więc skoro założyłem sobie że plansza do gry ma 10 pół i postanawiam sobie ułożyć na tych 10 polach 10 kart powiedzmy w takiej kolejności as, 10, król, jop , 9, 5, 8, 6, 7, dama to mam rozumieć że pierwszy palec wskazuje asa a drugi palec 10, więc biorę asa do ręki i kładę go na miejsce 10 a dziesiątkę w miejsce asa czyli obecnie plansza do gry wyglądała by następująco ? 10, as , król , jop , 9 , 5 ,8 ,6 , 7 ? Opisuję to w ten sposób bo tak jest mi to najłatwiej przyswoić.

Owszem tak jak opisujesz, tylko że skoro pierwszy wskazuje na 'A' to pozycja drugiego powinna być na '5'

@_13th_Dragon: Aaaaa bo drugi palec pokazuje pierwszą najmniejszą możliwą napotkaną wartość ? Bo jeżeli tak jest to przy następnym kroku pierwszy palec będzie na 10 a drugi na 6 i tak to się będzie powtarzać do momentu całkowitego posortowania.

Czy wg ciebie nazwa znajdzNajmniejszyPozostalyElement to tylko zlepek liter?

@_13th_Dragon: Nie tylko w tej funkcji nie ma tego najdzNajmniejszyPozostalyElement i chciałem właśnie przejść teraz to tej funkcji najdzNajmniejszyPozostalyElement bo wraz z twoimi wskazówkami komentuję sobie poszczególne linie całego kodu który podałem w temacie tak żeby dokładnie wiedzieć co się dzieje krok po kroku. Zdaję sobie sprawę że nie zauważam wielu rzeczy ale jestem na początku nauki a wcześniej styczności z programowaniem nie miałem dlatego też próbuję jakimiś konkretnymi przykładami opisywać kod tak żeby możliwie go najlepiej zrozumieć.

Nie ważnie że nie ma tu, już skomentowałeś funkcję sortuj a tam wyraźnie widać co jest przekazywane jako "drugi palec".

Chyba jednak zgadzam się z @AnyKtokolwiek.

Zauważ że każdy produkt ma jakieś wymagania co do zastosowania, np producent okularów przeciwsłonecznych zakładają że konsument będzie posiadał oczy które ślepi letnie słońce. A co jeżeli konsument nie posiada widzących oczy - czy okulary dla niego będą jakkolwiek przydatne?

Może drugi przykład, producent roweru zakłada że konsument będzie posiadał nogi, a co jeżeli konsument nie posiada nóg (np miał wypadek) - czy rower mu na coś się przyda?

Alex Allain, zakłada że czytelnik zrozumie podany przykład ... jak rozumiesz z poprzednich przykładów to możesz użyć tej książki np jako podstawkę albo przycisk dla papierów aby przeciąg je nie zdmuchnął. W każdym razie wg oryginalnego przeznaczenia nie dasz rady ją wykorzystać.

@_13th_Dragon:

Dobra została ostania funkcja.

int znajdzNajmniejszyPozostalyElement (int tablica[], int rozmiar, int indeks) // Jest tu plansza do gry , dana ilość kart i palec wskazujący dane miejsce.
{
      int indeks_najmniejszej_wartosci = indeks; // Tu na miejsce które wskazuje palec wkładam kartę o najmniejszej wartości ?
      for (int i = indeks + 1; i < rozmiar; i++) // Nie umiem sobie wytłumaczyć działania tej pętli.
      {
            if ( tablica[ i ] < tablica[ indeks_najmniejszej_wartosci ] ) // Mamy tu plansze do gry i jeżeli ... no właśnie nie wiem.
            {
                  indeks_najmniejszej_wartosci = i; // Tu palec wskazuje kartę o najmniejszej wartości
            }
      }
      return indeks_najmniejszej_wartosci;
}

Maciejsan napisał(a):

      int indeks_najmniejszej_wartosci = indeks; // Tu na miejsce które wskazuje palec wkładam kartę o najmniejszej wartości ?

Maciejsan napisał(a):

                  indeks_najmniejszej_wartosci = i; // Tu palec wskazuje kartę o najmniejszej wartości

Popatrz jeszcze raz na te dwa wiersze i swoje komentarze do nich

@_13th_Dragon:

W funkcji sortuj dodałeś taki komentarz "wywołujesz funkcję znajdzNajmniejszyPozostalyElement() przekazując planszę oraz ilość kart, funkcja zwraca pozycję najmniejszej karty (szukając od palca w prawo) - indeks to inny palec którym ustawiamy na to co zwróci funkcja"

indeks_najmniejszej_wartosci = i; // Rozumiem to tak że ta karta o najmniejszej wartości która ma się znaleźć w odpowiednim miejscu na planszy.

int indeks_najmniejszej_wartosci = indeks; // Napisałeś że indeks to inny palec który ustawiamy na to co zwróci funkcja. To wydaje mi się że że w tym miejscu palec jest ustawiany na właśnie tej karcie o najmniejszej wartości.

Aż głowa mnie od tego boli bo naprawdę staram się to zrozumieć.

Czy rozumiesz że przedmioty się nie transformują? Jakim cudem ci karta z palca się zrobiła?
W ten sposób świecznikiem po głowie można zarobić :D

@_13th_Dragon:
Hah teraz to już jest trochę śmiech przez łzy. Więc oświecisz mnie jak to ma wyglądać ?

Nie ma sensu, tu akurat wszystkie instrukcje podobne do tego co już było, czyli już komentowałeś a ja poprawiałem.
Skoro to nic nie dało to po kiego ciągnąć dalej?

@_13th_Dragon: Mhm dobrze to dziękuję za pomoc i wyjaśnienia jakich mi udzieliłeś :P Pozdrawiam.