
The Caesar cipher is a simple cipher and one of the best known encryption algorithms. It is very simple to encrypt, decrypt and intercept. The Caesar cipher is a substitution cipher where each letter in the plain-text (decoded text) is replaced by a letter a certain number of spaces to the right of the letter in the alphabet. (The amount of spaces is called the key or shift and is only known by the sender and intended receiver).

**Disclaimer: Do not attempt to encrypt personal data or serious messages with this cipher!!! It takes only half a second to crack by a computer!**

1. It takes a very small amount of time to encode and decode messages. (Less than a second, usually)
3. No real applications exist for the cipher as it is the most insecure out there.
4. This cipher was invented by Julius Caesar as a way to send messages of high military significance.

## Steps

### Encryption
1. Choose the alphabet you are going to use.
2. Choose a secret key (shift) that you are going to use in this case `n`.
3. For every letter in the plain-text, replace it by a letter of the alphabet that is `n` letters away from the letter. (Ex: for a key of `1`, `a` would become `b`, `z` would become `a`, etc.)
4. The message should now be encoded.

### Decryption
1. Choose the alphabet that the message was encrypted with.
2. Let `n` be the secret key the message is encoded in.
3. For every letter in the cipher-text, replace it by a letter of the alphabet that is `n` letters behind in the alphabet from the letter.
`c` would be `b`, `a` would be `z` with a key of `1`.
4. The message should now be decoded

## Example

### An example of encryption
Let us say we are sending a secret message to a friend.

* We first write out our message. In this case: `The Caesar cipher is a fun substitution cipher`
* Our alphabet will be: `abcdefghijklmnopqrstuvwxyz`. For the uses of this tutorial, case doesn't matter. (On a shift of `1`: `A` will become `B`, `a` will become `b`)
* Let our key be 6.
* Starting with the first letter: `T`. The letter 6 letters away is `Z`. We add `Z` to the message.
* The second letter is `h`. The letter 6 letters away is `n`. Our message is now `Zn`
* We continue like that until the end. Our final message is: `Znk Igkygx iovnkx oy g lat yahyzozazout iovnkx.`
* Decryption is the same way, except instead of going to the right in the alphabet, we go backwards.

## Implementation

