Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo‘l algoritmi
![{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0)
return 0; // colinear
return (val > 0) ? 1 : 2;
}
int compare(const void *vp1, const void *vp2)
{
Point *p1 = (Point *) vp1;
Point *p2 = (Point *) vp2;
// Find orientation
int o = orientation(p0, *p1, *p2);
if (o == 0)
return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;
return (o == 2) ? -1 : 1;
}
void convexHull(Point points[], int n)
{](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_8.png?v=1)
![int ymin = points[0].y, min = 0;
for (int i = 1; i < n; i++)
{
int y = points[i].y;
if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
ymin = points[i].y, min = i;
}
swap(points[0], points[min]);
p0 = points[0];
qsort(&points[1], n - 1, sizeof(Point), compare);
stack<Point> S;
S.push(points[0]);
S.push(points[1]);
S.push(points[2]);
for (int i = 3; i < n; i++)
{
while (orientation(nextToTop(S), S.top(), points[i]) != 2)
S.pop();
S.push(points[i]);
}
while (!S.empty())
{
Point p = S.top();](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_9.png?v=1)
![cout << "(" << p.x << ", " << p.y << ")" << endl;
S.pop();
}
}
int main()
{
Point points[] = { { 0, 3 }, { 1, 1 }, { 2, 2 }, { 4, 4 }, { 0, 0 },
{ 1, 2 }, { 3, 1 }, { 3, 3 } };
int n = sizeof(points) / sizeof(points[0]);
cout << "The points in the convex hull are: \n";
convexHull(points, n);
return 0;
}
Ish vaqti. Greham protsedurasining ishlash vaqti O (n lg n) dir, bu erda n = | Q |.
Osonlik bilan ko'rsatib turibdiki, while sikli O (n) vaqtni oladi. Qutbiy burchaklarni
saralash O (n lg n) vaqtni oladi, bu erda Greham protsedurasining umumiy
asimptotikasi kuzatiladi. Algoritm S dan p1 boshlang'ich nuqtasini topishdan
boshlanadi, bu esa konveks korpusining tepasi bo'lishi kafolatlanadi. Jarvis usulida
bo'lgani kabi S to'plamning eng past nuqtalarining chap tomoni p1 nuqta olinadi.
Shubhasiz, p1 nuqtasini O (n) vaqt ichida topish mumkin. Greхеm algoritmidagi
nuqtalar tartibi
Tartiblangan nuqtalar ikki baravar bog'langan ro'yxatga joylashtirilishi kerak
(p1, p2,…, pn). Grexemning o'tishi natijasida olingan tartiblangan ro'yxatni
skanerlash va undan konveks qobig'iga kiritilmagan nuqtalarni olib tashlash kiradi.
Algoritmni yanada tavsiflash uchun biz quyidagi yozuvni kiritamiz: agar a
nuqtadan b tomon yo'naltirilgan vektor hosil qilgan to'g'ri chiziqning chap tomonida c
bo'lsa, a, b va c uchta nuqta chap burilishni hosil qiladi deymiz.](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_10.png?v=1)
![Aytaylik, biz A massivni saralashni xohladik. Kichik vazifa bu p indeksidan
boshlanib, r indeksida tugagan, A [p..r] bilan belgilangan kichik qismini ajratishdir.
“Bo’lib tashlash” Agar q qiymati p va r orasida bo'lsa, biz A [p..r] massivni
ikkita A [p..q] va A [q + 1, r] kichik massivlarga bo'lishimiz mumkin.
“Hukmronlik qilish”. “Hukmronlik qilish” bosqichida biz ikkala A [p..q] va A [q
+ 1, r] kichik massivlarni saralashga harakat qilamiz. Agar hali ham boshlang'ich
darajaga yetib bormagan bo'lsak, yana ikkala quyi qismni ajratib, ularni saralashga
harakat qilamiz.
Birlashtirish bosqichi asosiy pog'onaga yetib borganida va biz A [p..r] massivi
uchun ikkita tartiblangan A [p..q] va A [q + 1, r] kichik massivlarni olsak, natijalarni
A [p..r] massiviga birlashtiramiz. Bu ikkita tartiblangan A [p..q] va A [q + 1, r]
massivlarning birlashmasidir.
MergeSort(A, p, r)
If p > r
return;
q = (p+r)/2;
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
Algoritmning eng muhim qismi bu "birlashtirish" bosqichidir.
Birlashish bosqichi - ikkita katta ro'yxat (massiv) yaratish uchun ikkita
tartiblangan ro'yxatni (massivlarni) birlashtirish bo'yicha oddiy muammoning
yechimi.
Algoritm uchta ko'rsatgichni saqlaydi, ikkitasi har biri uchun va bittasi
tartiblangan qatorning joriy indeksini saqlab qolish uchun.
Ikkinchi massivda boshqa elementlar qolmaganligi va ikkala massiv ham ishga
tushirilganda saralanganligini bilganimiz uchun qolgan massivlarni to'g'ridan-to'g'ri
birinchi massivdan nusxalashimiz mumkin.
Birlashtirib saralash algoritmi uchun dastur kodi](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_16.png?v=1)
![// C++ program for Merge Sort
#include
using namespace std;
// Array[] ikkita ichki massivni birlashtiradi.
//Birinchi ichki massiv - Array[l..m]
// Ikkinchi ichki massiv Array[m+1..r]
void merge(int Array[], int l, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
// Vaqtinchalik massivlarni yaratish
int L[n1], R[n2];
// Ma'lumotlarni vaqtinchalik L[] va R[] massivlariga nusxalash
for (int i = 0; i < n1; i++)
L[i] = Array[l + i];
for (int j = 0; j < n2; j++)
R[j] = Array[m + 1 + j];
// Vaqtinchalik massivlarni yana arr [l..r] ga birlashtirish.
// Birinchi ichki massivning boshlang'ich ko'rsatkichi
int i = 0;
// Ikkinchi kichik massivning boshlang'ich ko'rsatkichi
int j = 0;
// Birlashtirilgan ichki massivning dastlabki ko'rsatkichi
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
Array[k] = L[i];
i++;
}
else {
Array[k] = R[j];
j++;
}
k++;
}
// L [] ning qolgan elementlarini nusxalash,
//agar mavjud bo'lsa
while (i < n1) {
Array[k] = L[i];](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_17.png?v=1)
![i++;
k++;
}
// Agar mavjud bo'lsa, R [] ning
//qolgan elementlarini nusxalash
while (j < n2) {
Array[k] = R[j];
j++;
k++;
}
}
// l chap indeks uchun,
//r esa tartiblangan ichki massivning o'ng indeksidir
void mergeSort(int Array[],int l,int r){
if(l>=r){
return;//rekursiv ravishda qaytadi
}
int m =l+ (r-l)/2;
mergeSort(Array,l,m);
mergeSort(Array,m+1,r);
merge(Array,l,m,r);
}
// Massivni chop etish funksiyasi
void printArrayay(int A[], int size)
{
for (int i = 0; i < size; i++)
cout << A[i] << " ";
}
int main()
{
int Array[] = { 12, 11, 13, 5, 6, 7 };
int Array_size = sizeof(Array) / sizeof(Array[0]);
cout << "Berilgan massiv \n";
printArrayay(Array, Array_size);
mergeSort(Array, 0, Array_size - 1);
cout << "\n Tartiblangan massiv \n";
printArrayay(Array, Array_size);
return 0;
}](https://docx.uz/documents/b9006bb2-0947-4730-8a5e-61687029a015/page_18.png?v=1)
Oriyentatsiya funksiyasi. Grexem algoritmi. Ajrat va hukmron bo‘l algoritmi