# Algorithm Garage

Collection of some cool algorithms for everyday use :)

**Index**

- Dutch National Flag Algorithm
- Kadane’s Algorithm
- Algorithm to move -ve numbers to one side of the array
- 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**