* [Python](https://github.com/TheAlgorithms/Python/blob/master/ciphers/caesar_cipher.py)


Caesar Cipher

Xor Cipher

Binary To Decimal

Hexadecimal To Decimal

Octal To Decimal


#### Problem Statement

Given an array of n elements, write a function to sort the array

#### Approach

- Find a mid point and divide the array into to halves based on the mid point
- Recursively call the merge sort function for both the halves
- Merge the two sorted halves to get the sorted array

#### Time Complexity

`O(n log n)`

#### Space Complexity

`O(n)`

#### Example

```
arr = [1, 3, 9, 5, 0, 2]  

Divide the array in two halves [1, 3, 9] and [5, 0, 2]

Recursively call merge sort function for both these halves which will provide sorted halves
=> [1, 3, 9] & [0, 2, 5]

Now merge both these halves to get the sorted array [0, 1, 2, 3, 5, 9]
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/MergeSort.java)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/sorting/merge_sort.cpp)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/merge_sort.py)
- [C-Sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/Algorithms/Sorters/Comparison/MergeSorter.cs)
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/merge_sort.c)
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/sorting/merge_sort.rb)

#### Video Explanation

[A CS50 video explaining the Merge Sort Algorithm](https://www.youtube.com/watch?v=EeQ8pwjQxTM)


Mergesort

Edit Distance

Factorial

Fibonacci

Perfect Square


#### Problem Statement

Given a sorted  array of n elements, write a function to search for the index of a given element (target)

#### Approach

- Search for the array by dividing the array in half repeatedly.
- Initially consider the actual array and pick the element at the middle index
- Keep a lower index i.e. 0 and higher index i.e. length of array
- If it is equal to the target element then return the index
- Else if it is greater than the target element then consider only the left half of array. (lower index = 0, higher = middle - 1)
- Else if it is less than the target element then consider only the right half of array. (lower index = middle + 1, higher = length of array)
- Return -1 if target element is not found in the array (Base Case: If lower index is greater than or equal to higher index)

#### Time Complexity

O(log n) Worse Case     
O(1) Best Case (If middle element of initial array is the target element)

#### Space Complexity

O(1) For iterative approach          
O(log n) For recursive approach due to recursion call stack

#### Example

```
arr = [1,2,3,4,5,6,7]  

target = 2
Initially the element at middle index is 4 which is greater than 2. Therefore we search the left half of the
array i.e. [1,2,3].
Here we find the middle element equal to target element so we return its index i.e. 1

target = 9          
Binary Search should return -1 as 9 is not present in the array
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Searches/BinarySearch.java)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Search/Binary%20Search.cpp)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/searches/binary_search.py)
- [C-Sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/searches/binary_search.cs)
- [C](https://github.com/TheAlgorithms/C/blob/master/searching/Binary_Search.c)

#### Video Explanation

[A CS50 video explaining the Binary Search Algorithm](https://www.youtube.com/watch?v=5xlIPT1FRcA)

#### Animation Explanation

- [Tute Board](https://boardhub.github.io/tute/?wd=binarySearchAlgo2)


Binary Search


#### Problem Statement

Given an array of n elements, write a function to search for the index of a given element (target)

#### Approach

- Start iterating with the first element in the array.
- Compare it with the target element
- If it is equal to the target element then return the index
- Else continue iterating
- Return -1 if target element is not found in the array

#### Time Complexity

O(n) Worse Case     
O(1) Best Case (If first element of array is the target element)

#### Space Complexity

O(1)

#### Example

```
arr = [1, 3, 9, 5, 0, 2]  

target = 5
Linear Search should return index 3 as 5 is on index 3     

target = 6           
Linear Search should return -1 as 6 is not present in the array
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Searches/LinearSearch.java)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Search/Linear%20Search.cpp)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/searches/linear_search.py)

#### Video Explanation

[A CS50 video explaining the Linear Search Algorithm](https://www.youtube.com/watch?v=CX2CYIJLwfg)

#### Animation Explanation

- [Tute Board](https://boardhub.github.io/tute/?wd=linearSearchAlgo)


Linear Search


#### Problem Statement

Given an unsorted array of n elements, write a function to sort the array

#### Approach

- select the first element of the array
- compare it with its next element
- if it is larger than the next element then swap them
- else do nothing
- keep doing this for every index of the array
- repeat the above process n times.

#### Time Complexity

`O(n^2)` Worst case performance

`O(n)` Best-case performance

`O(n^2)` Average performance

#### Space Complexity

`O(1)` Worst case

#### Founder's Name

- The term âBubble Sortâ was first used by Iverson, K in 1962.

#### Example

```
arr[] = {10, 80, 40, 30}
Indexes: 0   1   2   3    

1. Index = 0, Number = 10
2. 10 < 80, do nothing and continue

3. Index = 1, Number = 80
4. 80 > 40, swap 80 and 40
5. The array now is {10, 40, 80, 30}

6. Index = 2, Number = 80
7. 80 > 30, swap 80 and 30
8. The array now is {10, 40, 30, 80}

Repeat the Above Steps again

arr[] = {10, 40, 30, 80}
Indexes: 0   1   2   3   

1. Index = 0, Number = 10
2. 10 < 40, do nothing and continue

3. Index = 1, Number = 40
4. 40 > 30, swap 40 and 30
5. The array now is {10, 30, 40, 80}

6. Index = 2, Number = 40
7. 40 < 80, do nothing
8. The array now is {10, 30, 40, 80}

Repeat the Above Steps again

arr[] = {10, 30, 40, 80}
Indexes: 0   1   2   3   

1. Index = 0, Number = 10
2. 10 < 30, do nothing and continue

3. Index = 1, Number = 30
4. 30 < 40, do nothing and continue

5. Index = 2, Number = 40
6. 40 < 80, do nothing

Since there are no swaps in above steps, it means the array is sorted and we can stop here.
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/BubbleSort.java)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/sorting/bubble_sort.cpp)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/bubble_sort.py)
- [C-Sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/Algorithms/Sorters/Comparison/BubbleSorter.cs)
- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/bubblesort.go)
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/sorting/bubble_sort.rb)
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/bubble_sort.c)
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/BubbleSort.scala)
- [Javascript](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/BubbleSort.js)

#### Video Explanation

