Sorting এবং Searching Techniques (সোর্টিং এবং সার্চিং টেকনিকস)

সোর্টিং (Sorting) এবং সার্চিং (Searching) হল অ্যালগরিদমের দুটি গুরুত্বপূর্ণ ধারণা, যা ডেটার সঠিক অর্ডারে স্থাপন এবং ডেটার মধ্যে নির্দিষ্ট উপাদান খোঁজার জন্য ব্যবহৃত হয়। এই টেকনিকগুলি ডেটার কার্যকরী ব্যবস্থাপনা, অনুসন্ধান এবং অপ্টিমাইজেশন প্রক্রিয়ায় অত্যন্ত গুরুত্বপূর্ণ ভূমিকা পালন করে।

সোর্টিং টেকনিকস (Sorting Techniques)

সোর্টিং অ্যালগরিদমের মাধ্যমে ডেটা একটি নির্দিষ্ট ক্রমে (যেমন, বৃদ্ধি বা হ্রাস) সাজানো হয়। সঠিক সোর্টিং অ্যালগরিদম বেছে নেওয়া খুবই গুরুত্বপূর্ণ, কারণ এর পারফর্ম্যান্স বিভিন্ন পরিস্থিতিতে ভিন্ন হতে পারে। সাধারণত সোর্টিং অ্যালগরিদমের প্রধান লক্ষ্য হলো ডেটাকে দ্রুত এবং দক্ষতার সাথে সাজানো।

১. বুবল সোর্ট (Bubble Sort)

বুবল সোর্ট একটি সহজ সোর্টিং অ্যালগরিদম যা ধারাবাহিকভাবে দুটি উপাদান তুলনা করে এবং সেগুলিকে সঠিক অবস্থানে রেখে যায়। এটি পুনরায় প্রতিটি উপাদান তুলনা করে এবং তাদের মধ্যে স্থানান্তর করে।

সময় জটিলতা: \(O(n^2)\)

উদাহরণ:

def bubbleSort(arr: Array[Int]): Array[Int] = {
  for(i <- arr.indices) {
    for(j <- 0 until arr.length - 1 - i) {
      if(arr(j) > arr(j + 1)) {
        val temp = arr(j)
        arr(j) = arr(j + 1)
        arr(j + 1) = temp
      }
    }
  }
  arr
}

val arr = Array(5, 2, 9, 1, 5, 6)
println(bubbleSort(arr).mkString(", "))

২. সিলেকশন সোর্ট (Selection Sort)

সিলেকশন সোর্টে, প্রতিটি ইটারেশনে সবচেয়ে ছোট উপাদানটি খুঁজে বের করা হয় এবং তারপরে সেই উপাদানটি সঠিক স্থানে স্থানান্তরিত হয়।

সময় জটিলতা: \(O(n^2)\)

উদাহরণ:

def selectionSort(arr: Array[Int]): Array[Int] = {
  for(i <- arr.indices) {
    var minIdx = i
    for(j <- i + 1 until arr.length) {
      if(arr(j) < arr(minIdx)) minIdx = j
    }
    if(minIdx != i) {
      val temp = arr(i)
      arr(i) = arr(minIdx)
      arr(minIdx) = temp
    }
  }
  arr
}

val arr = Array(64, 25, 12, 22, 11)
println(selectionSort(arr).mkString(", "))

৩. ইনসার্টশন সোর্ট (Insertion Sort)

ইনসার্টশন সোর্টে, একটি একটি করে উপাদান নিয়ে সেটিকে সঠিক স্থানে ইনসার্ট করা হয়। এটি প্রাথমিকভাবে ছোট আকারের লিস্টে ভালো কাজ করে।

সময় জটিলতা: \(O(n^2)\)

উদাহরণ:

def insertionSort(arr: Array[Int]): Array[Int] = {
  for(i <- 1 until arr.length) {
    var key = arr(i)
    var j = i - 1
    while(j >= 0 && arr(j) > key) {
      arr(j + 1) = arr(j)
      j -= 1
    }
    arr(j + 1) = key
  }
  arr
}

