shellSort

 avatar
unknown
c_cpp
2 years ago
2.9 kB
4
Indexable
    void shellSortLL(customer *head, customer *tail, int &counter)
    {
        int n = 0;
        customer *it = head;
        do
        {
            n++;
            it = it->next;
        } while (it && it != tail->next);

        // cout << "Size of shell sort: " << n << "\n";

        for (int gap = n / 2; gap > 0; gap /= 2)
        {
            customer *temp = head;
            customer *traverseFlag = head;
            while (temp != tail->next)
            {
                traverseFlag = temp;
                bool stop = false;
                for (int j = 0; j < gap; j++)
                {
                    if (!traverseFlag || traverseFlag == tail->next)
                    {
                        stop = true;
                        break;
                    }
                    traverseFlag = traverseFlag->next;
                }

                if (stop || traverseFlag == tail->next)
                    break;

                customer *temp2 = traverseFlag;
                if (temp2)
                    for (int j = 0; j < gap; j++)
                        temp2 = temp2->prev;
                customer *temp3 = traverseFlag;
                while (temp3 && temp2)
                {
                    int c = gap;
                    if (abs(temp3->energy) >= abs(temp2->energy))
                    {
                        if(temp3->energy > temp2->energy){
                            customerSwap(temp3, temp2);
                            counter++;
                        }

                        else if(temp3->energy == temp2->energy){
                            // if temp3 comes first in the customer order list, then swap
                            customer *checkOrder = custormerOrderAllHead;
                            while (checkOrder)
                            {
                                if (checkOrder->name == temp3->name)
                                {
                                    customerSwap(temp3, temp2);
                                    counter++;
                                    break;
                                }
                                else if (checkOrder->name == temp2->name)
                                    break;
                                checkOrder = checkOrder->next;
                            }
                        }
                    }
                    while (c-- && temp2)
                    {
                        temp2 = temp2->prev;
                    }
                    if (!temp2)
                        break;
                    c = gap;
                    while (c-- && temp3)
                        temp3 = temp3->prev;
                    if (!temp3)
                        break;
                }
                temp = temp->next;
            }
        }
    }
Editor is loading...