[A video explaining the Bubble Sort Algorithm](https://www.youtube.com/watch?v=Jdtq5uKz-w4)

#### Others

Bubble sort is also known as Sinking sort.

#### Animation Explanation

- [Tute Board](https://boardhub.github.io/tute/?wd=bubbleSortAlgo2)


Bubble Sort


#### Problem Statement

Given an array of n elements, write a function to sort the array in increasing order.

#### Approach

- Define a "key" index, the subarray to the left of which is sorted.
- Initiate "key" as 1, ie. the second element of array(as there is only one element to left of the second element, which can be considered as sorted array with one element).
- If value of element at (key - 1) position is less than value of element at (key) position; increment "key".
- Else move elements of sorted subarray that are greater than value of element at "key" to one position ahead of their current position. Put the value of element at "key" in the newly created void.

#### Time Complexity

- `Ð(n^2)` comparisons, `Ð(n^2)` swaps -- Worst Case

- `O(n)` comparisons, `O(1)` swaps -- Best Case

#### Space Complexity

`O(1)` -- (No extra space needed, sorting done in place)

#### Example

```

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (Size of input array)

i = 1.
Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2.
13 will remain at its position as all elements in sorted subarray are smaller than 13
11, 12, 13, 5, 6

i = 3.
5 will move to the beginning,
and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4.
6 will move to position after 5,
and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13  -- sorted array
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/InsertionSort.java)
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/insertion_sort.c)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/sorting/insertion_sort.cpp)
- [C#](https://github.com/TheAlgorithms/C-Sharp/blob/master/Algorithms/Sorters/Comparison/InsertionSorter.cs)
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/InsertionSort.scala)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py)
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/sorting/insertion_sort.rb)

#### Video Explanation

[A CS50 video explaining the Insertion Search Algorithm](https://www.youtube.com/watch?v=DFG-XuyPYUQ)


Insertion Sort


The lower bound for Comparison based sorting algorithm (Merge Sort, Heap Sort, Quick-Sort .. etc) is `Î©(nlogn)`, i.e., they cannot do better than `nlogn`. 

Counting sort is a linear time sorting algorithm that sort in `O(n+k)` time when elements are in the range from 1 to k.

What if the elements are in the range from 1 to n2? We canât use counting sort because counting sort will take `O(n2)` which is worse than comparison-based sorting algorithms. Can we sort such an array in linear time? 

Radix Sort is the answer. The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

## The Radix Sort Algorithm 

Do following for each digit i where i varies from least significant digit to the most significant digit. 
Sort input array using counting sort (or any stable sort) according to the iâth digit.

Example:

Original, unsorted list:
`170, 45, 75, 90, 802, 24, 2, 66`

Sorting by least significant digit (1s place) gives:

[*Notice that we keep 802 before 2, because 802 occurred 
before 2 in the original list, and similarly for pairs 
170 & 90 and 45 & 75.]

Sorting by next digit (10s place) gives: 

[*Notice that 802 again comes before 2 as 802 comes before 2 in the previous list.]

`802, 2, 24, 45, 66, 170, 75, 90`

Sorting by the most significant digit (100s place) gives:
`2, 24, 45, 66, 75, 90, 170, 802`

## What is the running time of Radix Sort? 

Let there be d digits in input integers. Radix Sort takes `O(d*(n+b))` time where b is the base for representing numbers, for example, for the decimal system, b is 10.
What is the value of d? If `k` is the maximum possible value, then d would be `O(logb(k))`. So overall time complexity is `O((n+b) * logb(k))`. Which looks more than the 
time complexity of comparison-based sorting algorithms for a large k. Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes 
`O(n logb(n))`. But it still doesnât beat comparison-based sorting algorithms. 

## Is Radix Sort preferable to Comparison based sorting algorithms like Quick-Sort? 

If we have `log2n` bits for every digit, the running time of Radix appears to be better than Quick Sort for a wide range of input numbers. The constant factors hidden in 
asymptotic notation are higher for Radix Sort and Quick-Sort uses hardware caches more effectively. Also, Radix sort uses counting sort as a subroutine and counting sort
takes extra space to sort numbers.

Video reference: https://youtu.be/nu4gDuFabIM


Radix Sort


#### Problem Statement

Given an unsorted array of n elements, write a function to sort the array

#### Approach

- select the smallest element from the array
- put it at the beginning of the array
- then select the smallest array from the remaining unsorted list
- append it to the sorted array at the beginning
- keep doing this for every element of the array
- repeat the above process n times

#### Time Complexity

`O(n^2)` Worst case performance

`O(n^2)` Best-case performance

`O(n^2)` Average performance

#### Space Complexity

`O(1)` Worst case

#### Example

```
arr[] = {80, 10, 40, 30}
Indexes: 0   1   2   3    

1. Index = 0
	Select the minimum number from the array (between index 0-3), ie, 10
2. Swap 10  and 80 (arr[0])
3. The array now is {10, 80, 40, 30}

4. Index = 1
	Select the minimum number from the array (between index 1-3), ie, 30
5. Swap 30 and 80 (arr[1])
6. The array now is {10, 30, 40, 80}

7. Index = 2
	Select the minimum number from the array (between index 2-3), ie, 40
8. Swap 40 and 40 (arr[2])
9. The array now is {10, 30, 40, 80}

The array is now sorted.
```

#### Code Implementation Links

- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/SelectionSort.java)
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Sorting/Selection%20Sort.cpp)
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/selection_sort.py)
- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/selection_sort.go)
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Sorting/selection_sort.rb)
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/SelectionSort.c)
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/SelectionSort.scala)
- [Javascript](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/selectionSort.js)

#### Video Explanation

[A video explaining the Selection Sort Algorithm](https://www.youtube.com/watch?v=f8hXR_Hvybo)

#### Animation Explanation

- [Tute Board](https://boardhub.github.io/tute/?wd=selectSortAlgo2)


PHP

ciphers

Caesar Cipher

Xor Cipher

conversions

Binary To Decimal

Hexadecimal To Decimal

Octal To Decimal

divideandconquer

Mergesort

dynamicprogramming

Edit Distance

Factorial

Fibonacci

math

Check Prime

maths

Perfect Square

AbsoluteMax

AbsoluteMin

Fastexponentiation

searches

Binary Search

Linear Search

Lower Bound

Upper Bound

sorting

Countsort

sorts

Bubble Sort

Insertion Sort

Radix Sort

Selection Sort

string

CheckAnagram

CheckPalindrome

MaxCharacter

ReverseString

Countvowels

strings

Reverse Words

tests

Cipherstest

Ciphertest

Conversionstest

Mathtest

Countsorttest

Stringtest