Как выполнить сортировку выбора в связанном списке?

Question

Я пытаюсь реализовать сортировку выбора в связанном списке. Я хочу, чтобы он выполнялся непосредственно в связанном списке, а не в копии, используя указатели узлов вместо метода индекса массива, который я вставил здесь:

void listClass::selectionsort(int array[], int size)
{
    int startscan, minIndex, minValue;

for (startscan = 0; startscan < (size - 1); startscan++) 
{
    minIndex = startscan;
    minValue = array[startscan];
    for (int index = startscan + 1; index < size; index++) 
    {
        if (array[index] < minValue)
        {
            minValue = array[index];
            minIndex = index;
        }
    }
    array[minIndex] = array[startscan];
    array[startscan] = minValue;
}
}

Как мне настроить эту функцию, чтобы принять мой связанный список? и сортировать это? Я также не хочу использовать какой-либо контейнер STL.

Answer 1

Скажите, что список {90, 13, 5, 12}. Начать указатель с начала.

{* 90, 13, 5, 12}

Найдите самый маленький элемент после указателя и переместите его непосредственно перед указателем.

{5, * 90, 13, 12}

Найдите самый маленький элемент после указателя и переместите его непосредственно перед указателем.

{5, 12, * 90, 13}

Опять же.

{5, 12, 13, * 90}

Опять.

{5, 12, 13, 90}

Указатель заканчивается в конце списка, все готово, список отсортирован.

Answer 2

Здесь C ++ реализация сортировки выбора в связанном списке без STL.Чтобы упростить тестирование программы для различных случаев, эта программа создает связанный список заданного размера со случайными числами.

    //Program to sort a linked list using selection sort.
    #include<stdio.h> 
    #include<time.h>
    #include<cstdlib>
    #define size 10 //Size of linked list.
    struct node
    {
         int info;
         struct node *next;
    }*start=NULL;
    typedef struct node * Node;
    int main()
    {
         int i;
         Node ptr;
         void selectionsort(Node);
         srand(time(NULL));
         for(i=0;i<size;i++)
         {
              Node ptr,temp;
              ptr=(Node)malloc(sizeof(node));
              ptr->info=rand()%100; //Random linked list of given size is created.
              ptr->next=NULL;
              if(start==NULL)
              {
                   start=ptr;
              }
              else
             {     temp=start;
                   while(temp->next!=NULL)
                         temp=temp->next;
                   temp->next=ptr;
             }          
         }
         printf(" Linked List Before Sorting Is -\n");
         ptr=start;
         while(ptr!=NULL)
         {
              printf(" %d ",ptr->info);
              ptr=ptr->next;
         }
         printf("\n Linked List After Sorting Is -\n");
         selectionsort(start);
         ptr=start;
         while(ptr!=NULL)
         {
              printf(" %d ",ptr->info);
              ptr=ptr->next;
         }
         return 0;
    }

    void selectionsort(Node start)
    {
             Node ptr=start,temp,address;
             int var;
             while(ptr->next!=NULL)
             {
                 temp=ptr;
                 address=temp;
                  while(temp!=NULL)
                  {
                        if((address->info)>(temp->info))
                        address=temp;
                        temp=temp->next;
                  }

                  var=address->info;
                  address->info=ptr->info;
                  ptr->info=var;
                  ptr=ptr->next;
            }

    }

Для получения более подробной информации посетите страницу - https://github.com/SahdevKansal02/Data-Structures-And-Algorithms.git