|
#include
// ikki bog’lamli ro’yxat elementi
typedef struct _tagIntegerList
{
int nInteger;
64
struct _tagIntegerList *pPrev;
struct _tagIntegerList *pNext;
} IntegerList;
//ro’yxatning birinchi va oxirgi
//elementlariga ko’rsatkichlar
IntegerList *g_pFirstItem = NULL;
IntegerList *g_pLastItem = NULL;
// ro’yxatga qo’shish
void AddListItem(int nInteger)
{
IntegerList *pItem = new IntegerList;
pItem->nInteger = nInteger;
if (g_pFirstItem == NULL)
{
g_pFirstItem = g_pLastItem = pItem;
pItem->pNext = pItem->pPrev = NULL;
}
else
{
g_pLastItem->pNext = pItem;
pItem->pPrev = g_pLastItem;
g_pLastItem = pItem;
pItem->pNext = NULL;
}
}
// o’chirish
void RemoveAllItems()
{
IntegerList *pDelItem, *pItem = g_pFirstItem;
65
while (pItem != NULL)
{
pDelItem = pItem;
pItem = pItem->pNext;
delete pDelItem;
}
g_pFirstItem = g_pLastItem = NULL;
}
// ro’yxat mazmunini chiqarish
void PrintList()
{
IntegerList *pItem = g_pFirstItem;
while (pItem != NULL)
{
printf("%d ", pItem->nInteger);
pItem = pItem->pNext;
}
printf("\n");
}
// tezkor saralash
void QuickSortList(IntegerList *pLeft, IntegerList
*pRight)
{
IntegerList *pStart;
IntegerList *pCurrent;
int nCopyInteger;
// saralash oxiri - chiqish
if (pLeft == pRight) return;
66
// ikkita ishchi ko’rsatkichni o’rnatish - Start
va Current
pStart = pLeft;
pCurrent = pStart->pNext;
// ro’yxat bo’yicha chapdan o’ngga yurish
while (1)
{
//eng katta qiymatli element ro’yxat boshiga
joylashadi
if (pStart->nInteger < pCurrent->nInteger)
{
nCopyInteger = pCurrent->nInteger;
pCurrent->nInteger = pStart->nInteger;
pStart->nInteger = nCopyInteger;
}
if (pCurrent == pRight) break;
pCurrent = pCurrent->pNext;
}
// First va Current ni almashtirish – eng katta
// qiymat ro’yxatning o’ng oxiriga tushadi
nCopyInteger = pLeft->nInteger;
pLeft->nInteger = pCurrent->nInteger;
pCurrent->nInteger = nCopyInteger;
// Current ni saqlab qo’yish
IntegerList *pOldCurrent = pCurrent;
// rekursiya
pCurrent = pCurrent->pPrev;
if (pCurrent != NULL)
{
67
if
((pLeft->pPrev!=pCurrent)&&(pCurrent->pNext!=
pLeft))
QuickSortList(pLeft, pCurrent);
}
pCurrent = pOldCurrent;
pCurrent = pCurrent->pNext;
if (pCurrent != NULL)
{
if
((pCurrent->pPrev!=pRight)&&(pRight-
>pNext!=pCurrent))
QuickSortList(pCurrent, pRight);
}
}
int main ()
{
AddListItem(100);
AddListItem(12);
AddListItem(56);
AddListItem(67);
PrintList();
QuickSortList(g_pFirstItem, g_pLastItem);
PrintList();
RemoveAllItems();
return 0;
}
68
4.4. Birlashtirish orqali saralash
Birlashtirish orqali (mergesort) saralashda massiv ikki qismga ajratilib, har
bir qism alohida saralanadi va saralangan qismlar qo’shiladi. Buni quyidagi misol
yordamida tushuntirish mumkin:
- kartalar to’plami ikki qismga ajratiladi, va har bir qism eng kichik karta
ustida turadigan qilib saralanadi;
- ustida turgan kartalardan kichigi tanlab olinadi va natijaviy to’plamga
qo’yiladi;
- ikki qismda kartalar tamom bo’lmaguncha ushbu jarayon takrorlanadi;
- agar biror qismto’plamda kartalar soni oldin tugab qolsa, qolgan
qismto’plamdagi kartalarni to’g’ridan-to’g’ri natijaviy to’plamga qo’shib
qo’yamiz.
Bu algoritm 1945 yilda Djon fon Neyman tomonidan o’ylab topilgan deb
hisoblanadi. Bu algoritmning kamchiligi, O(n) xotirani talab qiladi.
Listing 5. C tilida birlashtirib saralashning tadbiqi
struct node
{
int number;
struct node *next;
};
struct node *addnode(int number, struct node *next)
{
struct node *tnode;
tnode = (struct node*)malloc(sizeof(*tnode));
if(tnode != NULL)
{
tnode->number = number;
tnode->next = next;
}
69
return tnode;
}
int Length(struct node* head)
{
int count = 0;
struct node* current = head;
while (current != NULL)
{
count++;
current = current->next;
}
return(count);
}
void FrontBackSplit(struct node* source,
struct node** frontRef,
struct node** backRef)
{
int len = Length(source);
int i;
struct node* current = source;
if (len < 2)
{
*frontRef = source;
*backRef = NULL;
}
else
{
int hopCount = (len-1)/2;
for (i = 0; i
70
{
current = current->next;
}
// kiruvchi ro’yxatni ikkita qismro’yxatga
ajratish
*frontRef = source;
*backRef = current->next;
current->next = NULL;
}
}
struct node* SortedMerge(struct node* a, struct node*
b)
{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);
if (a->number <= b->number)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return(result);
}
void MergeSort(struct node** headRef)
71
{
struct node* head = *headRef;
struct node* a;
struct node* b;
// ro’yxat uzunligi 0 yoki 1 teng bo’lgan holda
if ((head == NULL) || (head->next == NULL))
{
return;
}
FrontBackSplit(head, &a, &b);
MergeSort(&a); // qismro’yxatlarni rekursiv
saralash
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
4.5. Turli algoritmlarni taqqoslash
Saralashning turli algoritmlarini o’rganib bo’lgandan keyin, ularni
samaradorligini taqqoslab ko’ramiz. Buning uchun 50000 ta elementdan iborat bir
bog’lamli ro’yxatdan foydalanamiz. Bu ro’yxat elementlari uchun 0 dan 100
gacha qiymatli kalitlarni qo’llash mumkin. Elementlarini erkin holda quyidagicha
joylashtiramiz:
0 10 10 2 9 7 2 3 4 5 2 2 10 1 1 .....
Saralangandan keyin ro’yxat quyidagi ko’rinishga ega bo’lishi kerak:
0 1 1 2 2 2 2 3 4 5 7 9 10 10 10 .....
Testlashda uchta vaqtinchalik belgilashlarni kiritib olamiz: dasturni ishga
tushirish, boshlash va saralashning oxiri. Eng qiziqarli narsa, bu saralash uchun
sarflanadigan vaqt. 6-listingda pufakimon saralash algoritmining samaradorligini
baholovchi main funktsiyasining kodi keltirilgan.
72
Listing 6. C tilida pufaksimon saralash algoritmini baholash
Do'stlaringiz bilan baham: | 
