Selection Sort Doubly linked list use alternative Dlist

  algorithm, c++, data-structures, linked-list

So I’ve tried to use another Dlist instead of swapping data but it failed. Is there anything wrong with my codes. I thought something went wrong in Remove function but I don’t know how to fix

void SelectionSort(DoublyLinkedList &ls)
{
    if(isEmpty(ls))
    {
        cout<<"Emptylist!"<<endl;
        return;
    }
    DoublyLinkedList mylist;
    Initial(mylist);
    Node *p = ls.head;
    while(p != NULL)
    {
        Node *q = FindSmallest(ls);
        InsertLast(mylist, q->data);
        Remove(ls, Find(ls,q->data));
        p = ls.head;
    }
    ls = mylist;
}

My findsmallest function

Node *FindSmallest(DoublyLinkedList ls)
{
    int min;
    Node *r = ls.head;
    Node *q = new Node;
    if(isEmpty(ls))
    {
        cout<<"EmptyList!"<<endl;
        return NULL;
    }
    else
    {
        min = ls.head->data;
        while(r != NULL)
        {
            if(r->data < min)
            {
                min = r->data;
                q = r;
            }
            r = r->next;
        }
    }
    return q;
}

My Insert function

void InsertLast(DoublyLinkedList &ls, int data)
{
    Node *p = CreateNode(data);
    if(p == NULL)
        return;
    if(isEmpty(ls))
    {
        ls.head = ls.tail = p;
    }
    else
    {
        ls.tail->next = p;
        p->prev = ls.tail;
        ls.tail = p;
    }
}

My Remove function at given position

void Remove(DoublyLinkedList &ls, int pos)
{
    if(isEmpty(ls))
    {
        cout<<"EmptyList!"<<endl;
        return;
    }
    else if(pos<=1)
        RemoveFirst(ls);
    else if(pos>size(ls))
        RemoveLast(ls);
    else
    {
        int count = 0;
        Node *p = ls.head;
        Node *q = new Node;
        while(p!= NULL)
        {
            count++;
            q=p;
            if(count==pos)
                break;
            else
                p=p->next;
        }
        q->prev->next = q->next;
        q->next->prev = q->prev;
        delete q;
    }

And Find function return node position

int Find(DoublyLinkedList &ls, int data)
{
    int i=1;
    Node *p = ls.head;
    while(p != NULL)
    {
        if(p->data == data)
           return i;
        else
        {
            i++;
            p = p->next;
        }
    }
    return -1;
}

Source: Windows Questions C++

LEAVE A COMMENT