Tekshirdi: Bo’riev Yusuf Toshkent 2022 Tezkor saralash (Quick sort) algoritmi Ishdan maqsad

Quick sort funksiyasi
Bu funksiyaning ichida oddiy rekursiya bo’ladi. Birinchi bo’lib massivimizni 0 dan oxirigi elementigacha partition funksiyasini ishlatamiz va u bizga pivot (oxirgi) elementimizning saralangan indeksini qaytaradi. Keyin esa 0 … pivot_index – 1 oraliqini va pivot_index + 1 dan oxirgi elementigacha bo’lgan oraliqdagi elementlarini sort() algoritmiga tashlaymiz… (Rekursiya shartimiz chap indeks o’ng indeksdan kichik bo’lishi kerak).

void quick_sort(int a[], int l, int r){
if (l < r) {
int pIndex = partition(a, l, r);
quick_sort(a, l, pIndex - 1);
quick_sort(a, pIndex + 1, r);
}
}



Masalalar.

1. 
   Quick sort algoritmi orqali massiv elementlarini saralang va unda nechta amal bajarganini ekranga chiqaruvchi dastur tuzing.
   

Dastur kodi:
#include
using namespace std;
int steps = 0;
void my_swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
steps++;
}
int partition(int a[], int l, int r){
int pivot = a[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j] <= pivot){
i++;
my_swap(&a[i], &a[j]);
}
}
my_swap(&a[i+1], &a[r]);
return i+1;
}
void quick_sort(int a[], int l, int r){
if (l < r) {
int pIndex = partition(a, l, r);
quick_sort(a, l, pIndex - 1);
quick_sort(a, pIndex + 1, r);
}
}
void show(int a[], int n){
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
}
int main(){
int a[100];
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
quick_sort(a, 0, n-1);
show(a, n);
cout << "Qadamlar soni: " << steps;
return 0;
}
Dastur natijasi:

2. 
   Ro’yxatda berilgan talabalarni familiyasi va ismi bo’yicha Quick sort algoritmi yordamida saralab beradigan dastur tuzing.
   

Dastur kodi:
#include
#include
using namespace std;
int partition(string a[], int l, int r){
string pivot = a[r];
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j].compare(pivot) <= 0){
i++;
swap(a[i], a[j]);
}
}
swap(a[i+1], a[r]);
return i+1;
}
void quick_sort(string a[], int l, int r){
if (l < r) {
int pIndex = partition(a, l, r);
quick_sort(a, l, pIndex - 1);
quick_sort(a, pIndex + 1, r);
}
}
void show(string a[], int n){
for (int i = 0; i < n; i++) {
cout << i + 1 << ". " << a[i] << endl;
}
}
int main(){
string a[100];
string s;
int n;
cout << "Talabalar soni: ";
cin >> n;
getline(cin, s);
for (int i = 0; i < n; i++) {
getline(cin, s);
a[i] = s;
}
quick_sort(a, 0, n-1);
show(a, n);
return 0;
}
Dastur natijasi:

3. 
   Elementlari o‘sish tartibida joylashgan A sonli massiv va a soni berilgan. a ni A massivga shunday qo‘shingki, tartiblanganlik buzilmasin.
   

Dastur kodi:
#include
using namespace std;

void show(int a[], int n){

for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
}

int main(){

cout << "O'sish tartibida massiv kiriting.\nMassiv uzunligi: ";

int n;
cin >> n;
int a[100];
for (int i = 0; i < n; i++) {
cin >> a[i];
}

cout << "Yangi elementni kiriting: ";

int x;
cin >> x;

for (int i = 0; i < n; i++) {

if (x <= a[i]){
swap(x, a[i]);
}
}
a[n] = x;
show(a, n+1);
return 0;
}
Dastur natijasi:

4. 
   A massivni uzunliklari har xil bo‘lgan n ta so‘z tashkil qiladi. So‘zlarni uzunliklari bo‘yicha kamayish tartibida joylashtiruvchi dastur tuzing.
   

Dastur kodi:
#include
#include
using namespace std;
int partition(string a[], int l, int r){
int pivot = a[r].length();
int i = l - 1;
for (int j = l; j < r; j++) {
if (a[j].length() >= pivot){
i++;
swap(a[i], a[j]);
}
}
swap(a[i+1], a[r]);
return i+1;
}
void quick_sort(string a[], int l, int r){
if (l < r) {
int pIndex = partition(a, l, r);
quick_sort(a, l, pIndex - 1);
quick_sort(a, pIndex + 1, r);
}
}
void show(string a[], int n){
for (int i = 0; i < n; i++) {
cout << i + 1 << ". " << a[i] << endl;
}
}
int main(){
string a[100];
int n;
cout << "So'zlar soni: ";
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
quick_sort(a, 0, n-1);
show(a, n);
return 0;
}

Dastur natijasi:

5. 
   N ta (x_i, y­_i) nuqtalar berilgan. Berilgan nuqtalardan OX o’qiga tushurilgan balandliklari uzunliklari kamayish tartibida (x_i, y­­_i) nuqtalarni chiqaring. (A_N massivda X koordinatalar va B_N massivda Y koordinatalar berilgan).
   

Dastur kodi:
#include
#include
using namespace std;
int partition(int a[], int b[], int l, int r){
int pivot = abs(b[r]);
int i = l - 1;
for (int j = l; j < r; j++) {
if (abs(b[j]) >= pivot){
i++;
swap(a[i], a[j]);
swap(b[i], b[j]);
}
}
swap(a[i+1], a[r]);
swap(b[i+1], b[r]);
return i+1;
}

void quick_sort(int a[], int b[], int l, int r){

if (l < r) {
int pIndex = partition(a, b, l, r);
quick_sort(a, b, l, pIndex - 1);
quick_sort(a, b, pIndex + 1, r);
}
}

int main(){

int a[100], b[100];
int n;
cout << "Nuqtalar soni: ";
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
cin >> b[i];
}
quick_sort(a, b, 0, n-1);
for (int i = 0; i < n; i++) {
printf("(%d, %d)\n", a[i], b[i]);
}

return 0;

}
Dastur natijasi:


Xulosa qilib aytadigan bo’lsak, bu amaliy ishimizda tezkor saralsh (Quick sort) algoritmi bilan to’liq tanishib chiqdik va C++ dasturlash tilida saralashga doir turli xil masalalarni ishlab, ko’nikmaga ega bo’ldik