Միակապ ցուցակի կարգավորումը (Insertion sort)

Վերջերս մի հարցազրույցի ժամանակ խնդիր առաջադրվեց C լեզվով իրականացնել միակապ ցուցակի (singly linked list) կարգավորման ալգորիթմը՝ անպայման ռեկուրսիայի օգտագործմամբ։ Ես ընտրեցի տեղադրումով կարգավորման (insertion sort) մեթոդը։ Ստորև ներկայացնում եմ դա։

Նախ՝ ցուցակի հանգույցի (node) սահմանումը, որտեղ բանալին double տիպի է․

typedef struct _node node;
struct _node {
    double data; /* բանալի */
    node* next;  /* կապ */
};

Հիմա տեղադրումով կարգավորման մասին։ Ալգորիթմի էությունն այն է, որ ամեն մի քայլում հերթական տարրը (իմ դեպքում՝ հանգույցը) տեղադրվում է իր ճիշտ տեղում։ Բնականաբար բուն տեղադրման գործողությունը կարևոր գործողություն է։ Սահմանում եմ insert_into() ֆունկցիան, որը տրված հանգույցը տեղադրում է տրված ցուցակի իր ճիշտ տեղում և վերադարձնում է ձևաձոխված ցուցակը։

node* insert_into( node* n, node* l )
{
    /* եթե ցուցակը դատարկ է, ապա տրված հանգույցը 
       վերադարձնել որպես կարգավորված ցուցակ */
    if( NULL == l ) {
        n->next = NULL;
        return n;
    }

    /* եթե տրված հանգույցի բանալին փոքր է տրված ցուցակի 
       առաջին հանգույցի բանալու արժեքից, ապա տրված 
       հանգույցը կցել ցուցակի սկզբից */
    if( n->data <= l->data ) {
        n->next = l;
        return n;
    }

    /* ռեկուրսիվ կանչով տրված հանգույցը տեղադրել ցոցակի 
       պոչի մեջ, ապա նախնական ցուցակի առաջին հանգույցը 
       կապել ձևափոխված պոչին */
    l->next = insert_into(n, l->next);
    return l;
}

Ցուցակը կարգավորող sort_list() ֆունկցիան պարզապես կանչում է insert_into() ֆունկցիան․

node* sort_list( node* l )
{
    /* ցուցակը դատարկ լինելու դեպքը */
    if( NULL == l )
        return NULL;

    /* ցուցակի առաջին հանգույցը տեղադրել կարգավորված 
       պոչի մեջ՝ ճիշտ տեղում */
    return insert_into(l, sort_list(l->next));
}

Այսքանը։