#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]);
}
}
