Matematika-informatika fakulteti

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI


FARG’ONA DAVLAT UNIVERSITETI
MATEMATIKA-INFORMATIKA FAKULTETI
AMALIY MATEMATIKA YO‘NALISHI
20.07- guruh talabasi
Nozimaxon Ne’matovaning
”Algoritmlar va berilganlar strukturasi” fanidan
”Hisoblash algoritmi” mavzusiga oid
yozgan


MUSTAQIL ISHI
Qabul qilib oluvchi:
“Amaliy matematika”
kafedrasi katta o’qitvchisi: Sh. Farmonov
Counting sorting (Hisoblash algoritmi).
Hisoblash algoritmi - bu ma'lum bir diapazon orasidagi kalitlarga asoslangan saralash usuli. U aniq asosiy qiymatlarga ega bo'lgan ob'ektlar sonini hisoblash orqali ishlaydi (xeshlash turi). Keyin har bir ob'ektning chiqish ketma-ketligidagi o'rnini hisoblash uchun biroz arifmetik bajaring.
Hisoblash turlarining xususiyatlari:
• Saralash sanash ma'lumotlar haqida taxminlar qiladi, masalan, qiymatlar 0 dan 10 gacha yoki 10 - 99 va hokazo oralig'ida bo'lishini taxmin qiladi, saralashning boshqa ba'zi taxminlari kiritilgan ma'lumotlarning barchasi haqiqiy raqamlar bo'ladi.
• Boshqa algoritmlar singari, bu tartiblash algoritmi taqqoslashga asoslangan algoritm emas, u vaqtinchalik hisoblash massividagi qiymatni xeshlaydi va ularni saralash uchun ishlatadi.
• U vaqtinchalik massivdan foydalanadi, bu uni In Place algoritmiga aylantiradi.
Keling, buni misol yordamida tushunamiz.
• Oddiylik uchun 0 dan 9 gacha bo'lgan ma'lumotlarni ko'rib chiqamiz.
• Kirish maʼlumotlari: {1, 4, 1, 2, 7, 5, 2}
• Har bir noyob obyektning sonini saqlash uchun hisoblash massivini olamiz.



• Endi, har bir noyob elementning sonini count massivida saqlaymiz.
• Agar biron bir element takrorlansa, shunchaki uning sonini oshiramiz.

•Bu erda count massividagi har bir noyob elementning soni quyida ko'rsatilgan:
•Indeks: 0 1 2 3 4 5 6 7 8 9
•Hisob: 0 2 2 0 1 1 0 1 0 0

•Har bir indeksdagi har bir element oldingi hisoblar yig‘indisini saqlaydigan qilib hisoblash massivini o‘zgartiring.
•Indeks: 0 1 2 3 4 5 6 7 8 9
•Hisob: 0 2 4 4 5 6 6 7 7 7
•O'zgartirilgan hisoblash massivi har bir ob'ektning chiqish ketma-ketligidagi o'rnini ko'rsatadi.
•Asl massivning har bir elementi indeksini count massividan topamiz. Bu yig’indidagi hisobni beradi.


•Masivni soat yoʻnalishi boʻyicha bir marta aylantiramiz.
•Indeks: 0 1 2 3 4 5 6 7 8 9
•Hisob: 0 0 2 4 4 5 6 6 7 7

• Har bir ob'ektni kiritish ketma-ketligidan chiqarib, uning sonini 1 ga oshiring.
• Kiritilgan ma'lumotlarni qayta ishlash: 1, 4, 1, 2, 7, 5, 2. 1 ning pozitsiyasi 0.
• Chiqishda 1-ma'lumotni 0 indeksiga qo'ying. Keyingi 1 ma'lumotni ushbu indeksdan 1 kattaroq indeksga joylashtirish uchun sonni 1 ga oshiring.

•Har bir elementni o‘z joyiga qo‘ygandan so‘ng, ularning sonini bittaga kamaytiring.
Quyida hisoblash algoritmi amalga oshirish keltirilgan.
C++

#include #include using namespace std; #define RANGE 255 void countSort(char arr[]) { char output[strlen(arr)]; int count[RANGE + 1], i; memset(count, 0, sizeof(count)); for (i = 0; arr[i]; ++i) ++count[arr[i]]; for (i = 1; i <= RANGE; ++i) count[i] += count[i - 1]; for (i = 0; arr[i]; ++i) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } /* For Stable algorithm for (i = sizeof(arr)-1; i>=0; --i) { output[count[arr[i]]-1] = arr[i]; --count[arr[i]]; } For Logic : See implementation */ for (i = 0; arr[i]; ++i) arr[i] = output[i]; } int main() { char arr[] = "geeksforgeeks"; countSort(arr); cout << "Sorted character array is " << arr; return 0; }

Python3

# Python program for counting sort def countSort(arr): output = [0 for i in range(len(arr))] count = [0 for i in range(256)] ans = ["" for _ in arr] for i in arr: count[ord(i)] += 1 for i in range(256): count[i] += count[i-1] for i in range(len(arr)): output[count[ord(arr[i])]-1] = arr[i] count[ord(arr[i])] -= 1 for i in range(len(arr)): ans[i] = output[i] return ans arr = "geeksforgeeks" ans = countSort(arr) print("Sorted character array is % s" %("".join(ans)))

