Juda ham katta sonlar bilan ishlash Reja: Merge sort


Download 106.64 Kb.
bet4/5
Sana18.06.2023
Hajmi106.64 Kb.
#1594785
1   2   3   4   5
Bog'liq
saidbek d

Algoritm g’oyasi katta sonlarni satr ko’rinishida olib uzunligi bo’yicha saralanadi,agar uzinlig teng bo’lsa taqqoslanadi.
Vaqtning murakkabligi: O (k * n log n), bu erda k - eng uzun raqamning uzunligi. Bu yerda sort () funktsiyasi O (n Log n) saralash algoritmidan foydalaniladi.


Berilgan katta sonlarni saralash usuli C++
//C ++ dasturi taqdim etilgan katta raqamlarni saralash uchun
// satr sifatida.
#include
using namespace std;
// agar str1 str2 dan kichik bo'lsa, u haqiqiy qiymatni qaytaradi.
bool raqamlarni_taqqoslash(string satr1, string satr2)
{
// Ikkala qatorning uzunligini hisoblang
int n1 = satr1.length(), n2 = satr2.length();
if (n1 < n2)
return true;
if (n2 < n1)
return false;
// Agar uzunliklar bir xil bo'lsa
for (int i=0; i{
if (satr1[i] < satr2[i])
return true;
if (satr1[i] > satr2[i])
return false;
} return false; }
// Ko'p sonli qatorlarni saralash funktsiyasi
// satrlar shaklida berilgan
void kattasonlarnisaralash(string arr[], int n)
{
sort(arr, arr+n, raqamlarni_taqqoslash);
}
// Boshqaruvchi kodi
int main()
{
int n;
cout<<"nechta son kiritmoqchisiz n=:";
cin>>n;
string sonlar[n];
for(int i=0;i{
cout<cin>>sonlar[i];
}
kattasonlarnisaralash(sonlar, n);
for (int i=0; icout << sonlar[i] <}
Namuna;
Ikkita kamaymaslik tartibda saralangan massiv berilgan. Birinchi massiv elementlari soni n ta, ikkinchi massiv elementlari soni m ta. Ularni birlashtirib shunday n+m ta elementdan iborat massiv hosil qilingki bu massiv yana kamaymaslik tartibda saralangan bo’lsin. Kiruvchi ma’lumotlar: Birinchi qatorda n va m butun sonlari berilgan(1≤n, m≤106) . Ikkinchi qatorda n ta son, birinchi massiv elementlari probel bilan ajratilib berilgan. Ikkinchi qatorda m ta son, ikkinchi massiv elementlari berilgan. Ikkala massivning barcha elementlari modul jihatdan 109 dan oshmaydi. Massivlar kamaymaslik tartibida berilgan. Chiquvchi ma’lumotlar: Bitta qatorga hosil bo’lgan massiv elementlarini bitta probel bilan ajratib chiqaring.
Yechish:
#include
using namespace std;

int main() {


int n, m;
cin >> n >> m;
int* firstArray = new int[n];
int* secondArray = new int[m];
for (int i = 0; i < n; i++) {
cin >> firstArray[i];
}
for (int i = 0; i < m; i++) {
cin >> secondArray[i];
}
int newSize = n + m;
int* mergedArray = new int[newSize];
for (int i = 0; i < n; i++) {
mergedArray[i] = firstArray[i];
}
for (int i = 0; i < m; i++) {
mergedArray[n + i] = secondArray[i];
}
// Kamaymaslik tartibida saralash
for (int i = 0; i < newSize - 1; i++) {
for (int j = 0; j < newSize - i - 1; j++) {
if (mergedArray[j] > mergedArray[j + 1]) {
int temp = mergedArray[j];
mergedArray[j] = mergedArray[j + 1];
mergedArray[j + 1] = temp;
}
}
}
for (int i = 0; i < newSize; i++) {
cout << mergedArray[i] << " ";
}
delete[] firstArray;
delete[] secondArray;
delete[] mergedArray;
return 0;
}

Bu kod foydalanuvchidan birinchi massivning elementlar sonini (n), ikkinchi massivning elementlar sonini (m) va ikki massivni kirish qatorlarini o'qib oladi. Keyin, ikki massivni birlashtirib, yangi bir massiv hosil qiladi va massivni kamaymaslik tartibida saralaydi. Natijani chiqaradi va dinamik xotiralarni tozalaydi.
Topshiriqlar.
1. Butun sonlar bir-biridan ‘:’ orqali ajratilib berilgan. Sizning vazifangiz barcha qatnashgan sonlarni qiymatlari kamaymaslik tartibida saralab chiqarishdan iborat.

Download 106.64 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




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