# Design and Analysis of Algorithms

Algorithms are abstract computational procedures that take as input a value (or values) and produce as output value (or values). Values could be a simple number, character, or any data structure.

# Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of element in the respective data structure.

# Merge Sort

It is a very famous and old algorithm for sorting. It’s complexity is O(nlogn) in best, average and worst case. It is a stable and comparative sorting algorithm having the lowest bound for comparison based sorting methods. Merge sort divides array in half and calls itself on the two halves. After returning, it merges both halves using a temporary array

Merge Sort components

There are two main components for merge sort:

> Divide

> Merge

# Selection Sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

Selection Sort characteristics

Selection sort has the following characteristics:

>Comparison-based sorting algorithm

>In-place sorting technique

>An unstable sorting algorithm i.e. does not preserve the order of duplicate elements

# Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. It is a sorting algorithm that compares two adjacent elements and swaps them until they are not in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration. Therefore, it is called a bubble sort.

Characteristics of Bubble Sort

Some Characteristics of Bubble Sort:

>Large values are always sorted first.

>It only takes one iteration to detect that a collection is already sorted.

>The best time complexity for Bubble Sort is O(n)

>The space complexity for Bubble Sort is O(1), because only single additional memory space is required

# Insertion Sort

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Characteristics of Insertion Sort

Important Characteristics of Insertion Sort:

>It is efficient for smaller data sets, but very inefficient for larger lists.

>Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

>Its space complexity is less.

**Quick Sort**

Like Merge Sort, Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quick sort that pick pivot in different ways.

>Always pick first element as pivot.

>Always pick last element as pivot (implemented below)

>Pick a random element as pivot.

>Pick median as pivot.