Clasa a IX-a lecția 17 - 29 feb 2020

Clasament teme lecțiile 1 - 16

Pe categorii

Divizori / Primalitate / Ciur
Sortari
Matrici
Cautare binara
Stivă
Recursivitate
Generale

Concursuri

Probleme OȘI
Probleme OJI

Lecție

Sortări (partea II)

Recapitulare rapidă

În Lecția 5 am vorbit despre mai multe tipuri de sortări, complexitățile și utilizarea lor:

• Sortarea prin selecție
  • Timp O(N²)
  • Spațiu suplimentar O(1)
• Sortarea prin vectori de frecvență
  • Timp O(N + MAX_VAL)
  • Spațiu suplimentar O(MAX_VAL)
• Sortarea STL
  • Timp O(N * log_N)
  • Spațiu suplimentar O(1)

V-am recomandat ca în condiții de concurs să folosiți sortarea prin vectori de frecvență dacă limitele problemei permite, iar în caz contrar să folosiți funcția sort.

Funcția de comparare

Sortările despre care am vorbit până acum, în complexitate fie O(N²), fie O(N * log_N) fac parte din categoria sortărilor prin comparare. Acestea funcționează comparând elementele între ele două câte două în funcție de un anumit criteriu, sau altfel spus, o metodă / funcție de comparare.

La sortările deja învățațe scrise de noi (sortarea prin selecție), avem control asupra implementării acestora și putem schimba ușor metoda de comparare. În majoritatea cazurilor, este suficient să schimbăm un singur semn: <, <=, >, >=.

Ce se întâmplă în cazul sortării din STL? În mod implicit, funcția sort ne ordonează elementele în ordine crescătoare. Dar putem să îi schimbăm metoda de comparare astfel:

// Returneaza true daca primul argument trebuie sa fie la stanga celui de-al doilea
bool cmp(int a, int b) {
  if (a < b) // Daca primul argument este mai mic decat cel de-al doilea
    return true; // Atunci el trebuie sa fie la stanga
  return false;
}


sort(v, v + n, cmp);

Funcția scrisă mai sus este chiar funcția implicită, pentru că va sorta elementele vectorului în ordine crescătoare. Ce trebuie să facem dacă vrem ca apelul funcției sort să ordoneze elementele descrescător? Schimbăm semnul în >.

Sortare obiecte cu vectori tip permutare

Este posibil să avem nevoie să sortăm și obiecte mai complexe, nu doar numere întregi sau reale. Să luăm următorul exemplu:

Exercițiu Se citește un număr N și apoi N intervale închise, reprezentate prin capătul stânga, respectiv capătul dreapta al acestora. Să se ordoneze aceste intervale crescător după capătul din stânga, iar în caz de egalitate crescător după capătul din dreapta.

Putem reține capetele din stânga ale intervalelor într-un vector X, iar capetele din dreapta într-un vector Y. Avem nevoie să ordonăm cei doi vectori în "paralel". O metodă eficientă pentru a face asta este să ne folosim de un vector auxiliar de dimensiune N, pe care când îl parcurgem de la stânga la dreapta, să parcurgem pozițiile intervalelor în ordinea lor sortată. Altfel spus, vectorul nou creat este o permutare a pozițiilor din cei doi vectori. Exemplu:

• | 0 | 1 | 2 | 3 | 4 | 5 | (P)
• | 5 | 3 | 6 | 3 | 2 | 1 | (X)
• | 6 | 5 | 8 | 4 | 7 | 3 | (Y)

Inițial, vetorul P este permutarea identică, intervalele noastre fiind încă nesortate. În timpul sortării, vom compara elementele prin vectorul P: X[P[i]] cu X[P[j]] și Y[P[i]] cu Y[P[j]], și vom interschimba elementele P[i] și P[j] la nevoie. Altfel spus, în loc să interschimbăm între ele intervalele efective, interschimbăm pozițiile acestora.

Cum scriem acest lucru folosind funcția sort?

bool cmp(int a, int b) { // a si b sunt pozitii, vom compara x[a] cu x[b] si y[a] cu y[b]
  if (x[a] < x[b]) // Daca capatul din stanga este mai mic
    return true; // Intervalul de pe pozitia a trebuie sa fie in stanga celui de pe pozitia b
  if (x[a] > x[b]) // Daca capatul din stanga este mai mare
    return false;
  if (y[a] < y[b]) // Daca capetele din stanga sunt egale si capatul din dreapta este mai mic
    return true;
  return false;
}


for (i = 0; i < n; ++i)
  p[i] = i;
sort(p, p + n, cmp);

Creare tip nou de date (struct)

Pe lângă tipurile de date de bază oferite de limbaj (bool, char, short, int, long long, float, double) ne putem crea o structură de date a noastră. Pentru simplitate, vom folosi exemplul anterior și vom crea o structură de date care să rețină un interval.

#include <stdio.h>

// Structura Interval, contine doi intregi a si b
struct Interval {
  int a, b;
};

int main() {
  Interval itv;
  itv.a = 3;
  itv.b = 5;
  
  printf("Intervalul este: [%d, %d]", itv.a, itv.b);

  return 0;
}

Am creat o structură Interval care conține doi întregi a și b, accesibili prin intermediul operatorului ".". Această structură poate fi folosită în program la fel ca orice alt tip de date cu care suntem deja obișnuiți.

Sortare intervale

Vrem acum să ordonăm intervalele reținute în structura creată, așa cum am făcut și în varianta anterioară.

bool cmp(Interval i1, Interval i2) {
  if (i1.a < i2.a)
    return true;
  if (i1.a > i2.a)
    return false;
  if (i1.b < i2.b)
    return true;
  return false;
}

Interval v[100];
int n;

sort(v, v + n, cmp);

Aplicații

Concurs virtual

Temă

reactivi - infoarena
int - infoarena
z - infoarena