체인 테이블 빠른 정렬

체인 테이블 빠른 정렬
대체적인 사상은 하나의 지침수 그룹을 통해 일반적인 수 그룹으로 전환하여 신속하게 정렬하고 마지막에 체인 테이블을 다시 정리하는 것이다.

#include <iostream>

#include <vector>

using namespace std;



typedef struct NODE{

    int data;

    NODE* next;

    NODE(int _data) : data(_data), next(nullptr){}

}NODE;



NODE* createLinkTable()

{

    const int tableLen = 10;

    const int testArray[tableLen] = { 12, 32, 0, 45, 2, 78, 34, 8, 365, 7 };

    NODE* root = new NODE(testArray[0]);

    NODE* prev = root;

    for (int i = 1; i < tableLen; i++)

    {

        NODE* cur = new NODE(testArray[i]);

        prev->next = cur;

        prev = cur;

    }

    return root;

}

void destroyLinkTable(NODE* table)

{

    NODE* iter = table;

    while (iter)

    {

        NODE* next = iter->next;

        delete iter;

        iter = next;

    }

}

void sortLinkTable(vector<NODE*>& linkVec,const int left,const int right)

{

    if (left >= right)

    {

        return;

    }

    NODE* flag = linkVec[right];

    int leftIter = left;

    int rightIter = left;

    for (int i = left; i < right-1; i++)

    {

        if (linkVec[i]->data < flag->data)

        {

            swap(linkVec[leftIter], linkVec[i]);

            leftIter++;

        }

        else{

            rightIter++;

        }

    }

    if (linkVec[leftIter]->data > linkVec[right]->data)

    {

        swap(linkVec[leftIter], linkVec[right]);

    }



    sortLinkTable(linkVec, left, leftIter-1);

    sortLinkTable(linkVec, leftIter + 1, right);

}

NODE* rebuildLinkTable(vector<NODE*>& linkVec)

{

    NODE* root = linkVec[0];

    NODE* prev = root;

    for (size_t i = 1; i < linkVec.size(); i++)

    {

        prev->next = linkVec[i];

        prev = linkVec[i];

    }

    prev->next = nullptr;



    return root;

}

NODE* sortLinkTable(NODE* table)

{

    vector<NODE*> linkVec;

    NODE* cur = table;

    while (cur)

    {

        linkVec.push_back(cur);

        cur = cur->next;

    }

    sortLinkTable(linkVec, 0, linkVec.size()-1);

    return rebuildLinkTable(linkVec);

}

void displayLinkTable(const NODE* const table)

{

    const NODE* iter = table;

    while (iter)

    {

        cout << iter->data << " ";

        iter = iter->next;

    }

    cout << endl;

}

int main(int argc, char* argv[])

{

    NODE* table = createLinkTable();

    if (!table)

    {

        return -1;

    }

    displayLinkTable(table);

    table = sortLinkTable(table);

    displayLinkTable(table);

    destroyLinkTable(table);

    return 0;

}