C#

using System; class GFG { static void countsort(char[] arr) { int n = arr.Length; char[] output = new char[n]; int[] count = new int[256]; for (int i = 0; i < 256; ++i) count[i] = 0; for (int i = 0; i < n; ++i) ++count[arr[i]]; for (int i = 1; i <= 255; ++i) count[i] += count[i - 1]; for (int i = n - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; --count[arr[i]]; } for (int i = 0; i < n; ++i) arr[i] = output[i]; } public static void Main() { char[] arr = { 'g', 'e', 'e', 'k', 's', 'f', 'o', 'r', 'g', 'e', 'e', 'k', 's' }; countsort(arr); Console.Write("Sorted character array is "); for (int i = 0; i < arr.Length; ++i) Console.Write(arr[i]); } }

Oldingi hisoblash tartibidagi muammo shundaki, agar bizda manfiy raqamlar bo'lsa, biz elementlarni saralay olmaymiz. Chunki manfiy massiv indekslari mavjud emas. Shunday qilib, biz minimal elementni topamiz va biz ushbu minimal elementning sonini nol indeksida saqlaymiz.
C++

// Counting sort which takes negative numbers as well #include #include #include using namespace std; void countSort(vector& arr) { int max = *max_element(arr.begin(), arr.end()); int min = *min_element(arr.begin(), arr.end()); int range = max - min + 1; vector count(range), output(arr.size()); for (int i = 0; i < arr.size(); i++) count[arr[i] - min]++; for (int i = 1; i < count.size(); i++) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < arr.size(); i++) arr[i] = output[i]; } void printArray(vector& arr) { for (int i = 0; i < arr.size(); i++) cout << arr[i] << " "; cout << "\n"; } int main() { vector arr = { -5, -10, 0, -3, 8, 5, -1, 10 }; countSort(arr); printArray(arr); return 0; }

Python3

def count_sort(arr): max_element = int(max(arr)) min_element = int(min(arr)) range_of_elements = max_element - min_element + 1 count_arr = [0 for _ in range(range_of_elements)] output_arr = [0 for _ in range(len(arr))] for i in range(0, len(arr)): count_arr[arr[i]-min_element] += 1 for i in range(1, len(count_arr)): count_arr[i] += count_arr[i-1] for i in range(len(arr)-1, -1, -1): output_arr[count_arr[arr[i] - min_element] - 1] = arr[i] count_arr[arr[i] - min_element] -= 1 for i in range(0, len(arr)): arr[i] = output_arr[i] return arr arr = [-5, -10, 0, -3, 8, 5, -1, 10] ans = count_sort(arr) print("Sorted character array is " + str(ans))

C#

using System; using System.Collections.Generic; using System.Linq; class GFG { static void countSort(int[] arr) { int max = arr.Max(); int min = arr.Min(); int range = max - min + 1; int []count = new int[range]; int []output = new int[arr.Length]; for (int i = 0; i < arr.Length; i++) { count[arr[i] - min]++; } for (int i = 1; i < count.Length; i++) { count[i] += count[i - 1]; } for (int i = arr.Length - 1; i >= 0; i--) { output[count[arr[i] - min] - 1] = arr[i]; count[arr[i] - min]--; } for (int i = 0; i < arr.Length; i++) { arr[i] = output[i]; } } static void printArray(int[] arr) { for (int i = 0; i < arr.Length; i++) { Console.Write(arr[i] + " "); } Console.WriteLine(""); } public static void Main(string[] args) { int[] arr = { -5, -10, 0, -3, 8, 5, -1, 10 }; countSort(arr); printArray(arr); } }

E'tiborga olish kerak bo'lgan fikrlar:
• Kiritilgan ma'lumotlar diapazoni saralanadigan ob'ektlar sonidan sezilarli darajada ko'p bo'lmasa, saralashni hisoblash samarali hisoblanadi. Kirish ketma-ketligi 1 dan 10K gacha bo'lgan va ma'lumotlar 10, 5, 10K, 5K bo'lgan vaziyatni ko'rib chiqing.
•Bu solishtirishga asoslangan saralash emas. Uning ishlash vaqtining murakkabligi O(n) bo'sh joy bilan ma'lumotlar diapazoniga proportsionaldir.
•Saralash hisobi bunga erisha oladi, chunki biz saralayotgan ma'lumotlar haqida taxminlar qilamiz.
•U ko'pincha radix sort kabi boshqa tartiblash algoritmiga quyi tartib sifatida ishlatiladi.
•Hisoblash tartibi O(1) da ma’lumotlar obyektining paydo bo‘lishini hisoblash uchun qisman xeshlashdan foydalanadi.
•Hisoblash tartibini salbiy kiritishlar uchun ham kengaytirish mumkin.
•Hisoblash tartibi barqaror algoritm emas. Ammo ba'zi kod o'zgarishlari bilan uni barqaror qilish mumkin.