In Algorithm Design, Sorting is an important part. Different algorithm use the sorting algorithm. Some Interesting sorting algorithm are include here: Bubble Sort, Heap Sort, Quick Sort, Counting Sort, Selection Sort, Insertion Sort etc.
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
Bubble Sort:
Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Bubble sort has worst-case and average complexity both О(n^2), where n is the number of items being sorted.
{codecitation style="brush: cpp;"}
template <class T> /*Template Declared Class here*/
void bubble_sort(T a[],int n){
T temp;
for(int i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1]; /*Swap have been done here*/
a[j+1]=temp;
}
}
}
}
{/codecitation}
Insertion Sort:
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
Simple implementation
Efficient for (quite) small data sets
Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
More efficient in practice than most other simple quadratic, i.e. O(n^2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
Stable, i.e. does not change the relative order of elements with equal keys
In-place, i.e. only requires a constant amount O(1) of additional memory space
Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
{codecitation style="brush: cpp;"}
template <class T>
void insertion_sort(T a[],int n)
{
T key;
for(int i=1;i<n;i++){
key=a[i];
int j=i-1;
while(j>=0&&a[j]>key){ a[j+1]=a[j];
j=j-1;
}
a[j+1]=key;
}
}
{/codecitation}
Selection Sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n^2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Worst case performance О(n^2).
Best case performance О(n^2)
Average case performance О(n^2)
{codecitation style="brush: cpp;"}
template <class T>
int min_elm(T a,int low,int up)
{
int min=low;
while(low<up)
{
if(a[low]<a[min])
min=low;
low++;
}
return min;
}
template <class T>
void selection_sort(T a[],int n)
{
int i=0;
int loc=0;
T temp;
for(i=0;i<n;i++)
{
loc=min_elm(a,i,n);
temp=a[loc];
a[loc]=a[i];
a[i]=temp;
}
}
{/codecitation}
Counting Sort
Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value i; then counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array. The algorithm was created by Harold H. Seward in 1954. Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n. But the limitation of that sorting is that it is not efficient to imply in float and double type variables and not possible to imply in string type variables.
{codecitation style="brush: cpp;"}
template <class T>
void linear_sort(T *a,long n,long m)
{
int c[m],b[10000];
for(int i=0;i<=m;i++)
c[i]=0;
for(int i=0;i<n;i++)
c[(long)a[i]]=c[(long)a[i]]+1;
for(int i=1;i<=m;i++)
c[i]=c[i]+c[i-1];
for(int i=n-1;i>=0;i--)
{
b[c[(long)a[i]]-1]=(long)a[i];
c[(long)a[i]]=c[(long)a[i]]-1;
}
copy(b,b+n,a);
}
{/codecitation}
Heap Sort:
Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a more favorable worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.
Heapsort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.
{codecitation style="brush: cpp;"}
template <class T>
void max_heapify(T a[],int i,int n)
{
int l,r,lar;
l=2*i;
r=(2*i)+1;
if(l<=n && a[l]>a[i])
lar=l;
else
lar=i;
if(r<=n && a[r]>a[lar])
lar=r;
if(lar!=i)
{
swap(a[i],a[lar]);
max_heapify(a,lar,n);
}
}
template <class T>
void build_max_heap(T a[],int n)
{
for(int i=n/2;i>=1;i--)
max_heapify(a,i,n);
}
template <class T>
void heapsort(T a[],int n)
{
build_max_heap(a,n);
for(int i=n;i>=2;i--)
{
swap(a[1],a[i]);
n=n-1;
max_heapify(a,1,n);
}
}
{/codecitation}
Quick Sort
Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that quicksort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures.
{codecitation style="brush: cpp;"}
template <class T>
int partition(T a[],int p,int r)
{
T x;
int i;
x=a[r];
i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[r]);
return i+1;
}
template <class T>
void quick_sort(T a[],int p,int r)
{
int q;
if(p<r)
{
q=partition(a,p,r);
quick_sort(a,p,q-1);
quick_sort(a,q+1,r);
}
}
{/codecitation}
Reference:
Introduction to Algorithms (2nd Ed) - Thomas H. Cormen
Data Structures and Problem Solving Using C++ (2nd Ed) - Pearson Education
In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important to optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output.
Bubble Sort:
Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Bubble sort has worst-case and average complexity both О(n^2), where n is the number of items being sorted.
{codecitation style="brush: cpp;"}
template <class T> /*Template Declared Class here*/
void bubble_sort(T a[],int n){
T temp;
for(int i=0;i<n;i++) {
for(int j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1]; /*Swap have been done here*/
a[j+1]=temp;
}
}
}
}
{/codecitation}
Insertion Sort:
Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
Simple implementation
Efficient for (quite) small data sets
Adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
More efficient in practice than most other simple quadratic, i.e. O(n^2) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
Stable, i.e. does not change the relative order of elements with equal keys
In-place, i.e. only requires a constant amount O(1) of additional memory space
Worst case performance О(n^2)
Best case performance O(n)
Average case performance О(n^2)
{codecitation style="brush: cpp;"}
template <class T>
void insertion_sort(T a[],int n)
{
T key;
for(int i=1;i<n;i++){
key=a[i];
int j=i-1;
while(j>=0&&a[j]>key){ a[j+1]=a[j];
j=j-1;
}
a[j+1]=key;
}
}
{/codecitation}
Selection Sort
Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n^2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
Worst case performance О(n^2).
Best case performance О(n^2)
Average case performance О(n^2)
{codecitation style="brush: cpp;"}
template <class T>
int min_elm(T a,int low,int up)
{
int min=low;
while(low<up)
{
if(a[low]<a[min])
min=low;
low++;
}
return min;
}
template <class T>
void selection_sort(T a[],int n)
{
int i=0;
int loc=0;
T temp;
for(i=0;i<n;i++)
{
loc=min_elm(a,i,n);
temp=a[loc];
a[loc]=a[i];
a[i]=temp;
}
}
{/codecitation}
Counting Sort
Counting sort (sometimes referred to as ultra sort or math sort) is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range to create an array C of this length. Each index i in array C is then used to count how many elements in A have the value i; then counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array. The algorithm was created by Harold H. Seward in 1954. Counting sort is a stable sort and has a running time of Θ(n+k), where n and k are the lengths of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be much larger than n. But the limitation of that sorting is that it is not efficient to imply in float and double type variables and not possible to imply in string type variables.
{codecitation style="brush: cpp;"}
template <class T>
void linear_sort(T *a,long n,long m)
{
int c[m],b[10000];
for(int i=0;i<=m;i++)
c[i]=0;
for(int i=0;i<n;i++)
c[(long)a[i]]=c[(long)a[i]]+1;
for(int i=1;i<=m;i++)
c[i]=c[i]+c[i-1];
for(int i=n-1;i>=0;i--)
{
b[c[(long)a[i]]-1]=(long)a[i];
c[(long)a[i]]=c[(long)a[i]]-1;
}
copy(b,b+n,a);
}
{/codecitation}
Heap Sort:
Heapsort is a comparison-based sorting algorithm, and is part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantage of a more favorable worst-case Θ(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.
Heapsort works as its name suggests. It begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. After removing the largest item, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements.
{codecitation style="brush: cpp;"}
template <class T>
void max_heapify(T a[],int i,int n)
{
int l,r,lar;
l=2*i;
r=(2*i)+1;
if(l<=n && a[l]>a[i])
lar=l;
else
lar=i;
if(r<=n && a[r]>a[lar])
lar=r;
if(lar!=i)
{
swap(a[i],a[lar]);
max_heapify(a,lar,n);
}
}
template <class T>
void build_max_heap(T a[],int n)
{
for(int i=n/2;i>=1;i--)
max_heapify(a,i,n);
}
template <class T>
void heapsort(T a[],int n)
{
build_max_heap(a,n);
for(int i=n;i>=2;i--)
{
swap(a[1],a[i]);
n=n-1;
max_heapify(a,1,n);
}
}
{/codecitation}
Quick Sort
Quicksort is a sorting algorithm developed by C. A. R. Hoare that, on average, makes O(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other O(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices that minimize the probability of requiring quadratic time. Additionally, quicksort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that quicksort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures.
{codecitation style="brush: cpp;"}
template <class T>
int partition(T a[],int p,int r)
{
T x;
int i;
x=a[r];
i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
swap(a[i],a[j]);
}
}
swap(a[i+1],a[r]);
return i+1;
}
template <class T>
void quick_sort(T a[],int p,int r)
{
int q;
if(p<r)
{
q=partition(a,p,r);
quick_sort(a,p,q-1);
quick_sort(a,q+1,r);
}
}
{/codecitation}
Reference:
Introduction to Algorithms (2nd Ed) - Thomas H. Cormen
Data Structures and Problem Solving Using C++ (2nd Ed) - Pearson Education
Comments (0)
