Быстрая сортировка в связанном списке, как заставить этот код использовать первый элемент в качестве основного, а не последний - PullRequest
Новая
       11

Быстрая сортировка в связанном списке, как заставить этот код использовать первый элемент в качестве основного, а не последний

0 голосов
/ 01 марта 2020

Что бы мне пришлось реализовать, чтобы этот код работал с использованием первого элемента в качестве основного, а не последнего?

Любой подход, который я использовал, не сработал, любая помощь будет оценена, спасибо !!!!!! 

struct Node* partition(struct Node *l, struct Node *h) 
{ 
    // set pivot as h element 
    int x = h->data; 

    // similar to i = l-1 for array implementation 
    struct Node *i = l->prev; 

    // Similar to "for (int j = l; j <= h- 1; j++)" 
    for (struct Node *j = l; j != h; j = j->next) 
    { 
        if (j->data <= x) 
        { 
            // Similar to i++ for array 
            i = (i == NULL) ? l : i->next; 

            swap(&(i->data), &(j->data)); 
        } 
    } 
    i = (i == NULL) ? l : i->next; // Similar to i++ 
    swap(&(i->data), &(h->data)); 
    return i; 
} 

/* A recursive implementation of quicksort for linked list */
void _quickSort(struct Node* l, struct Node *h) 
{ 
    if (h != NULL && l != h && l != h->next) 
    { 
        struct Node *p = partition(l, h); 
        _quickSort(l, p->prev); 
        _quickSort(p->next, h); 
    } 
} 

// The main function to sort a linked list. 
// It mainly calls _quickSort() 
void quickSort(struct Node *head) 
{ 
    // Find last node 
    struct Node *h = lastNode(head); 

    // Call the recursive QuickSort 
    _quickSort(head, h); 
}

Любой мой подход не сработал, любая помощь будет оценена, спасибо !!!!!!

1 Ответ

0 голосов
/ 01 марта 2020 
// set pivot as h element 
int x = h->data;

Установить pivot в качестве нижнего элемента, то есть первого элемента, здесь: 

int x = l->data;
...