Sortare prin selectie

Sortare prin selectia elementului maxim:

int main()
 {
 int maxi,p,i,n,v[100],j,aux;
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=n;i>=2;i--)
 {
  maxi=v[1];p=1;
  for(j=1;j<=i;j++)
  if(v[j]>maxi)
  {
   maxi=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++)
  cout<<v[i]<<' ';
 return 0;
 }

Sortare prin selectia elementului minim:

int main()
{
 int n,i,mini,p,j,aux,v[100];
 cin>>n;
 for(i=1;i<=n;i++)
  cin>>v[i];
 for(i=1;i<=n-1;i++)
 {
  mini=v[i];
  p=i;
  for(j=i+1;j<=n;j++)
  if (v[j]<mini)
  {
   mini=v[j];
   p=j;
  }
  aux=v[i];
  v[i]=v[p];
  v[p]=aux;
 }
 for(i=1;i<=n;i++) cout<<v[i]<<' ';
 return 0;
}

Interschimbarea termenilor egal departati

Acest set de instrucțiuni ajută în cazul problemelor în care vectorul este ordonat crescător și vrem să îl ordonăm descrescător sau invers.

aux=v[i];
v[i]=v[n+1-i];
v[n+1-i];

Unde indicele n+1-i se deduce din interschimbarea lui v[1] cu v[n],v[2] cu v[n-1]…,iar for-ul se face de la i=1 până la n/2.

Sortere prin interchimbare directa

for(i=1;i<=n-1;i++)
 {
    for(j=i+1;j<=n;j++)
    {
       if(v[i]>v[j])
       {
          aux=v[i];
          v[i]=v[j];
          v[j]=aux;
       }
    }
 }

Sortarea de tip bubble

#include <iostream>
using namespace std;
int main()
{

    int n,i,v[100],ok,aux;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i];
    do
    {
        ok=0;
        for(i=1;i<n;i++)
            if(v[i]>v[i+1])
            {
                aux=v[i];
                v[i]=v[i+1];
                v[i+1]=aux;
                ok=1;
            }
    }
    while(ok==1);
    for(i=1;i<=n;i++)
    cout<<v[i]<<' ';
    return 0;
}

Obs.

1. În cazul în care toate elementele sunt ordonate crescător, algoritmul realizează n-1 comparații și nicio interschimbare.

2. În cazul în care toate elementele sunt ordonate descrescător, algoritmul realizează:

n*(n-1) comparații

((n-1)*n)/2 interschimbări

Permutarea circulară la stânga

Deoarece numararea se face de la 1, v[0] nu va fi nefolosit; astfel, toate elementele vectorului se vor deplasa cu o pozitie spre stanga, iar apoi v[n] va prelua valoarea lui v[0].

In cazul in care numararea se va face incepand cu v[0], vom folosi o variabila auxiliara „aux”, care va prelua valoarea acestuia, se vor deplasa termenii, iar apoi v[n-1] (ultimul element din vector) va prelua la randul lui valoarea lui „aux”.

for(i=1;i<=n;i++)
    {
        v[i-1]=v[i];
        v[n]=v[0]
    }
        SAU
    aux=v[0]
    for(i=1;i<n;i++)
    {
        v[i-1]=v[i];
        v[n-1]=aux;
    }

Metafore informatice

1. x[++k]=y[i++] <=> k++; x[k]=y[i]; i++;
2. x[++k]=y[++i] <=> k++; i++; x[k]=y[i];
3. x[k++]=y[i++] <=> x[k]=y[i]; k++; i++;
4. x[k++]=y[++i] <=> i++; x[k]=y[i]; k++;

 

Deplasarea la stânga

                       i ia valori de la k+1 la n; dupa eliminarea lui v[k] toti ceilalti termeni de dupa el se vor deplasa cu o pozitie spre stanga.

 for(i=k+1;i<=n;i++;)
    {
        v[i-1]=v[i];
        n--;
    }

Perechi de numere neconsecutive

• v[1]  v[2] ……. v[i]  v[i+1]  ……. v[n]

(v[i] , v[j])     j ia valori de la i+1 pana la n;

                        i ia valori de la 1 pana la n-1;

 

• v[1]  v[2]  ……. v[i-1]  v[i] …….v[n]

(v[i] , v[j])    j ia valori de la 2 pana la n;

                       i ia valori de la 1 pana la i-1;

Perechi de numere consecutive

Avem un vector cu urmatoarele elemente:

v[1]  v[2]  v[3]  v[4]  …… v[i-2]  v[i-1]  v[i] ….. v[n];

Perechi de 2 numere consecutive

(v[i-1] , v[i])        i va lua valori de la 2 pana la n;

(v[i] , v[i+1])        i va lua valori de la 1 pana la n-1;

Perechi de 3 numere consecutive

(v[i-2] , v[i-1] , v[i])          i va lua valori de la 3 la n;

(v[i-1] , v[i] , v[i+1])           i va lua valori de la 2 la n-1;

(v[i] , v[i+1] , v[i+2])          i va lua valori de la 1 la n-2;