Misol: nxn o`lchovli massivning har bir satrini o`sish tartibida saralash.
Yechish:
Massivning har bir satr elementlarini yordamchi bir o`lchovli massivga berib, har bir satrini alohida QuickSort funkiyasi orqali saralab chiqamiz. Bu dasturni har bir satrini EasySort yoki BubleSort saralashlari orqali ham bajarsak ham boladi.
Lekin EasySortda n! marta, BubleSortda 2n ta iteratsiya bajariladi.
QuickSortda bu ko`rsatkich n*lg n ga teng.
Kodni C# tilida yozamiz.
Bunda massiv elementlari dasturchi vaqtini tejash uchunRandom metodi orqali kiritiladi.
1-run: n=5 massivning o`lchami kiritildi. 5x5 massiv elementlariga qiymat berildi va shu vaqtning o`zida console ga chiqariladi.
2-qismida esa,har bir satri o`sish tartibida joylashgan 5x5 o`lchovli massiv.
2-run: n=7;
Endi ustunlari bo`yich tartiblanganini ko`ramiz:
using System.Text;
namespace QuickSort
{
class Program
{
static void Main(string[] args)
{
int n = int.Parse(Console.ReadLine());
int[,] lst = new int[n,n];
Random rand = new Random();
for (int i = 0; i < n; i++)
{ for(int j=0;j
lst[i,j] = rand.Next(100);
//massiv elementlari RANDOM funksiyasi orqali kiritildi va sh vaqtda ekranga chiqarilib boradi
Console.Write(lst[i,j]+" ");
}
Console.WriteLine();
}
Console.WriteLine();
Sort obj = new Sort();
int []lst1=new int[n];//yordamchi massiv kiritamiz
for (int i = 0; i < n; i++)
{for(int j=0;j
lst1[j]=lst[j,i];
}
obj.QuickSort(lst1,0,n-1);
for(int j=0;j
lst[i,j]=lst1[j];
}
}
for (int i = 0; i < n; i++)
{ for(int j=0;j
Console.Write(lst[i,j]+" ");
}
Console.WriteLine();
}
Console.ReadKey();
}
}
}
Classni quyidagicha yozamiz:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class Sort
{ public void QuickSort(int []lst,int left,int right)
{int piv;
int l_a=left;
int r_a=right;
piv=lst[(int)((left+right)/2)];
int a;
do
{
while(lst[r_a]>piv)
r_a--;
while(lst[l_a]
l_a++;
if(r_a>=l_a)
{
a=lst[r_a];lst[r_a]=lst[l_a];lst[l_a]=a;
r_a--;
l_a++;
}
}while(r_a>=l_a);
if(r_a>left)
{
QuickSort(lst,left,r_a);
}
if(right>l_a)
{
QuickSort(lst,l_a,right);
}
}
}
}
Xulosa.
Barchamizga ma`lumki kundalik hayotimizda bevosita va bilvosita ba’zida o`zlarimiz e’tibor bermagan holda saralash algoritmlariga duch kelamiz. Masalan, safdagi bolalarni bo`ylari bo`yicha tartiblash , navbatda turganlarda va boshqa-boshqa joylarda ko`rishimiz mumkin. Inson har doim ish vaqtini kamaytirish uchun harakat qiladi.
Bu kurs ishimda Quick sort saralash algoritmini o`rgandim.
Easy Sort va Buble Sort larga nisbatan Quick Sort n*log(n) iteratsiyadan iborat. Katta-katta massivlarni saralashda biz 1000-10000 martagacha ishimizni qisqartirishimiz mumki.
Foydalanilgan adabiyotlar:
Г. Шилдт “Полный справочник по С++ ”;
Aripov M. “Informatika va hisoblash texnikasi asoslari ”;
Павел Агуров «С# справочник рецептов»;
Internet ma’lumotlari:
https://dasturchi.uz/algorithm/saralash-algoritmlari/
library.ziyonet.uz/ru/book
uzinfobiz.ru
aim.uz
www.javenue.info
Do'stlaringiz bilan baham: |