[C++] Insertion sort - problem

Zdravo!

Imam namreč ne problem. V šoli pri programiranju smo začeli z snovjo metode urejanja. Omenili smo tri metode. Bubble sort, Selection sort in Insertion sort. In smo dobili nalogo napisat program ki ti pove čas urejanja, število menjav in število preverjanj števil, pol pa tabelo še naredit,...

No, spodaj sem prilepil kodo ki sem jo do sedaj napisa. Vse dela lepo in prav razen število preverjanj me malo zafrkava. Namreč število preverjanj mi je enako številu izvedbe for zanke. Ne šteje mi pa tudi ko se while zanka izvede (na 1 for zanko se lahko while zanka večkrat izvede).

Zanima me če bi mi lahko kdo pomagal in mi napisal kako bi rešil ta problem.

Hvala!

Lp, golobich ;)

#include <iostream>
#include <time.h>
using namespace std;

int tab[5];
//INSERTION SORT
void uredi (int n) //a = število polj
{
      int j, temp; 
      //int zacasno = 0;
      //int trenutno = 0;
      int st_preverjanj = 0;
      int st_menjav = 0;
      for (int i=0; i<n; i++) 
      {
            j = i;
           // zacasno++;
           st_preverjanj++;
            while ((j>0)&& ((tab[j-1]) > (tab[j])) ) 
            { 
                  //if (zacasno==trenutno)
                  
                  temp = tab[j];
                  tab[j] = tab[j-1];
                  tab[j-1] = temp;
                  j--;
                  st_menjav++;
                 // trenutno = zacasno;
            }
            
      }
      cout <<endl;
      cout<<"Število menjav: "<<st_menjav<<endl;
      cout<<"Število preverjanj: "<<st_preverjanj+zacasno<<endl;
}

void narascajoce (int n)
{
     for (int i=0; i<n; i++)
     {
         tab[i]=i+1;
         cout << tab[i] <<", ";
     }    
}

void padajoce (int n)
{
     int j=n;
     for (int i=0; i<n; i++)
     {
         tab[i]=j;
         cout << tab[i] <<", ";
         j--;
     }
} 

void nakljucno (int n)
{
     srand(time(NULL));
     for (int i=0; i<n; i++)
     {
         tab[i]=rand()%40+1;
         cout <<tab[i] <<", ";
     }
}

int main ()
{
    int n=5;
    char izbira;
    cout << "Kako želite da je tabela napolnjena na zacetku?\n\t 1) Nakljucno\n\t 2) Najprej najmanjsi\n\t 3) Najprej najvecji\n"<<endl;
    cin >> izbira;
    for (int i=1; i>0; i++)
    {
        if (izbira == '1')
        {
             nakljucno(n);
             break;                 
        }
        else if (izbira == '2')
        {
             narascajoce(n);
             break;
        }
        else if (izbira == '3')
        {
             padajoce(n);
             break;
        }
        else
        {
            cout << "Vnesite pravilni znak (1, 2 ali 3)!"<<endl;
        }
    }
    
    clock_t start, finish;
    start = clock();
    
    uredi (n);
    
    finish = clock();
    cout <<"Cas: "<<(double(finish-start)/CLOCKS_PER_SEC)<<endl;
    
    cout<<endl;
    
    for (int i=0; i<n; i++)
    {
        cout << tab[i] <<", ";
    }
    cout << endl;
    
    
    system ("pause");
    return 0;
}

Moreš upoštevat da se while zanka ne izvede vedno. Izvede se samo ko se števili zamenjata. To je pa število menjav. To je pa že v zanki ;)

Ja sej. Do zamenjave pride ko se while zanka izvede. Drugače ne pride do zamenjave.
Ali misliš kako drugače?

Logicni pogoj, ki ga imas v zanki, das v svojo metodo, kjer preveris pogoj in povecas st. preverjanj, ali pa, bolj grdo:

while ((++st_preverjanj) && ((j>0)&& ((tab[j-1]) > (tab[j]))) )

Mej kokr češ, vendar kar ti je povedal genetic, žal ni prav.

Tista while zanka, ki najprej poveča število preverjanj, pade ven pri j==0. In ne gre preverjat neenakosti naprej, čeprav se je povečala vrednost spremenljivke ki šteje preverjanja.

Napaka.

Tko, bo moral zmutit še mau.

V tem primeru pa ne bo povecalo st. primerjanj, ce bo primerjanje (tab[j-1]) > (tab[j]) false

tem primeru pa ne bo povecalo st. primerjanj, ce bo primerjanje (tab[j-1]) > (tab[j]) false

Sej maš povečanje števca TUDI zgoraj.

More nekako mert spodnjo mejo, do kamor tisti j niža. Tole je standardna izvedenka insertion sorta, vsi jo tako pišejo. Vendar tudi meni to ni všeč in se mislim mau poglobit v zadevo.

No, smo vrgli tale insertion sort Critticallu v gobec. Kaj je naredil, si lahko ogledate tule:

http://critticall.com/insertionsort.html