Universitatea de Stat din Moldova
Facultatea de Fizică şi Inginerie
Departamentul Fizica Aplicată şi
Informatica
Lucrare de laborator nr.6
Tema: Algoritm QuickSort. Sortarea prin inserţie cu pas variabil
Lucrarea a fost elaborată de
Lupu Duimitru, gr. TI221
Lucrarea a fost verificată de
Curlicovschi Alisa, conf. univ.
Chisinau,2024
Ex.1
Scrieti programul care ordoneaza crescator un vector v
cu maximum 50 elemente intregi.
#include <iostream>
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
swap(arr[i + 1], arr[high]);
return i + 1;
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
std::cout << arr[i] << " ";
std::cout << std::endl;
int main() {
int n;
int arr[50];
std::cout << "Introduceți numărul de elemente (maximum 50): ";
std::cin >> n;
if (n <= 0 || n > 50) {
std::cout << "Numărul de elemente trebuie să fie între 1 și 50.";
return 1;
std::cout << "Introduceți " << n << " elemente: ";
for (int i = 0; i < n; i++) {
std::cin >> arr[i];
quickSort(arr, 0, n - 1);
std::cout << "Vectorul sortat este: ";
printArray(arr, n);
return 0;
}
Mersul lucrării:
1. Utilizatorul introduce numărul de elemente și apoi valorile
acestora.
2. Se apelează funcția quickSort pentru a sorta vectorul
introdus.
3. Funcția quickSort sortează recursiv vectorul folosind
algoritmul Quick Sort.
4. Vectorul sortat este afișat pentru utilizator.
Concluzie: Prin urmare, programul simplu citește datele de
intrare, le sortează folosind Quick Sort și afișează rezultatul
sortării. Este un program simplu și eficient pentru sortarea
unui vector de întregi.
Ex.2
Modificati programul astfel incat sa ordoneze elementele
vectorului descrescator.
#include <iostream>
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] > pivot) { // Modificarea cheie: schimbăm '>' cu '<'
++i;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
std::cout << arr[i] << " ";
}
std::cout << std::endl;
}
int main() {
int n;
int arr[50];
std::cout << "Introduceți numărul de elemente (maximum 50): ";
std::cin >> n;
if (n <= 0 || n > 50) {
std::cout << "Numărul de elemente trebuie să fie între 1 și 50.";
return 1;
}
std::cout << "Introduceți " << n << " elemente: ";
for (int i = 0; i < n; ++i) {
std::cin >> arr[i];
}
quickSort(arr, 0, n - 1);
std::cout << "Vectorul sortat descrescător este: ";
printArray(arr, n);
return 0;
}
Mersul lucrării:
1. Utilizatorul introduce numărul de elemente și valorile acestora.
2. Se apelează funcția quickSort pentru a sorta vectorul, făcându-l să fie
ordonat în ordine descrescătoare.
3. Funcția quickSort sortează vectorul în mod recursiv folosind
algoritmul Quick Sort, iar modificarea la funcția partition asigură
sortarea în ordine descrescătoare.
4. Vectorul sortat descrescător este afișat pentru utilizator.
Concluzie: În concluzie, acest program simplu oferă o modalitate
eficientă și ușor de utilizat pentru a sorta un vector de întregi în ordine
descrescătoare, demonstrând beneficiile și eficacitatea algoritmului
Quick Sort.