search_algorithms_dart

Description:

search algorithms dart

search_algorithms #
A Dart package providing various search algorithms with a quick sort utility for sorting lists of strings. This package includes implementations of linear search, binary search, and jump search, with an extension method for quick sort.
Installation #
Add the following to your pubspec.yaml file:
dependencies:
search_algorithms: ^1.0.0
copied to clipboard
Run dart pub get to install the package.
Usage #
Importing the Package #
import 'package:search_algorithms/search_algorithms.dart';
copied to clipboard
Quick Sort Extension #
This extension adds a quickSort method to the List<String> type for sorting strings using the QuickSort algorithm.
import 'dart:math';

extension QuickSortString on List<String> {
List<String> quickSort() {
if (length < 2) {
return this;
} else {
String pivot = this[Random().nextInt(length)];
List<String> left = [
for (String element in this)
if (element.compareTo(pivot) < 0) element
];
List<String> equal = [
for (String element in this)
if (element.compareTo(pivot) == 0) element
];
List<String> right = [
for (String element in this)
if (element.compareTo(pivot) > 0) element
];

return left.quickSort() + equal + right.quickSort();
}
}
}
copied to clipboard
Search Algorithms #
Linear Search
Searches the list sequentially for the target element.
int linearSearch(List<String> list, String target) {
for (int i = 0; i < list.length; i++) {
if (list[i] == target) {
return i; // Element found, return its index
}
}
return -1; // Element not found, return -1
}
copied to clipboard
Binary Search
Searches the list using a divide and conquer approach. The list must be sorted. If not sorted, set isSorted to false and it will sort the list first.
int binarySearch({
required List<String> list,
required String target,
bool isSorted = false,
}) {
if (!isSorted) {
list = List<String>.from(list).quickSort(); // Sort the list if not already sorted
}

int left = 0;
int right = list.length - 1;

while (left <= right) {
int mid = left + (right - left) ~/ 2; // Calculate mid index

if (list[mid] == target) {
return mid; // Element found, return its index
} else if (list[mid].compareTo(target) < 0) {
left = mid + 1; // Search in the right half
} else {
right = mid - 1; // Search in the left half
}
}

return -1; // Element not found, return -1
}
copied to clipboard
Jump Search
Searches the list by jumping ahead by a fixed step size. The list must be sorted. If not sorted, set isSorted to false and it will sort the list first.
int jumpSearch({
required List<String> list,
required String target,
bool isSorted = false,
}) {
if (!isSorted) {
list = List<String>.from(list).quickSort(); // Sort the list if not already sorted
}

int n = list.length;
int step = sqrt(n).toInt(); // Block size to be jumped
int prev = 0;

// Jump through the list until we find a block where the target might be
while (list[min(step, n) - 1].compareTo(target) < 0) {
prev = step;
step += sqrt(n).toInt();
if (prev >= n) {
return -1; // Element not found, return -1
}
}

// Linear search within the identified block
for (int i = prev; i < min(step, n); i++) {
if (list[i] == target) {
return i; // Element found, return its index
}
}

return -1; // Element not found, return -1
}
copied to clipboard
Example #
Here is an example of how to use the SearchAlgorithms class:
import 'package:search_algorithms/search_algorithms.dart';

void main() {
List<String> list = ['apple', 'banana', 'cherry', 'date', 'fig', 'grape'];

// Linear Search
int linearResult = SearchAlgorithms.linearSearch(list, 'cherry');
print('Linear Search: $linearResult'); // Output: Linear Search: 2

// Binary Search
int binaryResult = SearchAlgorithms.binarySearch(list: list, target: 'date');
print('Binary Search: $binaryResult'); // Output: Binary Search: 3

// Jump Search
int jumpResult = SearchAlgorithms.jumpSearch(list: list, target: 'fig');
print('Jump Search: $jumpResult'); // Output: Jump Search: 4
}
copied to clipboard
License #
This project is licensed under the MIT License - see the LICENSE file for details.