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



Download 105,93 Kb.
bet2/2
Sana29.11.2022
Hajmi105,93 Kb.
#874920
1   2
Bog'liq
DSA3

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:


  1. 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:


  1. 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:


  1. 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:





  1. N ta (xi, y­i) nuqtalar berilgan. Berilgan nuqtalardan OX o’qiga tushurilgan balandliklari uzunliklari kamayish tartibida (xi, y­­i) nuqtalarni chiqaring. (AN massivda X koordinatalar va BN 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

Download 105,93 Kb.

Do'stlaringiz bilan baham:
1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish