**#1 Introduction **

in computer science, a sorting algorithm is an algorithm that puts elements of a** list** in a** certain order.** The most frequently used orders are numerical order and** lexicographical order.**

Sorting is nothing but arranging the data in ascending or descending order. The term **sorting** came into picture, as humans realised the importance of searching quickly.

There are so many things in our real life that we need to search for, like a particular record in database, roll numbers in merit list, a particular telephone number in telephone directory, a particular page in a book etc. All this would have been a mess if the data was kept unordered and unsorted, but fortunately the concept of **sorting** came into existence, making it easier for everyone to arrange data in an order, hence making it easier to search.

Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms ) which require input data to be in sorted lists.

**#2 History **

From the beginning of computing, the sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite it’s simple, familiar statement. Among the authors of early sorting algorithms around 1951 was** Betty Holberton,** who worked on ENIAC and UNIVAC. Bubble sort was analyzed as early as 1956.

**#3 Popular Algorithms**

a) Insertion sort

b) Selection sort

c) Merge sort

d) Heap sort

e) Quick sort etc.

**#4 Classification **

Sorting algorithms are often classified by:

Computational complexity.

Memory usage.

Recursion.

Stability.

Adaptability.

Comparison-based or Not

**#5 Bubble Sort**

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs and swaps them if they are in the wrong order. the pass through the list is repeated until the list is sorted.

procedure bubble Sort( A: list of sortable items)

n = length(A)

repeat

swapped = false

for i = 1 to n-1 inclusive do

if a[i-1] > A[i] then

swapped = true

end if

end for

n = n-1

until not swapped

end procedure

**#6 Insertion Sort**

insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the soted list, and inserts it here.

i <— 1

while i < length(A)

j <— j – 1

while j > 0 and a[ j – 1] > A[ j ]

swap A[j] and A[j-1]

j <— j – 1

end while

i <— i+1

end while

**#7 Selection Sort**

The algorithm proceeds by finding the smallest (or largest, depending on sorting order ) element in the unsorted sublist, boundaries one element to the right.

int i,j;

int n;

for ( j = 0; j < n-1; j++){

int iMin = j;

for ( i = j+1; i < n; i++){

if( a[i] < a[iMin]){

iMin = i;

}

}

if(iMin != j){

swap( a[j], a[iMin]);

}

}