val arr = Array(12, 11, 13, 5, 6)
println(insertionSort(arr).mkString(", "))

৪. কুইক সোর্ট (Quick Sort)

কুইক সোর্ট একটি বিভাজন এবং বিজয় (Divide and Conquer) অ্যালগরিদম। এটি একটি পিভট উপাদান নির্বাচন করে এবং তারপর তার আশেপাশের উপাদানগুলি পিভটের তুলনায় সঠিক অবস্থানে সরিয়ে দেয়।

সময় জটিলতা: \(O(n \log n)\) (গড় ক্ষেত্রে)

উদাহরণ:

def quickSort(arr: Array[Int]): Array[Int] = {
  if (arr.length <= 1) arr
  else {
    val pivot = arr(arr.length / 2)
    val (left, right) = arr.filter(_ < pivot) -> arr.filter(_ > pivot)
    quickSort(left) ++ arr.filter(_ == pivot) ++ quickSort(right)
  }
}

val arr = Array(10, 80, 30, 90, 40, 50, 70)
println(quickSort(arr).mkString(", "))

সার্চিং টেকনিকস (Searching Techniques)

সার্চিং টেকনিকগুলির মাধ্যমে আমরা একটি নির্দিষ্ট উপাদান খুঁজে বের করি। সবচেয়ে সাধারণ সার্চিং অ্যালগরিদম দুটি হলো লাইনিয়ার সার্চ (Linear Search) এবং বাইনারি সার্চ (Binary Search)। এগুলির কার্যকারিতা বিভিন্ন ধরনের ডেটার উপর নির্ভর করে।

১. লাইনিয়ার সার্চ (Linear Search)

লাইনিয়ার সার্চে, প্রতিটি উপাদান পরপর পরীক্ষা করা হয় যতক্ষণ না আমরা খোঁজা উপাদানটি পেয়ে যাই।

সময় জটিলতা: \(O(n)\)

উদাহরণ:

def linearSearch(arr: Array[Int], target: Int): Int = {
  for(i <- arr.indices) {
    if(arr(i) == target) return i
  }
  -1
}

val arr = Array(2, 3, 4, 10, 40)
println(linearSearch(arr, 10))  // Output: 3

২. বাইনারি সার্চ (Binary Search)

বাইনারি সার্চ একটি ডিভাইড এবং বিজয় (Divide and Conquer) অ্যালগরিদম, যা সিলেক্ট করা অর্ডারড ডেটাসেটে দ্রুত উপাদান খোঁজার জন্য ব্যবহৃত হয়। এটি মধ্যম উপাদানটির সাথে তুলনা করে ডেটার বাকি অংশকে দুটি ভাগে ভাগ করে।

সময় জটিলতা: \(O(\log n)\)

উদাহরণ:

def binarySearch(arr: Array[Int], target: Int): Int = {
  var low = 0
  var high = arr.length - 1
  while(low <= high) {
    val mid = low + (high - low) / 2
    if(arr(mid) == target) return mid
    else if(arr(mid) < target) low = mid + 1
    else high = mid - 1
  }
  -1
}

val arr = Array(2, 3, 4, 10, 40)
println(binarySearch(arr, 10))  // Output: 3

সারাংশ

সোর্টিং এবং সার্চিং টেকনিকস ডেটা ব্যবস্থাপনায় অত্যন্ত গুরুত্বপূর্ণ। সঠিক সোর্টিং এবং সার্চিং অ্যালগরিদমের ব্যবহার ডেটা প্রসেসিং এবং কার্যকারিতার জন্য অত্যন্ত প্রয়োজনীয়। সোর্টিং অ্যালগরিদমগুলি ডেটাকে একটি নির্দিষ্ট অর্ডারে সাজানোর জন্য ব্যবহৃত হয়, এবং সার্চিং অ্যালগরিদমগুলি ডেটার মধ্যে একটি নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। সঠিক অ্যালগরিদম নির্বাচন করলে ডেটা প্রক্রিয়াকরণের গতি এবং কার্যকারিতা উল্লেখযোগ্যভাবে বৃদ্ধি পেতে পারে।

