Kirish: I. Ma’lumotlar tuzilmasini saralash usullari

Ildizli saralash

Ildizlarni saralashda ro'yxat kalit qiymatlarni bir-biri bilan to'g'ridan-to'g'ri taqqoslamasdan buyurtma qilinadi. Bunday holda, "vayronalar" to'plami yaratiladi va elementlar kalitlarning qiymatlariga qarab staklarga taqsimlanadi. Keyingi qiymatlarni yig'ib, kalitning ketma-ket qismlari uchun butun protsedurani takrorlab, biz tartiblangan ro'yxatni olamiz. Ushbu protsedura ishlashi uchun stacking va keyingi montaj juda ehtiyotkorlik bilan bajarilishi kerak.

Shunga o'xshash tartib kartalarni qo'lda tartiblashda qo'llaniladi. Ba'zi kutubxonalarda, kompyuterdan oldingi paytlarda, kitobni chiqarishda, kartochka to'ldirilgan. Chiqarilgan kartalar raqamlangan va karta raqamiga qarab ularning yon tomonida bir qator chuqurchalar qilingan. Kitob qaytarib berilganda, ekstraditsiya kartasi o'chirildi va qoziqqa tashlandi. So'ngra butun chuqurchaga birinchi chuqurchalar joyida uzun igna nayzalangan va igna ko'tarilgan. O'chirilgan belgi bilan kartalar stolda qoldi, qolganlari ignaga mixlab qo'yildi. Keyin paydo bo'lgan ikkita qoziqlar qayta joylashtirildi, shunda ignalardagi kartalar teshiklari bo'lgan kartalarning orqasida qoldi. Keyin igna ikkinchi chuqurchaga yopishtirilgan va butun jarayon takrorlangan. Barcha pozitsiyalarni teshib chiqqandan so'ng, kartalar raqamlar ketma-ketligida paydo bo'ldi.

Qo'lda ishlov berishning ushbu protsedurasi kartochkalarni birinchi bosqichdagi raqamning ahamiyatsiz raqamining qiymatiga va oxiridagi eng yuqori raqamga qarab ajratadi.

package koren_sort;

import java.util.Arrays;

public class Koren_sort {

void countingSort(int array[],

int size, int place) {

int[] output = new int[size + 1];

int max = array[0];

for (int i = 1; i < size; i++) {

if (array[i] > max)

max = array[i]; }

int[] count = new int[max + 1];

for (int i = 0; i < max; ++i)

count[i] = 0;

for (int i = 0; i < size; i++)

count[(array[i] / place) % 10]++;

for (int i = 1; i < 10; i++)

count[i] += count[i - 1];

for (int i = size - 1; i >= 0; i--) {

output[count[(array[i] / place) % 10] - 1] = array[i];

count[(array[i] / place) % 10]--; }

for (int i = 0; i < size; i++)

array[i] = output[i]; }

int getMax(int array[], int n) {

int max = array[0];

for (int i = 1; i < n; i++)

if (array[i] > max)

max = array[i];

return max; }

void radixSort(int array[], int size) {

int max = getMax(array, size);

for (int place = 1; max / place > 0; place *= 10)

countingSort(array, size, place); }

public static void main(String args[]) {

int[] data = { 121, 432, 564, 23, 1, 45, 788 };

int size = data.length;

Koren_sort rs = new Koren_sort ();

rs.radixSort(data, size);

System.out.println(Arrays.toString(data)); } }

310 213 023 130 013 301 222 032 201 111 323 002 330 102 231 120

Berilgan tizim Berilganlar

0 310 130 330 120

1 301 201 111 231

2 222 032 002 102

3 213 023 013 323

(а) Birinshi bosqish, birlik razryad

Birinchi bosqishdan olingan tizim
310 130 330 120 301 201 111 231 222 032 002 102 213 023 013 323

Berilgan tizim Berilganlar

0 301 201 002 102

1 310 111 213 013

2 120 222 023 323

3 130 330 231 032

(б) Ikkinchi bosqish, onlik razryad

Ikkinchi bosqishdan olingan tizim

301 201 002 102 310 111 213 013 120 222 023 323 130 330 231 032

Berilgan tizim Berilganlar

0 002 013 023 032

1 102 111 120 130

2 201 213 222 231

3 301 310 323 330

(в) Uchunchi bosqish, yuzlik razryad

Uchunchi bosqishdan olingan tizim