Collection of some cool algorithms for everyday use :)

Index

  1. Dutch National Flag Algorithm
  2. Kadane’s Algorithm
  3. Algorithm to move -ve numbers to one side of the array
  4. Palindromic Array

1. Dutch National Flag Algorithm

This algorithm can be implemented to sort an array with 3 unique elements in linear time.

1.1 Algorithm

  • 3 Pointers are used. low, mid, high
  • low and mid pointers point at the start and high pointer points at the end of the array
  • If array[mid]==0, then swap array[low] and array[mid]. Then increment low and mid by 1.
  • If array[mid]==1, no swapping is required, just increment mid by 1.
  • If array[mid]==2, swap array[mid] and array[high]. Then decrement high by 1.

1.2 Code

2. Kadane’s Algorithm

This algorithm is used to find the sum of the maximum contiguous subarray in linear time.

2.1 Algorithm

  • Initialise local_max to 0 and global_max to the least possible integer.
  • Using a for loop traverse through the array and using the max() method compare local_max + a[i] and a[i]. Store the larger value in local_max.
  • if the current value of local_max is greater than global_max, then assign the value of local_max to global_max.
  • After the traversal return Global_max.

2.2 Code

3. Algorithm to move -ve numbers to one side of the array

This algorithm intends to move all the negative elements to one side of the array in linear time. The order does not matter here. If order matters then use a sorting algorithm to sort the array. The difference is, this algorithm takes linear time and a good sorting algorithm will take n*log n time.

3.1 Algorithm

  • Initialize 2 pointers, low = 0 and high = len(arr)-1 .
  • Check if low and high pointers are negative, then increment the low pointer.
  • Otherwise, if the low pointer is greater than 0 and the high pointer is less than zero, swap these elements and increment both the low and high pointers.
  • Otherwise, if the low pointer is positive and the high pointer is also positive then simply decrement the high pointer.
  • Repeat these steps until the low pointer ≤ high pointer.

3.2 Code

4. Palindromic Array

Given an Integer array A[] of n elements. The task is to return 1 if all the elements of the array are palindrome otherwise it will return 0.

4.1 Algorithm

  • Run a for loop through the given array.
  • Take each element in the array and check if it is a palindrome using the pdrome() function.
  • If it is a palindrome then multiply the counter by 1.
  • Otherwise, multiply the counter by 0.
  • In this way, the counter will be 1 only if, all the elements of the array are palindrome.
  • print the counter.

4.2 Code

kaizoku oni ore wa naru :)