Sorting (সার্টিং) হল একটি ডেটা সংগ্রহের উপাদানগুলিকে একটি নির্দিষ্ট ক্রমে সাজানোর প্রক্রিয়া। স্কালাতে, Collections (কালেকশনস) এর মধ্যে ডেটা সজ্জিত করার জন্য বেশ কিছু সর্টিং টেকনিক ব্যবহৃত হয়। এটি ডেটাকে সহজে বিশ্লেষণ এবং ব্যবস্থাপনা করতে সাহায্য করে। স্কালা কালেকশনস যেমন List, Vector, Set, Map ইত্যাদির উপর বিভিন্ন সার্টিং অপারেশন প্রয়োগ করা যেতে পারে।

স্কালাতে সাধারণত ব্যবহৃত Sorting Techniques:

1. SortBy
   sortBy একটি ফাংশনাল অপারেশন যা এক বা একাধিক মানের ভিত্তিতে এলিমেন্টগুলোকে সাজাতে ব্যবহৃত হয়। এটি একটি কাস্টম ফাংশন গ্রহণ করে এবং সেই ফাংশনের মাধ্যমে উপাদানগুলিকে সাজানোর জন্য নির্দেশনা প্রদান করে।
2. Sorted
   sorted একটি স্ট্যান্ডার্ড ফাংশন যা একটি কালেকশনকে ডিফল্ট কম্প্যারেটর (যেমন, কমপ্যারেবল প্রপার্টি থাকা উপাদানগুলির উপর কাজ করা) ব্যবহার করে সাজায়।
3. SortWith
   sortWith ফাংশনটি একটি কাস্টম কম্প্যারেটর ব্যবহার করে এলিমেন্টগুলো সাজানোর জন্য ব্যবহৃত হয়, যেটি দুইটি উপাদানকে তুলনা করে একটি সজ্জিত ফলাফল তৈরি করে।

উদাহরণ ১: sortBy ব্যবহার

sortBy একটি কালেকশনের উপাদানগুলিকে নির্দিষ্ট ফিল্ড বা কাস্টম ক্রাইটেরিয়ার ভিত্তিতে সাজানোর জন্য ব্যবহৃত হয়।

val numbers = List(5, 2, 9, 1, 5, 6)

// Ascending Order
val sortedNumbers = numbers.sortBy(x => x)
println(sortedNumbers) // List(1, 2, 5, 5, 6, 9)

// Descending Order
val reverseSortedNumbers = numbers.sortBy(x => -x)
println(reverseSortedNumbers) // List(9, 6, 5, 5, 2, 1)

