Kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti samarqand filiali

 for(i = 0; i < MAX; i++)  
 { 
   llist_add(&newnode, (rand() % 100)); 
 } 
head = newnode; 
 printf("saralashgacha:\n"); 
 llist_print(); 
 printf("saralashdan keyin:\n"); 
 llist_bubble_sort(); 
 llist_print(); 
return 0; 
} 
void llist_add(struct lnode **q, int num)  
{ 
 struct lnode *tmp;  
tmp = *q; 
if(*q == NULL) { 
  *q = malloc(sizeof(struct lnode)); 
   tmp = *q; 
 } else { 
  while(tmp->next != NULL) 
   tmp = tmp->next; 

---

58 
 
   tmp->next = malloc(sizeof(struct lnode)); 
   tmp = tmp->next; 
 } 
tmp->data = num; 
 tmp->next = NULL; 
} 
void llist_print(void)  
{ 
 visit = head; 
while(visit != NULL) { 
  printf("%d ", visit->data); 
  visit = visit->next; 
 } 
 printf("\n"); 
} 
void llist_bubble_sort(void)  
{ 
 struct lnode *a = NULL; 
 struct lnode *b = NULL;  
 struct lnode *c = NULL; 
 struct lnode *e = NULL;  
 struct lnode *tmp = NULL;  
while(e != head->next)  
 { 
 
c = a = head; 
 
b = a->next; 
 
 
while(a != e)  
 
 
{ 
 
 
 
if(a->data > b->data)  

---

59 
 
 
 
 
{ 
 
 
 
 
if(a == head)  
 
 
 
 
{ 
 
 
 
 
 
tmp = b -> next; 
 
 
 
 
 
b->next = a; 
 
 
 
 
 
a->next = tmp; 
 
 
 
 
 
head = b; 
 
 
 
 
 
c = b; 
 
 
 
 
}  
 
 
 
 
else  
 
 
 
 
{ 
 
 
 
 
 
tmp = b->next; 
 
 
 
 
 
b->next = a; 
 
 
 
 
 
a->next = tmp; 
 
 
 
 
 
c->next = b; 
 
 
 
 
 
c = b; 
 
 
 
 
} 
 
 
 
}  
 
 
 
else  
 
 
 
{ 
 
 
 
 
c = a; 
 
 
 
 
a = a->next; 
 
 
 
} 
 
 
 
b = a->next; 
 
 
 
if(b == e) 
 
 
 
 
e = a; 
 
 
} 
 
} 
} 

---

60 
 
2-listingda  Python  tilidagi  standart  ro’yxatga  tadbiq  qilinagn  pufaksimon 
saralash algoritmining tadbiqi keltirilgan. 
Listing 2. Python tilida pufaksimon saralash algoritmining tadbiqi 
import random  
lista = []  
for i in range ( 0, 10 ) :  
  lista.append ( int ( random.uniform ( 0, 10 ) ) 
) 
print lista 
def bubble_sort ( lista ) : 
  swap_test = False 
  for i in range ( 0, len ( lista ) - 1 ): 
    for j in range ( 0, len ( lista ) - i - 1 ): 
      if lista[j] > lista[j + 1] : 
        lista[j],  lista[j  +  1]  =  lista[j  +  1], 
lista[j]  
        swap_test = True 
    if swap_test == False: 
      break 
bubble_sort ( lista )  
print lista 
3-listingda  Python  tilida  pufaksimon  saralash  algoritmining  bog’langan 
ro’yxatdagi tadbiqi keltirilgan.  
Listing  3.  Bog’langan  ro’yxatga  pufaksimon  saralash  algoritmini  tadbiq 
qilish 
import random  
class Node: 
    def __init__(self, value = None, next = None): 
        self.value = value 

---

61 
 
        self.next = next 
    def __str__(self): 
        return 'Node ['+str(self.value)+']' 
class LinkedList: 
    def __init__(self): 
        self.first = None 
        self.last  = None 
        self.length = 0 
    def add(self, x): 
        if self.first == None: 
            self.first = Node(x, None) 
            self.last = self.first 
        elif self.last == self.first: 
            self.last = Node(x, None) 
            self.first.next = self.last 
        else: 
            current = Node(x, None) 
            self.last.next = current 
            self.last = current 
    def __str__(self): 
        if self.first != None: 
            current = self.first 
    out = 'LinkedList [ ' +str(current.value) +' ' 
            while current.next != None: 
                current = current.next 
                out += str(current.value) + ' ' 
            return out + ']\n' 
        return 'LinkedList []' 
    def BubbleSort(self): 

---

62 
 
       a = Node(0,None) 
       b = Node(0,None) 
       c = Node(0,None) 
       e = Node(0,None) 
       tmp = Node(0,None) 
       while(e != self.first.next) : 
        c = a = self.first 
        b = a.next 
        while a != e: 
          if a and b: 
            if a.value > b.value: 
              if a == self.first: 
                tmp = b.next 
                b.next = a 
                a.next = tmp 
                self.first = b 
                c = b 
              else: 
                tmp = b.next 
                b.next = a 
                a.next = tmp 
                c.next = b 
                c = b 
            else: 
              c = a 
              a = a.next 
            b = a.next 
            if b == e: 
              e = a 

---

63 
 
          else: 
              e = a 
               
L  = LinkedList() 
for i in range ( 0, 10 ) :  
  L.add ( int ( random.uniform ( 0, 10 ) ) ) 
print L 
L.BubbleSort() 
print L 
3-listingdagi  keltirilgan  dastur  kodidan  ko’rish  mumkinki,  Python  da 
ob’ektga  qo’yilgan  ko’rsatkichlar  bilan  ishlash  aynan  C  tilidagiga  (1-listingga 
qarang) o’xshash amalga oshiriladi.  
 
4.3. Tezkor saralash 
Ushbu  bo’limda  ikki  bog’lamli  ro’yxatda  tezkor  saralash  (quicksort) 
algoritmining  QuickSortList  rekursiv  funktsiyasining  qo’llanilishini  qarab 
chiqamiz (4-listing).  
Bu funktsiya quyidagi tartibda ishlaydi: 
- ro’yxat bo’yicha iteratsiya qadamlarini bajaradi; 
- iteratsiya qadamlari natijasida massiv oxiriga joylashtiriladigan eng katta 
qiymatni aniqlaydi; 
- keyingi qadamda topilgan eng katta qiymatli elementdan tashqari qolgan 
elementlar ustida iteratsiya takrorlanadi va h.k.  
Listing 4. C tilida tezkor saralash algoritmining tadbiqi