Dastur natijasi:
4.Bubble sort algoritmi orqali tartiblangan
Optimallashtirilgan qabariqni saralash algoritmi
Yuqoridagi algoritmda, massiv allaqachon tartiblangan bo'lsa ham, barcha taqqoslashlar amalga oshiriladi.
Bu bajarilish vaqtini oshiradi.
Buni hal qilish uchun biz almashtirilgan qo'shimcha o'zgaruvchini kiritishimiz mumkin. Agar elementlar almashinuvi sodir bo'lsa, almashtirilgan qiymat rost bo'ladi. Aks holda, u noto'g'ri o'rnatiladi.
Iteratsiyadan so'ng, agar almashtirish bo'lmasa, almashtirilgan qiymat noto'g'ri bo'ladi. Bu shuni anglatadiki, elementlar allaqachon tartiblangan va keyingi takrorlashni amalga oshirishga hojat yo'q.
Dastur kodi:
# Optimized Bubble sort in Python
def bubbleSort(array):
for i in range(len(array)):
swapped = False
for j in range(0, len(array) - i - 1):
if array[j] > array[j + 1]:
temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
swapped = True
if not swapped:
break
data = [-2, 45, 0, 11, -9]
bubbleSort(data)
print('Sorted Array in Ascending Order:')
print(data)
Dastur natijasi:
5.Optimallashtirilgan Bubble sort algoritmi
Quicksort Algorithm
Quicksort - bu bo'lish va zabt etish yondashuviga asoslangan saralash algoritmi
Massiv pivot elementni (massivdan tanlangan element) tanlash orqali pastki massivlarga bo'linadi.
Massivni bo'lishda aylanma elementni shunday joylashtirish kerakki, burchakdan kichikroq elementlar chap tomonda, burilishdan kattaroq elementlar esa o'ng tomonda joylashgan bo'lishi kerak.
Xuddi shu yondashuv yordamida chap va o'ng pastki qatorlar ham bo'linadi. Bu jarayon har bir pastki qator bitta elementni o'z ichiga olguncha davom etadi.
Ushbu nuqtada elementlar allaqachon tartiblangan. Nihoyat, elementlar tartiblangan massivni hosil qilish uchun birlashtiriladi.
Dastur kodi:
# Quick sort in Python
def partition(array, low, high):
pivot = array[high]
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
(array[i], array[j]) = (array[j], array[i])
(array[i + 1], array[high]) = (array[high], array[i + 1])
return i + 1
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
data = [8, 7, 2, 1, 0, 9, 6]
print("Unsorted Array")
print(data)
size = len(data)
quickSort(data, 0, size - 1)
print('Sorted Array in Ascending Order:')
print(data)
Do'stlaringiz bilan baham: |