Hisoblash(counting) sort algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtiring

1. 
   Hisoblash(counting) sort algoritmi orqali Respublikamizdagi viloyatlar maydonini o’sish tartibida joylashtiring. (Foydalangan saralash algoritmingiz haqida nazariy ma’lumotlar bering?)
   

Hisoblash (counting sort) algoritmi - kirish massividagi har bir noyob elementning takrorlanish sonini hisoblash va bu ma'lumotlardan chiqish massividagi elementlarni to'g'ri tartibda joylashtirish orqali ishlaydigan tartiblash algoritmi. Bu kam sonli noyob elementlarga ega massivlarni saralash uchun samarali algoritm bo'lib, vaqt murakkabligi O(n) ga teng.

Counting sort barqaror tartibdir, ya'ni tartiblangan massivda bir xil qiymatga ega elementlarning tartibi saqlanib qoladi. Bu o'z joyida tartiblash, ya'ni massivni saralash uchun qo'shimcha joy kerak emas.

Amalda Counting sort algoritmiga misol:

Python dasturlash tilidagi kod :

# areas of regions

input_array = [4200, 39400, 6800,20500, 6300, 7900, 110800, 28400, 160000, 16400, 5100, 20800, 15300]
output_array = [0, 0, 0, 0, 0, 0, 0, 0, 0]
counts = [0, 0, 0] # Array to store the count of each element

# Count the number of occurrences of each element

for element in input_array:
counts[element] += 1

# Calculate the starting index for each element

for i in range(1, len(counts)):
counts[i] += counts[i-1]

# Place each element in the correct position in the output array

for element in input_array:
output_array[counts[element]-1] = element
counts[element] -= 1

print(output_array)