Algorithms¶
- pydatastructs.merge_sort_parallel(array, num_threads, **kwargs)¶
Implements parallel merge sort.
- Parameters
array (Array) – The array which is to be sorted.
num_threads (int) – The maximum number of threads to be used for sorting.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for sorting. If the function returns False then only swapping is performed. Optional, by default, less than or equal to is used for comparing two values.
Examples
>>> from pydatastructs import OneDimensionalArray, merge_sort_parallel >>> arr = OneDimensionalArray(int,[3, 2, 1]) >>> merge_sort_parallel(arr, 3) >>> [arr[0], arr[1], arr[2]] [1, 2, 3] >>> merge_sort_parallel(arr, 3, comp=lambda u, v: u > v) >>> [arr[0], arr[1], arr[2]] [3, 2, 1]
References
- pydatastructs.brick_sort(array, **kwargs)¶
Implements Brick Sort / Odd Even sorting algorithm
- Parameters
array (Array) – The array which is to be sorted.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for sorting. If the function returns False then only swapping is performed. Optional, by default, less than or equal to is used for comparing two values.
Examples
>>> from pydatastructs import OneDimensionalArray, brick_sort >>> arr = OneDimensionalArray(int,[3, 2, 1]) >>> brick_sort(arr) >>> [arr[0], arr[1], arr[2]] [1, 2, 3] >>> brick_sort(arr, comp=lambda u, v: u > v) >>> [arr[0], arr[1], arr[2]] [3, 2, 1]
References
- pydatastructs.brick_sort_parallel(array, num_threads, **kwargs)¶
Implements Concurrent Brick Sort / Odd Even sorting algorithm
- Parameters
array (Array/list) – The array which is to be sorted.
num_threads (int) – The maximum number of threads to be used for sorting.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for sorting. If the function returns False then only swapping is performed. Optional, by default, less than or equal to is used for comparing two values.
Examples
>>> from pydatastructs import OneDimensionalArray, brick_sort_parallel >>> arr = OneDimensionalArray(int,[3, 2, 1]) >>> brick_sort_parallel(arr, num_threads=5) >>> [arr[0], arr[1], arr[2]] [1, 2, 3] >>> brick_sort_parallel(arr, num_threads=5, comp=lambda u, v: u > v) >>> [arr[0], arr[1], arr[2]] [3, 2, 1]
References
- pydatastructs.heapsort(array, **kwargs)¶
Implements Heapsort algorithm.
- Parameters
array (Array) – The array which is to be sorted.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
Examples
>>> from pydatastructs import OneDimensionalArray, heapsort >>> arr = OneDimensionalArray(int,[3, 2, 1]) >>> heapsort(arr) >>> [arr[0], arr[1], arr[2]] [1, 2, 3]
References
Note
This function does not support custom comparators as is the case with other sorting functions in this file.
- pydatastructs.matrix_multiply_parallel(matrix_1, matrix_2, num_threads)¶
Implements concurrent Matrix multiplication
- Parameters
matrix_1 (Any matrix representation) – Left matrix
matrix_2 (Any matrix representation) – Right matrix
num_threads (int) – The maximum number of threads to be used for multiplication.
- Raises
ValueError – When the columns in matrix_1 are not equal to the rows in matrix_2
- Returns
C – The result of matrix multiplication.
- Return type
list
Examples
>>> from pydatastructs import matrix_multiply_parallel >>> I = [[1, 1, 0], [0, 1, 0], [0, 0, 1]] >>> J = [[2, 1, 2], [1, 2, 1], [2, 2, 2]] >>> matrix_multiply_parallel(I, J, num_threads=5) [[3, 3, 3], [1, 2, 1], [2, 2, 2]]
References
- pydatastructs.counting_sort(array: pydatastructs.linear_data_structures.arrays.Array) pydatastructs.linear_data_structures.arrays.Array¶
Performs counting sort on the given array.
- Parameters
array (Array) – The array which is to be sorted.
- Returns
output – The sorted array.
- Return type
Array
Examples
>>> from pydatastructs import DynamicOneDimensionalArray as DODA, counting_sort >>> arr = DODA(int, [5, 78, 1, 0]) >>> out = counting_sort(arr) >>> str(out) "['0', '1', '5', '78']" >>> arr.delete(2) >>> out = counting_sort(arr) >>> str(out) "['0', '5', '78']"
References
Note
Since, counting sort is a non-comparison sorting algorithm, custom comparators aren’t allowed. The ouput array doesn’t contain any None value.
- pydatastructs.bucket_sort(array: pydatastructs.linear_data_structures.arrays.Array, **kwargs) pydatastructs.linear_data_structures.arrays.Array¶
Performs bucket sort on the given array.
- Parameters
array (Array) – The array which is to be sorted.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
- Returns
output – The sorted array.
- Return type
Array
Examples
>>> from pydatastructs import DynamicOneDimensionalArray as DODA, bucket_sort >>> arr = DODA(int, [5, 78, 1, 0]) >>> out = bucket_sort(arr) >>> str(out) "['0', '1', '5', '78']" >>> arr.delete(2) >>> out = bucket_sort(arr) >>> str(out) "['0', '1', '78']"
References
Note
This function does not support custom comparators as is the case with other sorting functions in this file.
- pydatastructs.cocktail_shaker_sort(array: pydatastructs.linear_data_structures.arrays.Array, **kwargs) pydatastructs.linear_data_structures.arrays.Array¶
Performs cocktail sort on the given array.
- Parameters
array (Array) – The array which is to be sorted.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for sorting. If the function returns False then only swapping is performed. Optional, by default, less than or equal to is used for comparing two values.
- Returns
output – The sorted array.
- Return type
Array
Examples
>>> from pydatastructs import OneDimensionalArray as ODA, cocktail_shaker_sort >>> arr = ODA(int, [5, 78, 1, 0]) >>> out = cocktail_shaker_sort(arr) >>> str(out) '[0, 1, 5, 78]' >>> arr = ODA(int, [21, 37, 5]) >>> out = cocktail_shaker_sort(arr) >>> str(out) '[5, 21, 37]'
References
- pydatastructs.quick_sort(array: pydatastructs.linear_data_structures.arrays.Array, **kwargs) pydatastructs.linear_data_structures.arrays.Array¶
Performs quick sort on the given array.
- Parameters
array (Array) – The array which is to be sorted.
start (int) – The starting index of the portion which is to be sorted. Optional, by default 0
end (int) – The ending index of the portion which is to be sorted. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for sorting. If the function returns False then only swapping is performed. Optional, by default, less than or equal to is used for comparing two values.
pick_pivot_element (lambda/function) – The function implementing the pivot picking logic for quick sort. Should accept, low, high, and array in this order, where low represents the left end of the current partition, high represents the right end, and array is the original input array to quick_sort function. Optional, by default, picks the element at high index of the current partition as pivot.
- Returns
output – The sorted array.
- Return type
Array
Examples
>>> from pydatastructs import OneDimensionalArray as ODA, quick_sort >>> arr = ODA(int, [5, 78, 1, 0]) >>> out = quick_sort(arr) >>> str(out) '[0, 1, 5, 78]' >>> arr = ODA(int, [21, 37, 5]) >>> out = quick_sort(arr) >>> str(out) '[5, 21, 37]'
References
- pydatastructs.longest_common_subsequence(seq1: pydatastructs.linear_data_structures.arrays.OneDimensionalArray, seq2: pydatastructs.linear_data_structures.arrays.OneDimensionalArray) pydatastructs.linear_data_structures.arrays.OneDimensionalArray¶
Finds the longest common subsequence between the two given sequences.
- Parameters
seq1 (OneDimensionalArray) – The first sequence.
seq2 (OneDimensionalArray) – The second sequence.
- Returns
output – The longest common subsequence.
- Return type
Examples
>>> from pydatastructs import longest_common_subsequence as LCS, OneDimensionalArray as ODA >>> arr1 = ODA(str, ['A', 'B', 'C', 'D', 'E']) >>> arr2 = ODA(str, ['A', 'B', 'C', 'G' ,'D', 'E', 'F']) >>> lcs = LCS(arr1, arr2) >>> str(lcs) "['A', 'B', 'C', 'D', 'E']" >>> arr1 = ODA(str, ['A', 'P', 'P']) >>> arr2 = ODA(str, ['A', 'p', 'P', 'S', 'P']) >>> lcs = LCS(arr1, arr2) >>> str(lcs) "['A', 'P', 'P']"
References
Note
The data types of elements across both the sequences should be same and should be comparable.
- pydatastructs.is_ordered(array, **kwargs)¶
Checks whether the given array is ordered or not.
- Parameters
array (OneDimensionalArray) – The array which is to be checked for having specified ordering among its elements.
start (int) – The starting index of the portion of the array under consideration. Optional, by default 0
end (int) – The ending index of the portion of the array under consideration. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for specifying the desired ordering. Optional, by default, less than or equal to is used for comparing two values.
- Returns
True if the specified ordering is present
from start to end (inclusive) otherwise False.
Examples
>>> from pydatastructs import OneDimensionalArray, is_ordered >>> arr = OneDimensionalArray(int, [1, 2, 3, 4]) >>> is_ordered(arr) True >>> arr1 = OneDimensionalArray(int, [1, 2, 3]) >>> is_ordered(arr1, start=0, end=1, comp=lambda u, v: u > v) False
- pydatastructs.upper_bound(array, value, **kwargs)¶
Finds the index of the first occurence of an element greater than the given value according to specified order, in the given OneDimensionalArray using a variation of binary search method.
- Parameters
array (OneDimensionalArray) – The array in which the upper bound has to be found.
start (int) – The staring index of the portion of the array in which the upper bound of a given value has to be looked for. Optional, by default 0
end (int, optional) – The ending index of the portion of the array in which the upper bound of a given value has to be looked for. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for specifying the desired ordering. Optional, by default, less than or equal to is used for comparing two values.
- Returns
index – Index of the upper bound of the given value in the given OneDimensionalArray.
- Return type
int
Examples
>>> from pydatastructs import upper_bound, OneDimensionalArray as ODA >>> arr1 = ODA(int, [4, 5, 5, 6, 7]) >>> ub = upper_bound(arr1, 5, start=0, end=4) >>> ub 3 >>> arr2 = ODA(int, [7, 6, 5, 5, 4]) >>> ub = upper_bound(arr2, 5, comp=lambda x, y: x > y) >>> ub 4
Note
DynamicOneDimensionalArray objects may not work as expected.
- pydatastructs.lower_bound(array, value, **kwargs)¶
Finds the the index of the first occurence of an element which is not less than the given value according to specified order, in the given OneDimensionalArray using a variation of binary search method.
- Parameters
array (OneDimensionalArray) – The array in which the lower bound has to be found.
start (int) – The staring index of the portion of the array in which the upper bound of a given value has to be looked for. Optional, by default 0
end (int, optional) – The ending index of the portion of the array in which the upper bound of a given value has to be looked for. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for specifying the desired ordering. Optional, by default, less than or equal to is used for comparing two values.
- Returns
index – Index of the lower bound of the given value in the given OneDimensionalArray
- Return type
int
Examples
>>> from pydatastructs import lower_bound, OneDimensionalArray as ODA >>> arr1 = ODA(int, [4, 5, 5, 6, 7]) >>> lb = lower_bound(arr1, 5, end=4, comp=lambda x, y : x < y) >>> lb 1 >>> arr = ODA(int, [7, 6, 5, 5, 4]) >>> lb = lower_bound(arr, 5, start=0, comp=lambda x, y : x > y) >>> lb 2
Note
DynamicOneDimensionalArray objects may not work as expected.
- pydatastructs.longest_increasing_subsequence(array)¶
Returns the longest increasing subsequence (as a OneDimensionalArray) that can be obtained from a given OneDimensionalArray. A subsequence of an array is an ordered subset of the array’s elements having the same sequential ordering as the original array. Here, an increasing sequence stands for a strictly increasing sequence of numbers.
- Parameters
array (OneDimensionalArray) – The given array in the form of a OneDimensionalArray
- Returns
output – Returns the longest increasing subsequence that can be obtained from the given array
- Return type
Examples
>>> from pydatastructs import lower_bound, OneDimensionalArray as ODA >>> from pydatastructs import longest_increasing_subsequence as LIS >>> array = ODA(int, [2, 5, 3, 7, 11, 8, 10, 13, 6]) >>> longest_inc_subsequence = LIS(array) >>> str(longest_inc_subsequence) '[2, 3, 7, 8, 10, 13]' >>> array2 = ODA(int, [3, 4, -1, 5, 8, 2, 2 ,2, 3, 12, 7, 9, 10]) >>> longest_inc_subsequence = LIS(array2) >>> str(longest_inc_subsequence) '[-1, 2, 3, 7, 9, 10]'
- pydatastructs.next_permutation(array, **kwargs)¶
If the function can determine the next higher permutation, it returns True and the permutation in a new array. If that is not possible, because it is already at the largest possible permutation, it returns the elements according to the first permutation and returns False and the permutation in a new array.
- Parameters
array (OneDimensionalArray) – The array which is to be used for finding next permutation.
start (int) – The staring index of the considered portion of the array. Optional, by default 0
end (int, optional) – The ending index of the considered portion of the array. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for specifying the desired lexicographical ordering. Optional, by default, less than is used for comparing two values.
- Returns
output – First element is True if the function can rearrange the given portion of the input array as a lexicographically greater permutation, otherwise returns False. Second element is an array having the next permutation.
- Return type
bool, OneDimensionalArray
Examples
>>> from pydatastructs import next_permutation, OneDimensionalArray as ODA >>> array = ODA(int, [1, 2, 3, 4]) >>> is_greater, next_permute = next_permutation(array) >>> is_greater, str(next_permute) (True, '[1, 2, 4, 3]') >>> array = ODA(int, [3, 2, 1]) >>> is_greater, next_permute = next_permutation(array) >>> is_greater, str(next_permute) (False, '[1, 2, 3]')
References
- pydatastructs.prev_permutation(array, **kwargs)¶
If the function can determine the next lower permutation, it returns True and the permutation in a new array. If that is not possible, because it is already at the lowest possible permutation, it returns the elements according to the last permutation and returns False and the permutation in a new array.
- Parameters
array (OneDimensionalArray) – The array which is to be used for finding next permutation.
start (int) – The staring index of the considered portion of the array. Optional, by default 0
end (int, optional) – The ending index of the considered portion of the array. Optional, by default the index of the last position filled.
comp (lambda/function) – The comparator which is to be used for specifying the desired lexicographical ordering. Optional, by default, less than is used for comparing two values.
- Returns
output – First element is True if the function can rearrange the given portion of the input array as a lexicographically smaller permutation, otherwise returns False. Second element is an array having the previous permutation.
- Return type
bool, OneDimensionalArray
Examples
>>> from pydatastructs import prev_permutation, OneDimensionalArray as ODA >>> array = ODA(int, [1, 2, 4, 3]) >>> is_lower, prev_permute = prev_permutation(array) >>> is_lower, str(prev_permute) (True, '[1, 2, 3, 4]') >>> array = ODA(int, [1, 2, 3, 4]) >>> is_lower, prev_permute = prev_permutation(array) >>> is_lower, str(prev_permute) (False, '[4, 3, 2, 1]')
References