Kompyuter ilmlari va dasturlashtirish
Download 75.97 Kb.
|
3 mustaqil ish D
Paqirni saralash
Massivning har bir elementi M dan biriga joylashtiriladi "chelaklar" 2 1 3 1 2 B Algoritmning asosiy qadamalari quyidagilardan iborat: Har xil darajadagi barcha sonlarni ajratib olish. Bittadan boshlab, har bir darajadagi sonlarni ilgari yurgizish. Har bir darajada, sonlar ro'yxatini tartiblash. Algoritmning eng kattasi, har xil darajadagi raqamlar uchun 10 ta binlik jadvallar (buckets) yaratishdir. Qayd etilgan bo'lsa, ushbu jadvallar joyidan foydalanish orqali, sonlar ularni ichida ajratib olinadi. Bittadan boshlab har bir darajaga qadam qo'shilishi juda muhimdir. Bu qo'shimcha ishga tushirish dasturlashida aksirishni kamaytiradi va algoritmdan sovg'a qilingan vaqt kamayadi. Ishlatilgan toifalarni ro'yhatdan chiqarish uchun Radix sort algoritmi juda samarali, chunki u juda tez ishlaydi va qulaylik bilan ishlatiladi. Ammo u ma'lum bir hajmdagi toifalardan ko'proq elementlarni saralashda juda kuchli emas. Kod qismi: Bu yerda, C# da Windows Form ilovalari uchun Radix sort algoritmini ko'rsatamiz. Algoritm kodini quyidagi shaklda yozamiz: using System; using System.Windows.Forms; namespace RadixSort { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private void btnSort_Click(object sender, EventArgs e) { // Get the input array int[] arr = Array.ConvertAll(txtInput.Text.Split(','), int.Parse); // Find the maximum number to know the number of digits int maxNum = arr[0]; for (int i = 1; i < arr.Length; i++) { if (arr[i] > maxNum) { maxNum = arr[i]; } } // Sort using the Radix Sort algorithm for (int exp = 1; maxNum / exp > 0; exp *= 10) { int[] output = new int[arr.Length]; int[] count = new int[10]; for (int i = 0; i < arr.Length; i++) { count[(arr[i] / exp) % 10]++; } for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = arr.Length - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } for (int i = 0; i < arr.Length; i++) { arr[i] = output[i]; } } // Display the sorted array txtOutput.Text = string.Join(",", arr); } } } Bu kodni Windows Form ilovalarida ishlatish uchun, quyidagi qadamni bajarishimiz kerak: 1. Bir Windows Form ilovasi yaratamiz. 2. Ilovaning formasiga Textboxlar va bir Sort tugmasi qo'shamiz. 3. Sort tugmasini bosganingizda, kod avtomatik ravishda amalga oshiriladi va natijalar Textboxda ko'rsatiladi. Shuni unutmang, bu kod faqatgina int turidagi sonlar uchun ishlaydi, shuningdek sonlarni ',' belgi orqali ajratilgan string ko'rinishida kiritilishi kerak. Mana, C# Windows Forms ilovasida joriy qilingan Radix tartiblash misoli: // Radix sort function which takes an array of integers and sorts them using Radix sort algorithm public static void RadixSort(int[] arr) { // Find the maximum element in the input array int max = arr[0]; foreach (int element in arr) { if (element > max) { max = element; } } // Do counting sort for each digit in the input array for (int exp = 1; max / exp > 0; exp *= 10) { CountingSort(arr, exp); } } // Counting sort function for each digit in the input array public static void CountingSort(int[] arr, int exp) { int n = arr.Length; int[] output = new int[n]; int[] count = new int[10]; // Initialize count array to 0 for (int i = 0; i < 10; i++) { count[i] = 0; } // Store count of occurrences in count[] array for (int i = 0; i < n; i++) { int digit = (arr[i] / exp) % 10; count[digit]++; } // Change count[i] so that count[i] now contains actual // position of this digit in output[] for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } for (int i = n - 1; i >= 0; i--) { int digit = (arr[i] / exp) % 10; output[count[digit] - 1] = arr[i]; count[digit]--; } // Copy the output[] array to arr[], so that arr[] now // contains sorted numbers according to current digit for (int i = 0; i < n; i++) { arr[i] = output[i]; } } Ushbu Radix tartiblash funksiyasidan Windows Forms ilovasida foydalanish uchun uni quyidagi shakldagi tugmani bosish hodisasida chaqirishingiz mumkin: private void buttonSort_Click(object sender, EventArgs e) { // Convert the input string to an integer array int[] arr = textBoxInput.Text.Split(' ').Select(int.Parse).ToArray(); // Call the RadixSort function to sort the array RadixSort(arr); // Convert the sorted array back to a string and display it in the output textbox textBoxOutput.Text = string.Join(" ", arr); } Bu yerda foydalanuvchi kiritish matn maydoniga boʻsh joydan ajratilgan butun sonlar qatorini kiritadi va saralangan natijani chiqish matn maydonida koʻrsatish uchun tartiblash tugmasini bosadi. Xulosa Radix bilan tartiblash - bu raqamlarni raqamlariga qarab tartiblaydigan taqqoslashga asoslangan tartiblash algoritmi. Bu oddiy, samarali va barqaror saralash algoritmi bo'lib, chiziqli vaqt murakkabligiga ega va katta ma'lumotlar to'plamlari uchun ishlatilishi mumkin. Radix tartiblash raqamlarni ularning alohida raqamlari bo'yicha tartiblash g'oyasiga asoslanadi, eng kichik muhim raqamdan boshlab va eng muhim raqamga o'tadi. Ushbu algoritm butun sonlarni, suzuvchi nuqta raqamlarini va satrlarni saralash uchun ishlatilishi mumkin. Umuman olganda, Radix sort – turli ilovalarda ma’lumotlarni saralash uchun foydali algoritmdir.Razryadli saralash (Radix sort) bir tartiblash algoritmidir, bu algoritm matematikda raqam sistemasiga asoslanadi. Algoritm shu erda ma'lum bir tartiblash usuli bilan o'zlashtiriladi va unda sonlar ro'yxati yoki o'zgaruvchilarning qiymatlari tahrirlanmaydi, faqat ularni usullariga ko'ra tartiblaydi. Download 75.97 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling