0

I want to sort the data in a linked list by Quicksort . Here is my code:

struct stu
{

    int id; 
    char name[100]; 
    int score; 
    stu* next;
}head;

int address(stu* StudentList)
{

    //return the index of data
    int index = 0;
    stu* test = head;
    for (index = 0; test != StudentList; temp++)
    {
        test = test->next;
    }
    return index;
}

stu* section(int low)
{

    //Classification discussion on data
    stu* StudentList1=head;
    for (int i = 0; i < low; i++)
    {
        StudentList1 = StudentList1->next;
    }
    return StudentList1;
}

void swap(stu *Student1,stu *Student2)
{

    int t_id = 0, t_score = 0;
    char t_name[10] = "000";
    //exchange id 
    t_id = Student1->id;
    Student1->id = Student2->id;
    Student2->id = t_id;
    //exchange name
    strcpy(t_name, Student1->name);
    strcpy(Student1->name, Student2->name);
    strcpy(Student2->name, t_name);
    //exchange score
    t_score = Student1->score;
    Student1->score = Student2->score;
    Student2->score = t_score;
}

void sort(int low, int high)
{

    stu* StudentList1 = head, * StudentList2 = StudentList1->next;
    if (low >= high)
        return;
    else 
    {
        StudentList1=section(low);
        StudentList2 = StudentList1->next;
        stu* key = StudentList1;
        int i;
        for (int i = 0; i <= (high - low) && StudentList2 != NULL; i++)
        {
            if (StudentList2->score >= key->score)
            {
                StudentList1 = StudentList1->next;
                swap(StudentList1, StudentList2);
            }
            StudentList2 = StudentList2->next;
        }
        swap(key, StudentList1);
        int temp = address(StudentList1);
        StudentList2 = head;
        for (i = 0; StudentList2->next!=NULL;StudentList2=StudentList2->next)
        {
            if (StudentList2->next->score <= StudentList2->score)
            {
                i++;
            }
        }
        high = temp - 1;
        low = temp + 1;
        if (i < num - 1)
        {
            sort(0, high);
            sort(low, num - 1);
        }
        return;
    } 
}

The problem is the The program is in a infinite loop . I tried to modify it but it didn't help . So I have to turn into Stackoverflow . Thank you !

I just modified my code . But there are still some problems . When processing 7 data , the program can run well . However , when processing 8 data , the compiler told me stack overflow in "section" . Hope that you can point out the problems . Thank you sincerely !

XinChen1899
  • 1
  • 1
  • 2
  • Assigning to a function's (non-reference) parameters has no effect outside the function. There is nothing special about pointers. – molbdnilo Mar 21 '20 at 10:50
  • I strongly advise you to copy your data structure in a `std::vector`, sort the vector with `std::sort`, and then build a new linked list from the sorted vector. This should be much faster although is require a more memory. Moreover, prefer using `std::list` than handmade linked lists. Finally, `std::list` contains a [sort](https://en.cppreference.com/w/cpp/container/list/sort) method that do what you want. – Jérôme Richard Mar 21 '20 at 12:04
  • @JérômeRichard - Visual Studio 2015 and later versions switched from a bottom up merge sort using a small array of list to using iterators to keep track of run boundaries while moving nodes within the original list to avoid allocation issue with the side benefit that if a user's compare throws an exception, the list is re-ordered but no data is lost. However, there was a needless change to top down merge sort which can be up to 40% slower than bottom up. You can read more about this in [this answer](https://stackoverflow.com/questions/40622430/40629882#40629882) . – rcgldr Mar 21 '20 at 13:07
  • @JérômeRichard - for a single linked list, implementing splice (to move a node within a list) is difficult (it would have to keep track of previous nodes). So a bottom up merge sort for linked lists using an array of pointers to the first nodes of sub-lists, such as this [wiki example](https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists), would work Still as you commented, it would be faster to copy the linked list to an array or vector, then create a new list from the array or vector. – rcgldr Mar 21 '20 at 13:14

1 Answers1

0

One potential issue is this line:

            sort(0, high);

The recursive calls should always be at least one node less than sort(lo, hi). There may be other issues.

Assuming this is a class assignment, I'm not sure why quicksort was chosen as a method for sorting a linked list, when merge sort is normally used. There is also the choice of "sorting" a linked list by rearranging the data in the nodes, versus sorting by reordering the nodes within a linked list. Since the question doesn't specify the assignment requirements, I can't be sure what the goal is here.

Using indexing for a linked list is inefficient. You could use pointer based quicksort such as:

void QuickSort(stu * lo, stu * hi);

Here is an a variation of Lomuto partition scheme that can be converted to sort a linked list, where lo, hi, i, j, k would be converted to pointers to node.

void QuickSort(int a[], int lo, int hi);

void QuickSort(int a[])
{
    int lo = 0;
    int hi = sizeof(a)/sizeof(a[0])-1;
    if(lo >= hi)
        return;
    QuickSort(a, lo, hi);
}

void QuickSort(int a[], int lo, int hi)
{
    int p = a[lo];
    int i = lo;
    int j = lo;
    int k;
    for(k = lo+1; k <= hi; k++){
        if(a[k] < p){
            j = i++;
            std::swap(a[k], a[i]);
        }
    }
    std::swap(a[i], a[lo]);
    if(j != lo)
        QuickSort(a, lo, j);
    if(i != hi)
        QuickSort(a, i+1, hi);
}

You could also consider a quicksort like method, that creates 3 lists with each level of recursion, sorting nodes instead of swapping data. The 3 lists would be nodes < pivot, nodes == pivot, nodes > pivot. Recursion would be used on the 2 lists with nodes != pivot, then the 3 lists would be concatenated.

rcgldr
  • 27,407
  • 3
  • 36
  • 61