Malumotlar tuzilmasi va algoritmlar

Algoritm samaradorligi:
O( ) – eng samarali usul.

Dastur kodi:
def partition(arr, low, high):
i = (low-1) # kichik elementlar indeksi
pivot = arr[high] # pivot
for j in range(low, high):
if arr[j] <= pivot:
i = i+1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return (i+1)

def quickSort(arr, low, high):

if len(arr) == 1:
return arr
if low < high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr, 0, n-1)
print("Saralangan massiv: ")
for i in range(n):
print("%d" % arr[i])

Masala

1. 
   #include
   

using namespace std;
int main()
{int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr, arr + n, greater());
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;}

1. 
   #include
   

using namespace std;
int main()
{
int arr[] = { 0, 1, 5, 8, 9, 6, 7, 3, 4, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
sort(arr + 2, arr + n);
cout << "Array after sorting : \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
return 0;
}


#include
using namespace std;
int main()
{
int a[100],x,i,j,temp;
cout<<"mashina sonini kiriting: ";
cin>>x;
cout<<"mashina raqamlarini kiriting: "<
for(i=0;i
cin>>a[i];
for(i=1;i
{
for(j=0;j<(x-i);++j)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
cout<<"mashina raqamlarini boyicha saralangan varianti:"<
for(i=0;i
cout<<" "<
return 0;
}


#include
using namespace std;
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i
= (low
- 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high) {
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver Code
int main()
{
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}


Tezkor saralash o'zining umumiy ko'rinishida o'z joyida tartiblashdir (ya'ni, qo'shimcha saqlashni talab qilmaydi), birlashma tartiblash esa O(N) qo'shimcha saqlashni talab qiladi, N massiv hajmini bildiradi, bu juda qimmat bo'lishi mumkin. Birlashtirish uchun qo'shimcha joy ajratish va ajratish algoritmning ishlash vaqtini oshiradi. O'rtacha murakkablikni solishtirsak, biz ikkala turning ham O (NlogN) o'rtacha murakkabligiga ega ekanligini aniqlaymiz, ammo doimiylar farq qiladi. Massivlar uchun qo'shimcha O(N) saqlash joyidan foydalanish tufayli birlashma tartiblash yo'qotadi.
Tezkor saralashning ko'pgina amaliy ilovalari tasodifiy versiyadan foydalanadi. Tasodifiy versiyada kutilgan vaqt murakkabligi O(nLogn) ga ega. Eng yomon holat tasodifiy versiyada ham mumkin, lekin eng yomon holat ma'lum bir naqsh uchun (masalan, tartiblangan massiv) sodir bo'lmaydi va tasodifiy Tez tartiblash amalda yaxshi ishlaydi.
Tez tartiblash keshga qulay tartiblash algoritmidir, chunki u massivlar uchun ishlatilganda yaxshimosyozuvlar joyiga ega.
Tez tartiblash, shuningdek, quyruq rekursivdir, shuning uchun quyruq qo'ng'iroqlarini optimallashtirish amalga oshiriladi.

Shell sort asosan Insertion Sort ning o'zgarishi hisoblanadi . Qo'shish tartibida biz elementlarni faqat bir pozitsiya oldinga siljitamiz. Elementni ancha oldinga siljitish kerak bo'lganda, ko'plab harakatlar ishtirok etadi. ShellSort g'oyasi uzoqdagi narsalarni almashish imkonini berishdir. Shell sortida biz massivni h ning katta qiymati uchun h-tartibga solamiz. Biz h qiymatini 1 ga aylanguncha kamaytirishda davom etamiz. Agar har bir h elementning barcha quyi ro'yxatlari tartiblangan bo'lsa, massiv h-tartiblangan deyiladi.