Attachment 83357 Details for Bug 119077 – file.txt

file.txt

file.txt (text/plain), 1.49 KB, created by Michal Botka on 2007-12-27 21:30:00 UTC

(hide)

Description:

Filename:

MIME Type:

Creator: Michal Botka

Created: 2007-12-27 21:30:00 UTC

Size: 1.49 KB

patch

obsolete

>418c418,456
>< /* Use a disgustingly simplistic bubble sort to put our lists in order */
>---
>> /* Quick sort algorithm */
>> void
>> index_list_qsort(PkgNodePtr first, PkgNodePtr stop)
>> {
>>     /* empty or one-item list is already sorted */
>>     if (first == stop || first->next == stop)
>>         return;
>> 	
>>     /* quick sort */
>>     PkgNodePtr i, p;
>>     int size1, size2;
>>     char* pivotName;
>>  
>>     size1 = 0;
>>     size2 = 0;
>>     pivotName = first->name;
>>     for (p = first, i = p->next; i!=stop; i = i->next) {
>>         if (strcmp(i->name, pivotName)<0) {
>>             p = p->next;
>>             swap_nodes(p, i);
>>             size1++;
>>         } else {
>>             size2++;
>>         }
>>     }
>>     swap_nodes(first, p);
>>     
>>     /* we handle the shorter part before the longer
>>        recursion depth never exceeds logarithm of the total list length */
>>     if (size1 <= size2) { 
>>         index_list_qsort(first, p);
>>         index_list_qsort(p->next, stop);
>>     } else {
>>         index_list_qsort(p->next, stop);
>>         index_list_qsort(first, p);
>>     }
>> }
>> 
>> /* Use a quick sort to put our lists in order */
>425,430c463
><     for (p = top->kids; p; p = p->next) {
>< 	for (q = top->kids; q; q = q->next) {
>< 	    if (q->next && strcmp(q->name, q->next->name) > 0)
>< 		swap_nodes(q, q->next);
>< 	}
><     }
>---
>>     index_list_qsort(top->kids, NULL);
>434,435c467,469
>< 	if (p->kids)
>< 	    index_sort(p);
>---
>>         if (p->kids) {
>>             index_sort(p);
>>         }

Actions: View

Attachments on bug 119077: 83357