৭-৮ঃ Sort Singly Linked List

এবার আমরা লিঙ্কড লিস্ট সর্ট করা দেখব সিলেকশন সর্ট দিয়ে।

আমরা এরে যেভাবে সর্ট করেছিলাম সিলেকশন সর্ট দিয়ে সেইমভাবে আমরা একটি লিঙ্কড লিস্ট ও সর্ট করে ফেলতে পারব। আমরা শুরুতে সিলেকশন সর্ট দিয়ে এরে সর্ট করার কোডটা একটু মনে করি।

for(int i=0;i<n-1;i++)      // নেস্টেড লুপ চালিয়ে প্রতিটি এলিমেন্ট এর সাথে প্রতিটি এলিমেন্ট কম্পেয়ার করা হচ্ছে। 
{
    for(int j=i+1;j<n;j++)
    {
        if(a[i]>a[j])        // যদি পূর্বের ভেলুটি পরের ভেলু থেকে বড় হয়ে যায় তারমানে এরেটি সর্টেড নেই।
        {
            swap(a[i],a[j]);    // তখন আমরা ভেলু দুটো সোয়াপ করে দিচ্ছি যেন সর্টেড হয়ে যায়। 
        }
    }
}

এবার আমরা এই কোডটিকে লিঙ্কড লিস্টে কনভার্ট করি। for(int i=0;i<n-1;i++) int i=0 -> Node *i = head [ এখানে একটি পয়েন্টার নিয়ে তাতে হেড রেখে দিচ্ছি ] i<n-1 -> i->next != NULL [ i<n-1 দিয়ে আমরা লাস্টের আগের ইন্ডেক্স পর্যন্ত যাচ্ছিলাম, i->next != NULL দিয়ে আমরা লাস্টের আগের নোড পর্যন্ত যাচ্ছি ] i++ -> i = i->next [ i++ দিয়ে আমরা ইন্ডেক্স কে সামনে আগাচ্ছিলাম, i = i->next দিয়ে আমরা পয়েন্টার কে নেক্সট নোডে অর্থাৎ সামনে আগাচ্ছি ] int j=i+1 -> Node *j = i->next [ int j=i+1 দিয়ে আমরা নতুন ভেরিয়েবল নিয়েছিলাম যা শুরু হচ্ছিল i এর পরের ইন্ডেক্স থেকে, Node *j = i->next দিয়ে আমরা নতুন পয়েন্টার নিয়েছি যা শুরু হচ্ছে i এর পরের নোড থেকে ] j<n -> j != NULL [ j<n দিয়ে আমরা লাস্ট ইন্ডেক্স পর্যন্ত যাচ্ছিলাম, j != NULL দিয়ে আমরা লাস্ট নোড পর্যন্ত যাচ্ছি ] j++ -> j = j->next [ j++ দিয়ে আমরা ইন্ডেক্স কে সামনে আগাচ্ছিলাম, j = j->next দিয়ে আমরা পয়েন্টার কে নেক্সট নোডে অর্থাৎ সামনে আগাচ্ছি ] a[i],a[j] -> i->val, j->val [ a[i],a[j] দিয়ে আমরা এরেতে i,j ইন্ডেক্সে থাকা ভেলু এক্সেস করছিলাম, i->val, j->val দিয়ে আমরা i,j পয়েন্টারে থাকা ভেলু এক্সেস করছি।

সম্পুরন কোডঃ

#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *next;
    Node(int val)
    {
        this->val = val;
        this->next = NULL;
    }
};
void insert_tail(Node *&head, Node *&tail, int val)
{
    Node *newNode = new Node(val);
    if (head == NULL)
    {
        head = newNode;
        tail = newNode;
        return;
    }
    tail->next = newNode;
    tail = newNode;
}
void print_linekd_list(Node *head)
{
    Node *tmp = head;
    while (tmp != NULL)
    {
        cout << tmp->val << " ";
        tmp = tmp->next;
    }
    cout << endl;
}
int main()
{
    Node *head = NULL;
    Node *tail = NULL;
    int val;
    while (true)
    {
        cin >> val;
        if (val == -1)
            break;
        insert_tail(head, tail, val);
    }
    for (Node *i = head; i->next != NULL; i = i->next)
    {
        for (Node *j = i->next; j != NULL; j = j->next)
        {
            if (i->val < j->val)
            {
                swap(i->val, j->val);
            }
        }
    }
    print_linekd_list(head);
    return 0;
}

ডাটা স্ট্রাকচার কোর্সের গিটবুকগুলো আপনাদের কেমন লাগছে ? আমাদেরকে জানাতে পারেন। https://forms.gle/t3uHWc3mgFRu1iTi8