এখানে, sortBy ফাংশনটি x => x (অথবা x => -x এর মাধ্যমে অবলম্বন করে ডেটা সাজিয়েছে।

উদাহরণ ২: sorted ব্যবহার

sorted একটি সাধারণ ফাংশন যা ডিফল্ট কম্প্যারেটর অনুসারে এলিমেন্টগুলো সাজাতে ব্যবহৃত হয়।

val numbers = List(5, 2, 9, 1, 5, 6)

// Ascending Order
val sortedNumbers = numbers.sorted
println(sortedNumbers) // List(1, 2, 5, 5, 6, 9)

এখানে, sorted ফাংশনটি ডিফল্টভাবে কম্প্যারেটেবল এলিমেন্টগুলিকে চড়া অর্ডারে সাজিয়ে দিয়েছে।

উদাহরণ ৩: sortWith ব্যবহার

sortWith ব্যবহার করে আপনি একটি কাস্টম তুলনা ফাংশন (কম্প্যারেটর) প্রদান করতে পারেন যা উপাদানগুলির মধ্যে তুলনা করে সাজানোর কাজ করবে।

val numbers = List(5, 2, 9, 1, 5, 6)

// Custom Sort: Sort in descending order
val sortedNumbers = numbers.sortWith((x, y) => x > y)
println(sortedNumbers) // List(9, 6, 5, 5, 2, 1)

এখানে, sortWith ফাংশনটি একটি তুলনা ফাংশন নিয়ে কাজ করেছে যেখানে প্রথম উপাদানটি দ্বিতীয়টির চেয়ে বড় হলে তা আগে আসবে।

উদাহরণ ৪: Map এ Sorting

যখন আপনি Map-এর উপর সার্টিং করতে চান, আপনি মূলত key বা value অনুযায়ী সাজাতে পারবেন।

val map = Map("apple" -> 3, "banana" -> 1, "cherry" -> 2)

// Sort by key
val sortedByKey = map.toList.sortBy(_._1)
println(sortedByKey) // List((apple,3), (banana,1), (cherry,2))

// Sort by value
val sortedByValue = map.toList.sortBy(_._2)
println(sortedByValue) // List((banana,1), (cherry,2), (apple,3))

এখানে, Map-এর উপর sortBy ব্যবহার করে আপনি key বা value অনুযায়ী ডেটা সাজাতে পারেন।

সারাংশ

Sorting Techniques কালেকশনগুলির উপাদানগুলিকে সাজানোর জন্য একটি গুরুত্বপূর্ণ উপায়। স্কালায় sortBy, sorted, এবং sortWith ফাংশনগুলি সাধারণত ব্যবহৃত হয়, যা ডেটার উপর বিভিন্ন ধরনের ক্রম সজ্জিত করতে সাহায্য করে। এর মাধ্যমে আপনি সহজে এবং কার্যকরভাবে ডেটাকে সাজাতে পারেন, যা পরবর্তীতে বিশ্লেষণ বা অন্যান্য অপারেশনে সহায়ক হতে পারে।

স্কালাতে, কাস্টম সোর্টিং এবং কম্প্যারেটর ব্যবহৃত হয় যখন আমরা ডেটার একটি বিশেষ শর্ত বা কাস্টম ক্রম অনুযায়ী সজ্জিত করতে চাই। স্কালার sortBy, sortWith এবং Ordering এ কাস্টম সোর্টিং করা সম্ভব, এবং কম্প্যারেটর ব্যবহার করে আরো বেশি নিয়ন্ত্রণ পাওয়া যায়।

১. sortBy দিয়ে কাস্টম সোর্টিং

স্কালাতে, sortBy একটি সহজ এবং সাধারণ উপায় সত্ত্বেও একটি কাস্টম ফিল্ড অনুযায়ী কোনো কালেকশন সজ্জিত করতে ব্যবহৃত হয়। এটি সাধারণত লিস্ট, সেট, বা অন্যান্য কালেকশনগুলোর উপর প্রয়োগ করা হয়।

উদাহরণ:

ধরা যাক, আমরা কিছু ছাত্রের একটি লিস্ট রেখেছি, এবং আমরা ছাত্রদের নামের প্রথম অক্ষরের ভিত্তিতে সজ্জিত করতে চাই:

case class Student(name: String, age: Int)

val students = List(
  Student("Alice", 22),
  Student("Bob", 20),
  Student("Charlie", 23)
)

// কাস্টম সোর্টিং: নামের প্রথম অক্ষরের ভিত্তিতে সজ্জিত করা
val sortedByFirstLetter = students.sortBy(student => student.name.head)

sortedByFirstLetter.foreach(println)

এখানে, sortBy ব্যবহার করে আমরা name.head (নামের প্রথম অক্ষর) এর ভিত্তিতে সজ্জিত করেছি। আউটপুট হবে:

Student(Bob,20)
Student(Alice,22)
Student(Charlie,23)

২. sortWith দিয়ে কাস্টম সোর্টিং

sortWith এর মাধ্যমে আমরা আরও কাস্টম কন্ডিশন দিতে পারি। এটি একটি তুলনা ফাংশন নেয় এবং সেই তুলনাতে দুইটি উপাদানকে তুলনা করে, যেটি Boolean রিটার্ন করে।

উদাহরণ:

ধরা যাক, আমরা আবার সেই একই ছাত্রদের তালিকা ব্যবহার করছি, কিন্তু এবার আমরা তাদের বয়সের ভিত্তিতে সজ্জিত করতে চাই:

val sortedByAge = students.sortWith((student1, student2) => student1.age < student2.age)

sortedByAge.foreach(println)

এখানে, sortWith ব্যবহার করে আমরা বয়সের ভিত্তিতে সজ্জিত করেছি (অথবা যেভাবে আমরা চাই সেভাবে)। আউটপুট হবে:

Student(Bob,20)
Student(Alice,22)
Student(Charlie,23)

৩. Ordering এবং কাস্টম কম্প্যারেটর

আপনি যদি আরও বেশি কাস্টমাইজেশন চান, তখন Ordering এর মাধ্যমে কাস্টম কম্প্যারেটর তৈরি করতে পারেন। এটি কাস্টম সঠিকভাবে তুলনা করার জন্য একটি উপযুক্ত উপায়।

উদাহরণ:

ধরা যাক, আমরা Student এর একটি লিস্টে বয়স এবং নাম এর ভিত্তিতে কাস্টম সজ্জিত করতে চাই:

implicit val customOrdering: Ordering[Student] = Ordering.by((student: Student) => (student.age, student.name))

val sortedStudents = students.sorted

sortedStudents.foreach(println)

এখানে, Ordering.by ব্যবহৃত হয়েছে, যেখানে প্রথমে বয়স দিয়ে তুলনা এবং তারপরে নাম দিয়ে তুলনা করা হয়েছে (যদি বয়স সমান হয়)। আউটপুট হবে:

Student(Bob,20)
Student(Alice,22)
Student(Charlie,23)

৪. কম্প্যারেটর (Comparator) ব্যবহার

কম্প্যারেটর এমন একটি অবজেক্ট যা একটি নির্দিষ্ট নিয়ম অনুযায়ী দুইটি অবজেক্টের তুলনা করে। স্কালাতে Comparator ব্যাবহার করা হয় সাধারণত Java's Comparator এর সাথে কাজ করতে।

উদাহরণ:

import java.util.{Comparator, Arrays}

case class Employee(name: String, salary: Double)

val employees = List(
  Employee("John", 5000),
  Employee("Alice", 8000),
  Employee("Bob", 3000)
)

// Comparator এর মাধ্যমে কাস্টম সোর্টিং
val comparator: Comparator[Employee] = new Comparator[Employee] {
  def compare(e1: Employee, e2: Employee): Int = {
    e1.salary.compareTo(e2.salary)  // বেতন অনুযায়ী তুলনা
  }
}

val sortedEmployees = employees.sortWith((e1, e2) => comparator.compare(e1, e2) < 0)

sortedEmployees.foreach(println)

এখানে, Comparator ব্যবহার করা হয়েছে Employee অবজেক্টের বেতন অনুযায়ী সজ্জিত করতে।

সারাংশ

• sortBy এবং sortWith সহজ এবং সাধারণ কাস্টম সোর্টিংয়ের জন্য ব্যবহৃত হয়।
• Ordering ব্যবহার করে আপনি কাস্টম কম্প্যারেটর তৈরি করতে পারেন এবং তার মাধ্যমে সজ্জিত করতে পারেন।
• Comparator স্কালাতে কম্প্যারেটর তৈরি করতে ব্যবহৃত হয়, যেখানে আপনি নির্দিষ্ট কাস্টম তুলনা ফাংশন ব্যবহার করতে পারেন।

এই কৌশলগুলি স্কালার ডেটা স্ট্রাকচারগুলির সাথে পারফরম্যান্স অপটিমাইজেশন এবং কাস্টম ক্রম নিশ্চিত করতে সহায়ক।

সার্চিং টেকনিকস (searching techniques) এবং দক্ষ অ্যালগরিদম (efficient algorithms) হল কম্পিউটার বিজ্ঞান এবং প্রোগ্রামিংয়ের অত্যন্ত গুরুত্বপূর্ণ অংশ। এগুলি ডেটার মধ্যে তথ্য খোঁজার প্রক্রিয়াকে দক্ষ এবং দ্রুত করতে সহায়তা করে। একটি ভালো সার্চিং অ্যালগরিদম ডেটা প্রসেসিংয়ে সময় এবং সম্পদ সাশ্রয় করে।

সার্চিং টেকনিকস

সার্চিং টেকনিকস ডেটার মধ্যে একটি নির্দিষ্ট মান বা উপাদান খোঁজার জন্য ব্যবহৃত হয়। সাধারণত, সার্চিং টেকনিকস দুইটি প্রধান ক্যাটেগরিতে বিভক্ত হয়: লাইনার সার্চ (Linear Search) এবং বাইনারি সার্চ (Binary Search)।

১. লাইনার সার্চ (Linear Search)

লাইনার সার্চ একটি সিম্পল সার্চিং পদ্ধতি যেখানে আপনি একটি লিস্ট বা অ্যারে দ্বারা শুরু করেন এবং একে একে প্রতিটি উপাদান চেক করেন যতক্ষণ না আপনি যে উপাদানটি খুঁজছেন তা পেয়ে যান।

অ্যালগরিদম:

• লিস্টের প্রথম উপাদান থেকে শুরু করুন।
• প্রতিটি উপাদান তুলনা করুন।
• যদি উপাদানটি মেলে, তবে আপনি ফলাফল পাবেন।
• যদি উপাদানটি না মেলে, তবে আপনি পরবর্তী উপাদানে যাবেন এবং এই প্রক্রিয়াটি চলতে থাকবে।

উদাহরণ:

def linearSearch(arr: Array[Int], target: Int): Int = {
  for (i <- arr.indices) {
    if (arr(i) == target) {
      return i
    }
  }
  -1 // যদি target পাওয়া না যায়
}

সময়ের জটিলতা (Time Complexity): O(n)
এটি O(n) সময় নিবে, যেখানে n হল অ্যারের আকার।

২. বাইনারি সার্চ (Binary Search)

বাইনারি সার্চ একটি খুব দক্ষ সার্চিং পদ্ধতি যা sorted অ্যারে বা লিস্টে কাজ করে। বাইনারি সার্চ ডেটার মধ্যে দুটি ভাগে ভাগ করে তুলনা করে দ্রুত খোঁজ নেয়।

অ্যালগরিদম:

• প্রথমে, অ্যারেটি মিডিয়ামে ভাগ করুন।
• যদি মেটাডেটার মান খুঁজে পাওয়া না যায়, তবে আপনার সঠিক ভাগটি নির্ধারণ করুন (ডান বা বাম), এবং পুনরায় সার্চ করুন।
• প্রক্রিয়াটি চলতে থাকবে যতক্ষণ না আপনি উপাদানটি খুঁজে পান অথবা অ্যারে শেষ হয়ে যায়।

উদাহরণ:

def binarySearch(arr: Array[Int], target: Int): Int = {
  var low = 0
  var high = arr.length - 1
  
  while (low <= high) {
    val mid = (low + high) / 2
    if (arr(mid) == target) {
      return mid
    } else if (arr(mid) < target) {
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  -1 // যদি target পাওয়া না যায়
}

সময়ের জটিলতা (Time Complexity): O(log n)
এটি বাইনারি সার্চের জন্য সবচেয়ে বড় সুবিধা, কারণ এটি প্রতিটি ধাপে অ্যারের আকারের অর্ধেক অংশ বাদ দেয়।

কার্যকরী অ্যালগরিদম (Efficient Algorithms)

একটি অ্যালগরিদমের কার্যকারিতা সাধারণত তার সময় ও স্পেস কমপ্লেক্সিটির উপর নির্ভর করে। অ্যালগরিদমের কার্যকারিতা ভাল হলে তা কম সময় এবং কম রিসোর্সে কাজ করবে। নিচে কিছু জনপ্রিয় কার্যকরী অ্যালগরিদম দেয়া হলো:

১. কিউক্লিক্স সোর্ট (Quick Sort)

কিউক্লিক্স সোর্ট হল একটি ভাগ এবং জয় করার অ্যালগরিদম (Divide and Conquer), যা খুবই দ্রুত এবং সাধারণভাবে অ্যারে বা লিস্ট সোর্টিংয়ের জন্য ব্যবহৃত হয়।

অ্যালগরিদম:

• একটি পিভট এলিমেন্ট নির্বাচন করুন।
• অ্যারেটিকে পিভটের চেয়ে ছোট এবং বড় দুটি ভাগে ভাগ করুন।
• এই প্রক্রিয়াটি প্রতিটি ভাগের জন্য পুনরাবৃত্তি করুন।

সময়ের জটিলতা (Time Complexity): O(n log n) (গড় ক্ষেত্রে)
স্পেস কমপ্লেক্সিটি (Space Complexity): O(log n)

২. মার্জ সোর্ট (Merge Sort)

মার্জ সোর্ট একটি কার্যকরী সোর্টিং অ্যালগরিদম যা Divide and Conquer পদ্ধতি ব্যবহার করে। এটি অনেক ক্ষেত্রে সঠিকভাবে কাজ করে এবং স্থিতিশীল।

অ্যালগরিদম:

• অ্যারেটি দুইটি ভাগে ভাগ করুন।
• প্রতিটি ভাগে মার্জ সোর্ট প্রয়োগ করুন।
• এরপর দুটি ভাগকে একত্রিত করুন।

সময়ের জটিলতা (Time Complexity): O(n log n)
স্পেস কমপ্লেক্সিটি (Space Complexity): O(n)

৩. ডাইকাস্ট্রা অ্যালগরিদম (Dijkstra's Algorithm)

ডাইকাস্ট্রা অ্যালগরিদম গ্রাফের মধ্যে দুটি নোডের মধ্যে সবচেয়ে কম খরচে পথ খোঁজার জন্য ব্যবহৃত হয়।

অ্যালগরিদম:

• একটি সূচনা নোড থেকে শুরু করুন এবং প্রতিটি নোডের মধ্যে ছোটতম খরচ খুঁজুন।
• একে একে সব নোডের মধ্যে সর্বনিম্ন খরচ পথ নির্ধারণ করুন।

সময়ের জটিলতা (Time Complexity): O(V^2) অথবা O(E log V) (যেখানে V হল নোড এবং E হল এজ)
স্পেস কমপ্লেক্সিটি (Space Complexity): O(V)

সারাংশ

সার্চিং টেকনিকস এবং কার্যকরী অ্যালগরিদমগুলি কম্পিউটারে ডেটা প্রক্রিয়াকরণ এবং তথ্য খোঁজার জন্য অত্যন্ত গুরুত্বপূর্ণ। লাইনার সার্চ এবং বাইনারি সার্চ হল দুটি প্রধান সার্চিং টেকনিকস, যেখানে বাইনারি সার্চটি sorted ডেটাতে কার্যকরী। কিউক্লিক্স সোর্ট, মার্জ সোর্ট এবং ডাইকাস্ট্রা অ্যালগরিদম যেমন সঠিকভাবে সাজানোর এবং গ্রাফের মধ্যে সবচেয়ে ছোট পথ খুঁজে বের করার জন্য ব্যবহৃত হয়। কার্যকরী অ্যালগরিদমগুলো কম সময় এবং স্পেস খরচ করে, যা ডেটা প্রক্রিয়াকরণকে আরও দক্ষ করে তোলে।

স্কালাতে sorted, sortBy, এবং sortWith ফাংশনগুলো কালেকশন (যেমন লিস্ট) এর উপাদানগুলোকে সজ্জিত (sort) করতে ব্যবহৃত হয়। এগুলি প্রতিটি আলাদা ফাংশনালিটি প্রদান করে এবং বিভিন্ন ধরনের সাজানোর কৌশল প্রয়োগ করতে সক্ষম। চলুন, এই ফাংশনগুলোর বিস্তারিত উদাহরণ এবং পার্থক্য দেখি।

১. sorted ফাংশন

sorted ফাংশন একটি কালেকশনের উপাদানগুলোকে ডিফল্টভাবে অ্যাসেন্ডিং (ascending) অর্ডারে সাজায় (যদি উপাদানগুলোর মধ্যে নির্দিষ্ট কোনো ক্রম না থাকে, তবে তাদের তুলনা করা হয়)।

উদাহরণ:

val numbers = List(5, 2, 9, 1, 3)
val sortedNumbers = numbers.sorted
println(sortedNumbers)  // List(1, 2, 3, 5, 9)

এখানে, sorted ফাংশন লিস্টের উপাদানগুলোর ডিফল্ট অ্যাসেন্ডিং অর্ডারে সাজানো হয়েছে।

২. sortBy ফাংশন

sortBy ফাংশন ব্যবহার করে আপনি একটি নির্দিষ্ট ক্রাইটেরিয়ার ভিত্তিতে সজ্জিত করতে পারেন। এটি সাধারণত একটি ফাংশন গ্রহণ করে যা প্রত্যেকটি উপাদানকে একটি মানের উপর ম্যাপ করে এবং সেই মানের ভিত্তিতে সাজানো হয়।

উদাহরণ:

case class Person(name: String, age: Int)

val people = List(
  Person("Alice", 30),
  Person("Bob", 25),
  Person("Charlie", 35)
)

val sortedByAge = people.sortBy(person => person.age)
println(sortedByAge)  // List(Person(Bob,25), Person(Alice,30), Person(Charlie,35))

এখানে, sortBy ফাংশনটি Person অবজেক্টগুলির age ফিল্ডের উপর ভিত্তি করে সজ্জিত করছে।

আরেকটি উদাহরণ:

val names = List("Banana", "Apple", "Cherry")
val sortedByLength = names.sortBy(_.length)
println(sortedByLength)  // List(Apple, Banana, Cherry)

এখানে, sortBy লিস্টের উপাদানগুলির দৈর্ঘ্যের (length) ওপর ভিত্তি করে সাজাচ্ছে।

৩. sortWith ফাংশন

sortWith ফাংশন একটি তুলনা ফাংশন নেয় যা দুটি উপাদান তুলনা করে এবং তাদের মধ্যে কোনটি আগে আসবে তা নির্ধারণ করে। এটি একটি বাইনারি ফাংশন যা true ফেরত দিলে প্রথম উপাদানটি আগে আসবে, না হলে দ্বিতীয় উপাদানটি আগে আসবে।

উদাহরণ:

val numbers = List(5, 2, 9, 1, 3)
val sortedWithCustomComparison = numbers.sortWith((x, y) => x < y)
println(sortedWithCustomComparison)  // List(1, 2, 3, 5, 9)

এখানে, sortWith ফাংশনটি x < y শর্তে ভিত্তি করে দুটি উপাদান তুলনা করছে এবং অ্যাসেন্ডিং অর্ডারে সাজাচ্ছে।

আরেকটি উদাহরণ:

case class Person(name: String, age: Int)

val people = List(
  Person("Alice", 30),
  Person("Bob", 25),
  Person("Charlie", 35)
)

val sortedByName = people.sortWith((a, b) => a.name < b.name)
println(sortedByName)  // List(Person(Alice,30), Person(Bob,25), Person(Charlie,35))

এখানে, sortWith ব্যবহার করে Person অবজেক্টগুলিকে তাদের নামের উপর ভিত্তি করে সাজানো হয়েছে।

পার্থক্য

সারাংশ

• sorted ফাংশনটি একটি কালেকশনের উপাদানগুলোকে ডিফল্টভাবে অ্যাসেন্ডিং অর্ডারে সাজায়।
• sortBy ফাংশনটি একটি নির্দিষ্ট ফিল্ড বা ক্রাইটেরিয়া অনুযায়ী উপাদানগুলোকে সাজাতে ব্যবহৃত হয়।
• sortWith ফাংশনটি একটি তুলনা ফাংশন নেয় এবং ব্যবহারকারীর নিজস্ব তুলনা লজিক অনুসারে উপাদানগুলোকে সাজায়।

এই ফাংশনগুলি স্কালাতে খুবই গুরুত্বপূর্ণ এবং বিভিন্ন ডেটা সেট বা কালেকশন এর উপর ভিত্তি করে সাজানোর কাজ করতে ব্যবহৃত হয়।