ডেটা স্ট্রাকচার এবং অ্যালগরিদম কম্পিউটার বিজ্ঞান এবং সফটওয়্যার ডেভেলপমেন্টের মূল ভিত্তি। এগুলি প্রোগ্রামিংয়ের দক্ষতা বৃদ্ধির জন্য অত্যন্ত গুরুত্বপূর্ণ, কারণ সঠিক ডেটা স্ট্রাকচার এবং অ্যালগরিদম নির্বাচন প্রোগ্রামের কার্যকারিতা, গতি এবং ব্যবহারের সহজতা বাড়াতে সহায়তা করে।
ডেটা স্ট্রাকচার (Data Structures)
ডেটা স্ট্রাকচার হলো একটি নির্দিষ্ট পদ্ধতিতে ডেটা সংরক্ষণের এবং পরিচালনা করার উপায়। এটি ডেটার একটি সংগঠিত ফরম্যাট যেখানে ডেটা সহজে অ্যাক্সেস, সম্পাদনা, ম্যানিপুলেট এবং ম্যানেজ করা যায়। ডেটা স্ট্রাকচার বিভিন্ন ধরণের হতে পারে, যেমন:
১. অ্যারের (Array)
- একটি অ্যারে হলো এক ধরনের ডেটা স্ট্রাকচার যেখানে একধরনের ডেটা একটি ধারাবাহিক ব্লকে সংরক্ষিত থাকে।
- অ্যারে ইন্ডেক্সিংয়ের মাধ্যমে দ্রুত অ্যাক্সেস প্রদান করে।
- সীমাবদ্ধতা: এর আকার ফিক্সড থাকে এবং একবার সেট করার পরে পরিবর্তন করা সম্ভব নয়।
উদাহরণ:
var
arr: array[1..5] of Integer;
begin
arr[1] := 10;
arr[2] := 20;
writeln(arr[1]); // আউটপুট: 10
end.২. লিঙ্কড লিস্ট (Linked List)
- লিঙ্কড লিস্ট হলো একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি এলিমেন্ট একটি নোডে থাকে এবং প্রতিটি নোডের মধ্যে পরবর্তী নোডের রেফারেন্স থাকে।
- এতে ডেটার সংরক্ষণ এবং পরিবর্তন সহজ হলেও অ্যাক্সেসের জন্য শুরু থেকে শেষ পর্যন্ত যেতে হয়, যা কিছুটা ধীরগতি হতে পারে।
উদাহরণ:
type
PNode = ^TNode;
TNode = record
data: Integer;
next: PNode;
end;
var
head: PNode;
begin
New(head);
head^.data := 10;
head^.next := nil;
writeln(head^.data); // আউটপুট: 10
end.৩. স্ট্যাক (Stack)
- স্ট্যাক একটি LIFO (Last In First Out) ডেটা স্ট্রাকচার। এর মধ্যে শুধুমাত্র সর্বশেষ যোগ করা আইটেমটি প্রথমে বের করা যায়।
- স্ট্যাক সাধারণত ফাংশনের কল স্ট্যাক, ব্যাকট্র্যাকিং বা অভ্যন্তরীণ মেমরি ব্যবস্থাপনায় ব্যবহৃত হয়।
উদাহরণ:
type
TStack = array[1..10] of Integer;
var
stack: TStack;
top: Integer;
begin
top := 0;
Inc(top);
stack[top] := 5;
writeln(stack[top]); // আউটপুট: 5
end.৪. কিউ (Queue)
- কিউ একটি FIFO (First In First Out) ডেটা স্ট্রাকচার। এর মধ্যে প্রথমে যোগ করা আইটেমটি প্রথমে বের করা হয়।
- কিউ সাধারণত প্রসেসিং বা ইভেন্ট ম্যানেজমেন্টে ব্যবহৃত হয়।
উদাহরণ:
type
TQueue = array[1..10] of Integer;
var
queue: TQueue;
front, rear: Integer;
begin
front := 0;
rear := 0;
Inc(rear);
queue[rear] := 10;
writeln(queue[rear]); // আউটপুট: 10
end.অ্যালগরিদম (Algorithms)
অ্যালগরিদম হলো একটি নির্দিষ্ট সমস্যার সমাধান দেওয়ার জন্য স্টেপ বাই স্টেপ নির্দেশনা। এটি কোনো নির্দিষ্ট সমস্যা সমাধানের জন্য একটি সুসংগঠিত প্রক্রিয়া। অ্যালগরিদমগুলি বিভিন্ন ধরণের হতে পারে এবং সাধারণত কার্যকারিতা এবং দক্ষতার ভিত্তিতে নির্বাচন করা হয়।
১. সার্চিং অ্যালগরিদম (Searching Algorithms)
- সার্চিং অ্যালগরিদমগুলি একটি ডেটা স্ট্রাকচারে নির্দিষ্ট ডেটা অনুসন্ধান করতে ব্যবহৃত হয়। দুইটি জনপ্রিয় সার্চিং অ্যালগরিদম হলো:
- লিনিয়ার সার্চ (Linear Search): এটি অ্যারের সব আইটেম পরীক্ষা করে ডেটা খুঁজে পায়।
- বাইনারি সার্চ (Binary Search): এটি সাজানো অ্যারেতে সেন্ট্রাল এলিমেন্ট পরীক্ষা করে এবং ডেটা দ্রুত খুঁজে পায়।
উদাহরণ: লিনিয়ার সার্চ
function LinearSearch(arr: array of Integer; key: Integer): Integer;
var
i: Integer;
begin
for i := 0 to High(arr) do
if arr[i] = key then
exit(i);
result := -1; // Not found
end;২. সোর্টিং অ্যালগরিদম (Sorting Algorithms)
- সোর্টিং অ্যালগরিদমগুলি একটি ডেটা স্ট্রাকচারের এলিমেন্টগুলোকে সাজানোর জন্য ব্যবহৃত হয়। কিছু জনপ্রিয় সোর্টিং অ্যালগরিদম হলো:
- বাবল সোর্ট (Bubble Sort): এটি একে একে সন্নিবেশ করে সজ্জিত করে।
- কুইক সোর্ট (Quick Sort): এটি পিভট এলিমেন্ট ব্যবহার করে ডেটা দ্রুত সজ্জিত করে।
উদাহরণ: সিম্পল বাবল সোর্ট
procedure BubbleSort(var arr: array of Integer);
var
i, j, temp: Integer;
begin
for i := 0 to High(arr) - 1 do
for j := 0 to High(arr) - 1 - i do
if arr[j] > arr[j + 1] then
begin
temp := arr[j];
arr[j] := arr[j + 1];
arr[j + 1] := temp;
end;
end;৩. ডাইনামিক প্রোগ্রামিং (Dynamic Programming)
- ডাইনামিক প্রোগ্রামিং একটি অ্যালগরিদম টেকনিক যা সমস্যা সমাধান করতে ছোট ছোট উপসমস্যাগুলির সমাধান ব্যবহার করে। এটি মূলত পুনরাবৃত্তি সমাধানের জন্য ব্যবহৃত হয়।
উদাহরণ: ফিবোনাচি সিরিজ
function Fibonacci(n: Integer): Integer;
var
fib: array[0..100] of Integer;
i: Integer;
begin
fib[0] := 0;
fib[1] := 1;
for i := 2 to n do
fib[i] := fib[i - 1] + fib[i - 2];
result := fib[n];
end;ডেটা স্ট্রাকচার এবং অ্যালগরিদমের মধ্যে সম্পর্ক
ডেটা স্ট্রাকচার এবং অ্যালগরিদমের মধ্যে একটি গভীর সম্পর্ক রয়েছে। ডেটা স্ট্রাকচার এমনভাবে ডিজাইন করা হয় যাতে অ্যালগরিদমগুলো আরও কার্যকরভাবে এবং দক্ষতার সাথে কাজ করতে পারে। উদাহরণস্বরূপ, একটি সঠিক সোর্টিং অ্যালগরিদম শুধুমাত্র তখনই দ্রুত কাজ করবে যদি ডেটা সঠিকভাবে সাজানো থাকে।
সারাংশ
ডেটা স্ট্রাকচার এবং অ্যালগরিদম সফটওয়্যার ডেভেলপমেন্টের জন্য অত্যন্ত গুরুত্বপূর্ণ বিষয়। ডেটা স্ট্রাকচার যেমন অ্যারে, লিঙ্কড লিস্ট, স্ট্যাক এবং কিউ আপনাকে ডেটা সঠিকভাবে সংরক্ষণ এবং ম্যানিপুলেট করতে সাহায্য করে, আর অ্যালগরিদমগুলি সেই ডেটার উপর কাজ করার পদ্ধতিগুলি নির্ধারণ করে। দক্ষ ডেটা স্ট্রাকচার এবং অ্যালগরিদম নির্বাচন করলে প্রোগ্রামের গতি, কার্যকারিতা এবং রক্ষণাবেক্ষণ ক্ষমতা বৃদ্ধি পায়।
এখানে আমরা Linked Lists, Stacks, এবং Queues তৈরি করতে শিখব। এই তিনটি ডেটা স্ট্রাকচার প্রোগ্রামিংয়ে সাধারণত ব্যবহৃত হয়, এবং তারা নিজেদের মধ্যে কিছু গুরুত্বপূর্ণ পার্থক্য রাখে। প্যাসক্যাল ভাষায় তাদের বাস্তবায়ন কিভাবে করা যায়, তা দেখব।
১. Linked List
Linked List একটি ডেটা স্ট্রাকচার যেখানে প্রতিটি উপাদান (নোড) একটি ডেটা এবং পরবর্তী নোডের রেফারেন্স (পয়েন্টার) ধারণ করে। এটি একটি সিকুয়েন্স্যাল ডেটা স্ট্রাকচার, কিন্তু প্রতিটি নোড একে অপরের সাথে সম্পর্কিত থাকে।
Linked List এর গঠন:
প্রতিটি নোডের মধ্যে দুটি অংশ থাকে:
- ডেটা: নোডের মূল মান।
- পয়েন্টার: পরবর্তী নোডের ঠিকানা।
প্যাসক্যাল কোড:
program LinkedListExample;
type
Node = ^NodeRec;
NodeRec = record
data: Integer;
next: Node;
end;
var
head: Node;
procedure InsertFront(var head: Node; value: Integer);
var
newNode: Node;
begin
New(newNode); { নতুন নোড তৈরি }
newNode^.data := value;
newNode^.next := head; { পরবর্তী নোডকে প্রাক্তন হেডের রেফারেন্সে সংযুক্ত করুন }
head := newNode; { হেড পয়েন্টার আপডেট করুন }
end;
procedure PrintList(head: Node);
var
temp: Node;
begin
temp := head;
while temp <> nil do
begin
writeln(temp^.data);
temp := temp^.next;
end;
end;
begin
head := nil;
InsertFront(head, 10);
InsertFront(head, 20);
InsertFront(head, 30);
writeln('Linked List:');
PrintList(head);
end.আউটপুট:
Linked List:
30
20
10এখানে, InsertFront ফাংশনটি লিঙ্কড লিস্টের শুরুতে নতুন নোড যোগ করে এবং PrintList ফাংশনটি লিঙ্কড লিস্টের সমস্ত উপাদান প্রিন্ট করে।
২. Stack
Stack একটি লিনিয়ার ডেটা স্ট্রাকচার যা LIFO (Last In, First Out) পদ্ধতিতে কাজ করে। অর্থাৎ, সর্বশেষে ঢোকানো উপাদানটি প্রথমে বের হবে।
প্যাসক্যাল কোড:
program StackExample;
type
Stack = record
arr: array[1..10] of Integer;
top: Integer;
end;
procedure InitStack(var s: Stack);
begin
s.top := 0; { স্ট্যাকটি শূন্য অবস্থায় শুরু করুন }
end;
procedure Push(var s: Stack; value: Integer);
begin
if s.top < 10 then
begin
s.top := s.top + 1;
s.arr[s.top] := value;
end
else
writeln('Stack is full');
end;
function Pop(var s: Stack): Integer;
begin
if s.top > 0 then
begin
Pop := s.arr[s.top];
s.top := s.top - 1;
end
else
begin
writeln('Stack is empty');
Pop := -1;
end;
end;
begin
var myStack: Stack;
InitStack(myStack);
Push(myStack, 10);
Push(myStack, 20);
Push(myStack, 30);
writeln('Popped: ', Pop(myStack));
writeln('Popped: ', Pop(myStack));
writeln('Popped: ', Pop(myStack));
writeln('Popped: ', Pop(myStack)); { Stack is empty }
end.আউটপুট:
Popped: 30
Popped: 20
Popped: 10
Stack is emptyএখানে, Push ফাংশনটি স্ট্যাকে নতুন উপাদান যোগ করে এবং Pop ফাংশনটি সর্বশেষ উপাদানটি সরিয়ে নেয় (LIFO অনুযায়ী)।
৩. Queue
Queue একটি লিনিয়ার ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতিতে কাজ করে। অর্থাৎ, প্রথমে ঢোকানো উপাদানটি প্রথমে বের হবে।
প্যাসক্যাল কোড:
program QueueExample;
type
Queue = record
arr: array[1..10] of Integer;
front, rear: Integer;
end;
procedure InitQueue(var q: Queue);
begin
q.front := 0;
q.rear := 0;
end;
procedure Enqueue(var q: Queue; value: Integer);
begin
if q.rear < 10 then
begin
q.rear := q.rear + 1;
q.arr[q.rear] := value;
end
else
writeln('Queue is full');
end;
function Dequeue(var q: Queue): Integer;
begin
if q.front < q.rear then
begin
q.front := q.front + 1;
Dequeue := q.arr[q.front];
end
else
begin
writeln('Queue is empty');
Dequeue := -1;
end;
end;
begin
var myQueue: Queue;
InitQueue(myQueue);
Enqueue(myQueue, 10);
Enqueue(myQueue, 20);
Enqueue(myQueue, 30);
writeln('Dequeued: ', Dequeue(myQueue));
writeln('Dequeued: ', Dequeue(myQueue));
writeln('Dequeued: ', Dequeue(myQueue));
writeln('Dequeued: ', Dequeue(myQueue)); { Queue is empty }
end.আউটপুট:
Dequeued: 10
Dequeued: 20
Dequeued: 30
Queue is emptyএখানে, Enqueue ফাংশনটি কিউতে নতুন উপাদান যোগ করে এবং Dequeue ফাংশনটি প্রথম উপাদানটি সরিয়ে নেয় (FIFO অনুযায়ী)।
সারাংশ
- Linked List: এটি একটি সিকুয়েন্সিয়াল ডেটা স্ট্রাকচার, যেখানে প্রতিটি নোডে একটি ডেটা এবং পরবর্তী নোডের রেফারেন্স থাকে।
- Stack: এটি একটি লিনিয়ার ডেটা স্ট্রাকচার যা LIFO (Last In, First Out) পদ্ধতিতে কাজ করে। শেষের দিকে ঢোকানো উপাদান প্রথমে বের হবে।
- Queue: এটি একটি লিনিয়ার ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতিতে কাজ করে। প্রথমে ঢোকানো উপাদান প্রথমে বের হবে।
এই তিনটি ডেটা স্ট্রাকচার প্রোগ্রামিংয়ের ক্ষেত্রে খুবই গুরুত্বপূর্ণ এবং বিভিন্ন সমস্যার সমাধান করার জন্য ব্যবহৃত হয়।
ট্রি (Tree) এবং বাইনরি সার্চ ট্রি (Binary Search Tree) ডেটা স্ট্রাকচারগুলি কম্পিউটার সায়েন্সে গুরুত্বপূর্ণ। এগুলো হায়ারার্কিক্যাল ডেটা সংগঠনের জন্য ব্যবহৃত হয় এবং বিশেষ করে ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনের জন্য খুবই কার্যকরী।
১. ট্রি (Tree)
একটি ট্রি হলো একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা একটি সেট নোড এবং এদের মধ্যে সংযুক্ত এজ (edges) দিয়ে গঠিত হয়। ট্রি সাধারণত একটি রুট (root) নোড দিয়ে শুরু হয় এবং অন্যান্য নোডগুলি রুটের সাথে সংযুক্ত থাকে।
ট্রি ডেটা স্ট্রাকচারের কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য:
- রুট (Root): ট্রির প্রথম নোড, যেখান থেকে অন্যান্য নোডগুলো শাখা বা উপশাখা হিসেবে বৃদ্ধি পায়।
- লিফ (Leaf): যে নোডগুলির কোন চাইল্ড নোড থাকে না, তাদের লিফ নোড বলা হয়।
- প্যারেন্ট (Parent): একটি নোড যার চাইল্ড নোড থাকে।
- চাইল্ড (Child): যে নোডটি প্যারেন্ট নোডের অধীনে থাকে।
- এজ (Edge): দুটি নোডের মধ্যে সংযোগ।
উদাহরণ:
A
/ \
B C
/ \
D Eএখানে:
Aহলো রুট।BএবংCহলোAএর চাইল্ড।DএবংEহলোBএর চাইল্ড।D,E, এবংCহলো লিফ নোড।
২. বাইনারি ট্রি (Binary Tree)
একটি বাইনারি ট্রি হলো একটি বিশেষ ধরনের ট্রি যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকে। অর্থাৎ, প্রতিটি নোডের দুটি সন্তান থাকতে পারে: একটি বাম (Left) এবং একটি ডান (Right) সন্তান।
উদাহরণ:
A
/ \
B C
/ \
D Eএখানে:
Aহলো রুট নোড।BহলোAএর বাম চাইল্ড এবংCহলোAএর ডান চাইল্ড।DএবংEহলোBএর বাম ও ডান চাইল্ড।
৩. বাইনারি সার্চ ট্রি (Binary Search Tree - BST)
একটি বাইনারি সার্চ ট্রি (BST) হলো একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম সাবট্রি এবং ডান সাবট্রির মধ্যে একটি নির্দিষ্ট নিয়ম থাকে:
- বাম সাবট্রি: একটি নোডের বাম চাইল্ড সাবট্রিতে থাকা সব নোডের মান ঐ নোডের মানের চেয়ে ছোট।
- ডান সাবট্রি: একটি নোডের ডান চাইল্ড সাবট্রিতে থাকা সব নোডের মান ঐ নোডের মানের চেয়ে বড়।
এই নিয়মের কারণে BST-তে ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনগুলো খুব দ্রুত সম্পন্ন করা যায়। সাধারণত O(log n) সময়ে এই অপারেশনগুলো সম্পন্ন করা সম্ভব হয়।
উদাহরণ:
10
/ \
5 15
/ \ \
2 7 20এখানে:
10হলো রুট নোড।- বাম সাবট্রিতে (5, 2, 7) এর মানগুলি
10এর চেয়ে ছোট, আর ডান সাবট্রিতে (15, 20) এর মানগুলি10এর চেয়ে বড়।
এটি বাইনারি সার্চ ট্রির একটি উদাহরণ।
৪. BST এর মূল অপারেশন
BST-তে কিছু প্রধান অপারেশন রয়েছে যা গুরুত্বপূর্ণ ডেটা ম্যানিপুলেশনে ব্যবহৃত হয়। এগুলি হলো:
- ইনসার্ট (Insert):
- BST-তে নতুন নোড যোগ করার সময়, নতুন নোডটি সঠিক স্থানে বসাতে হয় যাতে ট্রির নিয়ম বজায় থাকে। মানের তুলনায় ছোট হলে বাম সাবট্রিতে এবং বড় হলে ডান সাবট্রিতে যুক্ত হয়।
- অনুসন্ধান (Search):
- BST-তে অনুসন্ধান করা সহজ, কারণ প্রতি নোডের বাম ও ডান সাবট্রির মধ্যে নিয়মিত অবস্থান থাকে। প্রতিটি নোডে গিয়ে আপনি খুঁজতে পারেন যে নোডটি কোথায় অবস্থিত। এটির গড় সময় জটিলতা O(log n) হয়।
- ডিলিট (Delete):
- BST-তে ডিলিট অপারেশন তিনটি ক্ষেত্রে বিভক্ত হতে পারে:
- কেস ১: যদি মুছে ফেলা নোডের কোন চাইল্ড না থাকে, তাহলে শুধু নোডটি মুছে ফেলতে হবে।
- কেস ২: যদি একটি চাইল্ড থাকে, তাহলে চাইল্ডটি সরাসরি নোডের জায়গায় বসিয়ে দেওয়া হয়।
- কেস ৩: যদি দুটি চাইল্ড থাকে, তাহলে নোডের ডান বা বাম সাবট্রি থেকে সর্বনিম্ন (বা সর্বোচ্চ) মানের নোডটি খুঁজে এনে তা মুছে ফেলা নোডের জায়গায় বসানো হয়।
- BST-তে ডিলিট অপারেশন তিনটি ক্ষেত্রে বিভক্ত হতে পারে:
৫. BST-এর সুবিধা ও অসুবিধা
সুবিধা:
- দ্রুত অনুসন্ধান: ডেটা BST-তে সজ্জিত থাকলে অনুসন্ধান, ইনসার্ট, ডিলিট অপারেশনগুলো O(log n) সময়ের মধ্যে সম্পন্ন করা যায়।
- প্রাকৃতিক সাজানো: BST ডেটাকে স্বাভাবিকভাবে সাজায়, যাতে ইন অর্ডার ট্রাভার্সাল করলে সজ্জিত ডেটা পাওয়া যায়।
অসুবিধা:
- অসামঞ্জস্যপূর্ণ ডেটা: যদি ডেটা সঠিকভাবে সাজানো না থাকে (যেমন একে একে বাড়ানো বা কমানো), তাহলে BST একটি লিনিয়ার স্ট্রাকচারে পরিণত হতে পারে, যার ফলে অপারেশনগুলো O(n) সময় নিতে পারে।
- ব্যালেন্সিং: ব্যালেন্সড না হলে BST-এর কার্যকারিতা কমে যায়, তাই সাধারনত AVL ট্রি বা Red-Black ট্রি ব্যবহার করা হয়।
সারাংশ
- ট্রি একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা নোড এবং এজ দিয়ে গঠিত হয়।
- বাইনারি ট্রি এমন একটি ট্রি যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকে।
- বাইনারি সার্চ ট্রি (BST) এমন একটি বাইনারি ট্রি যা ডেটাকে একটি নির্দিষ্ট নিয়মে সাজায়, যা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনকে দ্রুত করতে সাহায্য করে।
BST ব্যবহৃত হয় দ্রুত ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট করতে, তবে এটি ব্যালেন্সড রাখতে হয় যাতে অপারেশনগুলি দক্ষ থাকে।
সার্চিং এবং সোর্টিং অ্যালগরিদম কম্পিউটার সায়েন্সের অন্যতম গুরুত্বপূর্ণ ধারণা। সার্চিং অ্যালগরিদমে কোনো উপাদান একটি ডেটা সেটে খোঁজা হয়, আর সোর্টিং অ্যালগরিদমে একটি ডেটা সেটকে একটি নির্দিষ্ট ক্রমে সাজানো হয়। এখানে আমরা তিনটি জনপ্রিয় সার্চিং এবং সোর্টিং অ্যালগরিদমের (Bubble Sort, Selection Sort, Merge Sort) বিস্তারিত আলোচনা করব।
১. বব্বল সোর্ট (Bubble Sort)
বব্বল সোর্ট হল একটি সহজতম সোর্টিং অ্যালগরিদম যেখানে উপাদানগুলো পরস্পরের সাথে তুলনা করা হয় এবং যদি তারা সঠিক ক্রমে না থাকে, তবে তাদের অদলবদল করা হয়। এই প্রক্রিয়া পুরো অ্যারে বা লিস্টের মাধ্যমে পুনরাবৃত্তি করা হয় যতক্ষণ না সেগুলো সঠিক ক্রমে সাজানো হয়।
অ্যালগরিদম:
- অ্যারের প্রথম উপাদানটি পরবর্তী উপাদানের সাথে তুলনা করুন।
- যদি প্রথম উপাদানটি বড় হয়, তবে তাদের অবস্থান পরিবর্তন করুন।
- একে একে শেষ উপাদান পর্যন্ত যান।
- এই প্রক্রিয়াটি বারবার চলতে থাকে যতক্ষণ না পুরো অ্যারে সঠিকভাবে সজ্জিত হয়।
উদাহরণ (Bubble Sort):
program BubbleSortExample;
procedure BubbleSort(arr: array of Integer);
var
i, j, temp: Integer;
begin
for i := 0 to High(arr) - 1 do
for j := 0 to High(arr) - i - 1 do
if arr[j] > arr[j + 1] then
begin
temp := arr[j];
arr[j] := arr[j + 1];
arr[j + 1] := temp;
end;
end;
var
arr: array[0..4] of Integer = (5, 2, 9, 1, 5);
begin
BubbleSort(arr);
for var i := 0 to High(arr) do
writeln(arr[i]);
end.আউটপুট:
1
2
5
5
9বব্বল সোর্ট একটি ধীর অ্যালগরিদম, যার সময় জটিলতা হল O(n²), যেখানে n হল অ্যারের আকার।
২. সিলেকশন সোর্ট (Selection Sort)
সিলেকশন সোর্ট অ্যালগরিদমের মূল ধারণা হল যে অ্যারের মধ্যে সর্বনিম্ন উপাদানটি খুঁজে বের করে তা প্রথম অবস্থানে রাখুন, তারপর বাকি অংশের জন্য একই কাজ করুন। এই প্রক্রিয়া শেষ পর্যন্ত সমস্ত উপাদান সঠিকভাবে সাজানোর জন্য পুনরাবৃত্তি করা হয়।
অ্যালগরিদম:
- অ্যারের সর্বনিম্ন উপাদান খুঁজুন।
- ওই উপাদানটি প্রথম উপাদানের সাথে অদলবদল করুন।
- প্রথম উপাদান বাদ দিয়ে বাকি অংশের জন্য এই প্রক্রিয়াটি পুনরাবৃত্তি করুন।
উদাহরণ (Selection Sort):
program SelectionSortExample;
procedure SelectionSort(arr: array of Integer);
var
i, j, minIndex, temp: Integer;
begin
for i := 0 to High(arr) - 1 do
begin
minIndex := i;
for j := i + 1 to High(arr) do
if arr[j] < arr[minIndex] then
minIndex := j;
temp := arr[i];
arr[i] := arr[minIndex];
arr[minIndex] := temp;
end;
end;
var
arr: array[0..4] of Integer = (5, 2, 9, 1, 5);
begin
SelectionSort(arr);
for var i := 0 to High(arr) do
writeln(arr[i]);
end.আউটপুট:
1
2
5
5
9সিলেকশন সোর্ট-এর সময় জটিলতা হল O(n²), এবং এটি বব্বল সোর্টের মতোই একটি ধীর অ্যালগরিদম, তবে কিছু ক্ষেত্রে এটি কার্যকরী হতে পারে।
৩. মার্জ সোর্ট (Merge Sort)
মার্জ সোর্ট হল একটি ডিভাইড এন্ড কনকার অ্যালগরিদম, যেখানে অ্যারের দুটি ভাগে বিভক্ত করা হয় এবং প্রতিটি ভাগকে সঠিকভাবে সাজিয়ে আবার একত্র করা হয়। এটি একটি খুব দ্রুত সোর্টিং অ্যালগরিদম, যার সময় জটিলতা **O(n log n)**।
অ্যালগরিদম:
- অ্যারেকে দুটি অংশে বিভক্ত করুন।
- প্রতিটি অংশে মার্জ সোর্ট প্রয়োগ করুন।
- দুটি সজ্জিত অংশকে একত্র করে একটি সাজানো অ্যারে তৈরি করুন।
উদাহরণ (Merge Sort):
program MergeSortExample;
procedure Merge(var arr: array of Integer; left, right: Integer);
var
mid, i, j, k: Integer;
temp: array of Integer;
begin
if left < right then
begin
mid := (left + right) div 2;
Merge(arr, left, mid);
Merge(arr, mid + 1, right);
SetLength(temp, right - left + 1);
i := left;
j := mid + 1;
k := 0;
while (i <= mid) and (j <= right) do
begin
if arr[i] < arr[j] then
begin
temp[k] := arr[i];
Inc(i);
end
else
begin
temp[k] := arr[j];
Inc(j);
end;
Inc(k);
end;
while i <= mid do
begin
temp[k] := arr[i];
Inc(i);
Inc(k);
end;
while j <= right do
begin
temp[k] := arr[j];
Inc(j);
Inc(k);
end;
for i := 0 to k - 1 do
arr[left + i] := temp[i];
end;
end;
var
arr: array[0..4] of Integer = (5, 2, 9, 1, 5);
begin
Merge(arr, 0, High(arr));
for var i := 0 to High(arr) do
writeln(arr[i]);
end.আউটপুট:
1
2
5
5
9মার্জ সোর্ট-এর সময় জটিলতা হল O(n log n), যা এটি অন্যান্য সিম্পল সোর্টিং অ্যালগরিদমের তুলনায় অনেক দ্রুত।
সারাংশ
| অ্যালগরিদম | সময় জটিলতা (Best) | সময় জটিলতা (Worst) | সময় জটিলতা (Average) | স্থায়িত্ব | বর্ণনা |
|---|---|---|---|---|---|
| বব্বল সোর্ট | O(n) | O(n²) | O(n²) | ইন-প্লেস | সহজ, কিন্তু ধীর |
| সিলেকশন সোর্ট | O(n²) | O(n²) | O(n²) | ইন-প্লেস | সহজ, কিন্তু ধীর |
| মার্জ সোর্ট | O(n log n) | O(n log n) | O(n log n) | বাহ্যিক | দ্রুত, ডিভাইড এন্ড কনকার |
বব্বল সোর্ট এবং সিলেকশন সোর্ট সাধারণত ছোট আকারের ডেটা সেটে ব্যবহৃত হয়, কিন্তু মার্জ সোর্ট একটি দ্রুত এবং কার্যকরী পদ্ধতি, যা বড় ডেটা সেটের জন্য উপযুক্ত।
গ্রাফ হলো একটি গাণিতিক কাঠামো যা ভেরটিস (vertices বা nodes) এবং তাদের মধ্যে সম্পর্ক নির্দেশকারী এজেস (edges) দিয়ে গঠিত। গ্রাফ বিভিন্ন ধরনের সম্পর্ক বা সংযোগ প্রদর্শন করতে ব্যবহৃত হয়, যেমন রাস্তা, নেটওয়ার্ক, সোসাল মিডিয়া সংযোগ ইত্যাদি। গ্রাফ প্রোগ্রামিং বা অ্যালগরিদম ডিজাইনে অত্যন্ত গুরুত্বপূর্ণ এবং এটি বিভিন্ন সমস্যা সমাধানে ব্যবহার করা হয়।
গ্রাফের মৌলিক উপাদান
১. ভেরটিস (Vertex বা Node):
- একটি গ্রাফের মৌলিক উপাদান, যা তথ্য বা অন্যান্য কোন বস্তু প্রতিনিধিত্ব করে।
২. এজ (Edge):
- দুটি ভেরটিসের মধ্যে সম্পর্ক বা সংযোগ। এজগুলি অভ্যন্তরীণ বা বাহ্যিক হতে পারে, অর্থাৎ এটি দিকনির্দেশিত (directed) বা দিকহীন (undirected) হতে পারে।
৩. ডিগ্রী (Degree):
- একটি ভেরটিসের সাথে যুক্ত এজের সংখ্যা। যদি গ্রাফটি দিকনির্দেশিত হয়, তবে এটি ইনডিগ্রী (incoming edges) এবং আউটডিগ্রী (outgoing edges) হিসেবে বিভক্ত হয়।
গ্রাফের ধরন
১. অবিচ্ছিন্ন গ্রাফ (Connected Graph):
- যেখানে একটি ভেরটিস থেকে অন্য যে কোনো ভেরটিসে পৌঁছানো সম্ভব।
২. অবিচ্ছিন্ন গ্রাফ (Disconnected Graph):
- যেখানে কিছু ভেরটিস অন্য ভেরটিস থেকে আলাদা, অর্থাৎ কিছু ভেরটিসে পৌঁছাতে অন্য ভেরটিসের মধ্য দিয়ে যাওয়া সম্ভব নয়।
৩. দিকনির্দেশিত গ্রাফ (Directed Graph):
- এখানে প্রতিটি এজ একটি দিক নির্দেশ করে। উদাহরণস্বরূপ, এক ভেরটিস থেকে অন্য ভেরটিসে যোগাযোগ।
- দিকহীন গ্রাফ (Undirected Graph):
- এখানে এজগুলির কোনো নির্দিষ্ট দিক নেই, অর্থাৎ একটি ভেরটিস থেকে অন্য ভেরটিসে যোগাযোগ দুই দিকেই হতে পারে।
গ্রাফ ট্র্যাভার্সাল টেকনিক্স
গ্রাফ ট্র্যাভার্সাল হল গ্রাফের প্রতিটি ভেরটিস পরিদর্শন করার প্রক্রিয়া। এই প্রক্রিয়ায় সাধারণত দুটি প্রধান ট্র্যাভার্সাল টেকনিক ব্যবহার করা হয়:
BFS (Breadth-First Search):
- BFS হল একটি সারি (queue)-ভিত্তিক ট্র্যাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমটি প্রথমে গ্রাফের এক ভেরটিস (যে কোন একটি) থেকে শুরু করে তার সব সরাসরি প্রতিবেশী ভেরটিসগুলোকে পরিদর্শন করে, এবং তারপর প্রতিবেশীদের প্রতিবেশী, এবং এভাবে পরবর্তী স্তরের ভেরটিসগুলিকে পরিদর্শন করে। এটি স্তরভিত্তিক (level-order) ট্র্যাভার্সাল।
BFS অ্যালগরিদমের পদক্ষেপ:
- প্রথমে, একটি ভিজিটেড (visited) অ্যারে বা সেট তৈরি করুন এবং গ্রাফের স্টার্টিং ভেরটিসটি ভিজিটেড হিসেবে চিহ্নিত করুন।
- একটি কিউতে স্টার্টিং ভেরটিসটি যুক্ত করুন।
- কিউ থেকে একটি ভেরটিস বের করুন, সেই ভেরটিসের সকল অজানা প্রতিবেশীকে কিউতে যুক্ত করুন এবং ভিজিটেড হিসেবে চিহ্নিত করুন।
- কিউ খালি না হওয়া পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।
উদাহরণ (BFS):
procedure BFS(graph: array of array of integer; start: integer); var queue: array[1..100] of integer; visited: array[1..100] of boolean; front, rear, i, v: integer; begin front := 1; rear := 1; visited[start] := True; queue[rear] := start; writeln('BFS Traversal: '); while front <= rear do begin v := queue[front]; front := front + 1; write(v, ' '); for i := 1 to length(graph[v]) do begin if not visited[graph[v][i]] then begin visited[graph[v][i]] := True; rear := rear + 1; queue[rear] := graph[v][i]; end; end; end; writeln; end;DFS (Depth-First Search):
- DFS হল একটি স্ট্যাক (stack)-ভিত্তিক ট্র্যাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমটি একটি ভেরটিস থেকে শুরু করে যতদূর সম্ভব গভীরভাবে (depth-first) যাবে এবং যখন আর গভীরে যাওয়া সম্ভব হবে না, তখন পিছিয়ে এসে পরবর্তী ভেরটিসের দিকে যাবে।
DFS অ্যালগরিদমের পদক্ষেপ:
- একটি ভিজিটেড অ্যারে বা সেট তৈরি করুন এবং গ্রাফের স্টার্টিং ভেরটিসটি ভিজিটেড হিসেবে চিহ্নিত করুন।
- স্ট্যাক থেকে একটি ভেরটিস বের করুন, তার সকল অজানা প্রতিবেশীকে স্ট্যাকে যুক্ত করুন এবং ভিজিটেড হিসেবে চিহ্নিত করুন।
- স্ট্যাক খালি না হওয়া পর্যন্ত এই প্রক্রিয়া চালিয়ে যান।
উদাহরণ (DFS):
procedure DFS(graph: array of array of integer; v: integer; visited: array of boolean); var i: integer; begin visited[v] := True; writeln(v); for i := 1 to length(graph[v]) do begin if not visited[graph[v][i]] then DFS(graph, graph[v][i], visited); end; end;
BFS এবং DFS এর মধ্যে পার্থক্য
| বৈশিষ্ট্য | BFS (Breadth-First Search) | DFS (Depth-First Search) |
|---|---|---|
| অ্যালগরিদম টাইপ | স্তরভিত্তিক (Level-order) | গভীরতা-ভিত্তিক (Depth-first) |
| ডেটা স্ট্রাকচার | সারি (Queue) | স্ট্যাক (Stack) |
| পরিদর্শনের প্রক্রিয়া | প্রথমে নিকটবর্তী ভেরটিস পরিদর্শন | প্রথমে গভীরতম ভেরটিস পরিদর্শন |
| ব্যবহৃত হয় | সার্চিং, শাখা-বিষয়ক (level-order) সমস্যা সমাধান | পথ খোঁজা, টপোলজিক্যাল শ্রেণীবিভাগ, গেমস ইত্যাদি |
| অধিকতর কাজ | শাখায় আরও গভীরভাবে প্রবেশ করে না | গভীরে গিয়ে শাখার শেষে সরে আসে |
| চালানো সহজ | সাধারণত সহজ এবং দ্রুত | সময়ের জন্য কমপ্লেক্স, কিন্তু শক্তিশালী |
সারাংশ
গ্রাফ এবং গ্রাফ ট্র্যাভার্সাল অ্যালগরিদমগুলি বিভিন্ন ধরনের সমস্যার সমাধানে গুরুত্বপূর্ণ। BFS (Breadth-First Search) স্তরভিত্তিক পরিদর্শন করে এবং প্রথমে নিকটবর্তী ভেরটিস পরিদর্শন করে, যা সরল এবং দ্রুত হয়। অন্যদিকে, DFS (Depth-First Search) গভীরতায় প্রবেশ করে এবং প্রথমে গভীরতম ভেরটিস পরিদর্শন করে। প্রতিটি অ্যালগরিদমের নিজস্ব সুবিধা এবং ব্যবহার রয়েছে, এবং নির্দিষ্ট সমস্যা অনুযায়ী এগুলোর নির্বাচন করা হয়।
Read more
