10 2018 Lectia23

Lectie

Quicksort

Varianta 1 de implementare

#include <iostream>
using namespace std;
int a[100000], n, i;
void quickSort(int a[], int p, int u) {
  int i = p, j = u;
  int aux;
  int pivot = a[( p + u ) / 2];
  while ( i <= j ) {
    while ( a[i] < pivot )        // inaintez cu i pana gasesc un element mai mare sau egal cu pivotul
      i ++;
    while ( a[j] > pivot )        // inaintez cu j pana gasesc un element mai mare sau egal cu pivotul
      j --;
    if ( i <= j ){                // daca elem de pe poz i se afla in stanga celui de pe poz j,
      aux = a[i];                 // interchimb cele doua valori
      a[i] = a[j];
      a[j] = aux;
      i++;                        // mut cei doi pointeri cu o pozitie
      j--;
    }
  }
  // de la p la j au elemente mai mici decat pivotul
  // de la i la u am elemente mai mari decat pivotul
  if ( p < j )
    quickSort( a, p, j );         // sortez [p,j] daca am mai mult de un element
  if ( i < u )
    quickSort( a, i, u );         // sortez [i,u] daca am mai mult de un element
}
 int main() {
  int n, i;
  cin >> n;
  for( i = 1; i <= n; i++ )
    cin >> a[i];
  quickSort( a, 1, n );
  for( i = 1; i <= n; i++ )
    cout<< a[i] <<" ";
  return 0;
}

Varianta 2 de implementare

#include <bits/stdc++.h>

using namespace std;

int a[100001];

int Partition( int a[], int l, int r ){
  int x = a[l];
  int j=l;
  for(int i = l + 1; i <= r; i++ ){
    if(a[i] <=x ){
      j ++;
      swap( a[j], a[i] );
    }
  }
  swap(a[l], a[j]);
  return j;
}

void QuickSort( int a[], int l, int r ){
    if( l >= r ){
      return;
    }
    int m = Partition( a, l, r );      
    QuickSort( a, l, m-1 );
    QuickSort( a, m + 1, r );
}

int main(){
  int l, r, n;
    
  cin >> n;
  for(int i = 1; i <= n; i++ )
    cin >> a[i];
    
  l = 1;
  r = n;
  QuickSort( a, l, r );
  for(int i = 1; i <= n; i++ )
    cout << a[i] <<" ";
    
  return 0;
}

TEMA

usor

• https://www.pbinfo.ro/?pagina=probleme&id=1024 Quicksort
• https://www.pbinfo.ro/?pagina=probleme&id=1264 Statisticiordine
• https://www.pbinfo.ro/?pagina=probleme&id=1156 InaltimiQ
• https://www.pbinfo.ro/?pagina=probleme&id=1157 KSort2

medie

• https://www.pbinfo.ro/?pagina=probleme&id=2525 Cioc