Insertion Algorithm
Insertion algorithm is a kind of sorting algorithm where the sorting is made one at a time starting from the left most part of an array. This kind of algorithm is very useful if you have only few data to be sorted. The advantage of this algorithm is it’s easy to implement and very efficient when you have a small data. It is very user friendly in the beginner sides. One of the disadvantages in insertion algorithm comes when the array is sorted from highest to lowest because when you sorted it from lowest to highest form, it will make the value of your array shifted in every data inside before it stops. For example, you have array with a value of 5 4 3 2 1. Before the array become 1 5 4 3 2, 5 will be compare to 4 then 4 will be the new data to be compare. Next, the 4 will be compared to 3 and so on until it will be 1 2 3 4 5.
Example code for Insertion:
By:” Nikolai Bezroukov, 1996 “
#include <stdio.h>
#include <stdlib.h>
typedef int itemtype; // type of item to be sorted
int total_comp=0;
int total_moves=0;
void insertSort(
itemtype *a, // array to be sorted
int n // size of the array; note that (n-1) is the upper index of the array
)
{
itemtype t;
int i, j;
/* Outer "boundary definition" loop */
for (i = 1; i < n; i++) {
if ( a[i-1]<=a[i] ) { total_comp++; continue;}
t = a[i]; total_moves++;
/* inner loop: elements shifted down until insertion point found */
for (j = i-1; j >= 0; j--) {
total_comp++;
if ( a[j] <= t ) { break; }
a[j+1] = a[j]; total_moves++;
}
/* insert */
a[j+1] = t; total_moves++;
}
}
Example Flow:
Selection Sort
Selection sort is another sorting algorithm that is known by its simple structure and a few advantage compare to the complex sorting algorithm like quick sort. The Algorithm for this is first, you need to find the smallest value in your array. Next, swap the smallest value in your array to the beginning of your array. Next is to find the second smallest value and repeat the process all over again until the array will be sorted. Note that in every successful swapping, the iteration will be added with one until it will rich at the end of file.
Example code:
void selectionSort(int arr[], int n) {
int i, j, minIndex, tmp;
for (i = 0; i < n - 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}
Bubble Sort
Bubble sort is a sorting algorithm that is very easy to understand but the implementation or the algorithm is not that good. The original name of this is “sorting by exchange” came from articles 1962 ACM Sorting conference .This algorithm performs (n) times of its algorithm just to sort them all and it’s not a good practice in programming. For example, you have an inputs 4 2 1 5 3. You need to have a variable x and variable y. x is equal to index zero and the y is equals to 1. Compare the two and if data y is greater than x, we need to swap the value then x and y plus one. Repeat the process until it reaches the end of an array. Repeat this process over and over again to get the sorted array.
Example code.
#include <stdio.h>
#include <iostream.h>
void bubbleSort(int *array,int length)//Bubble sort function
{
int i,j;
for(i=0;i<10;i++)
{
for(j=0;j<i;j++)
{
if(array[i]>array[j])
{
int temp=array[i]; //swap
array[i]=array[j];
array[j]=temp;
}
}
}
}
void printElements(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<10;i++)
cout<<array[i]<<endl;
}
void main()
{
int a[]={9,6,5,23,2,6,2,7,1,8}; // array to sort
bubbleSort(a,10); //call to bubble sort
printElements(a,10); // print elements
}
#include <iostream.h>
void bubbleSort(int *array,int length)//Bubble sort function
{
int i,j;
for(i=0;i<10;i++)
{
for(j=0;j<i;j++)
{
if(array[i]>array[j])
{
int temp=array[i]; //swap
array[i]=array[j];
array[j]=temp;
}
}
}
}
void printElements(int *array,int length) //print array elements
{
int i=0;
for(i=0;i<10;i++)
cout<<array[i]<<endl;
}
void main()
{
int a[]={9,6,5,23,2,6,2,7,1,8}; // array to sort
bubbleSort(a,10); //call to bubble sort
printElements(a,10); // print elements
}
Example Flow:
5 1 4 2 3
1 5 4 2 3
1 4 5 2 3
1 4 2 5 3
1 4 2 3 5
Next
1 4 2 3 5
1 2 4 3 5
1 2 3 4 5
Sometimes, the step will be repeated at (n) number of time where n=length of an array.
Shell Sort
Shell sort is a sorting algorithm invented by Donald shell in 1959. Shell sort is a fast sorting algorithm and not bad but not that good for sorting large files. For me, shell sort is not a pure sorting algorithm but it’s only enhancing the speed of when you sort your file. It will not be effective if you will not use other sorting algorithm. The Algorithm of this is first you need to arrange your data from 1 column to N column. Sort your data from lowest to highest using another algorithm by rows. Arrange it again to make it one column and then divide it but this time, the column must be less than N column. If you are satisfied, you can sort it now by column with a simple sorting algorithm but if your not satisfied. You can still repeat the process.
Example Code:
void shellsort (int[] a, int n)
{ int i, j, k, h, v; int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 1968, 861, 336, 112, 48, 21, 7, 3, 1} for (k=0; k<16; k++) { h=cols[k]; for (i=h; i<n; i++) { v=a[i]; j=i; while (j>=h && a[j-h]>v) { a[j]=a[j-h]; j=j-h; } a[j]=v; } }}
Example Flow :
23 1 78 33 28 8 11 98 66 56 12 54 3 9 75 12 26 24 88
Arrange it in N column (where N is a programmer dependent)
| 23 | 1 | 78 | 33 | 28 |
| 8 | 11 | 98 | 66 | 56 |
| 12 | 54 | 3 | 9 | 75 |
| 12 | 26 | 24 | 88 | |
Sort the data by column
| 8 | 1 | 3 | 9 | 28 |
| 12 | 11 | 24 | 33 | 56 |
| 12 | 26 | 78 | 66 | 75 |
| 23 | 54 | 98 | 88 | |
Merge them all and make it one row and one column
8 1 3 9 28 12 11 24 33 56 12 26 78 66 75 23 54 98 88
Arrange it again in column less than n.
| 8 | 1 | 3 |
| 9 | 28 | 12 |
| 11 | 24 | 33 |
| 56 | 12 | 26 |
| 78 | 66 | 75 |
| 23 | 54 | 98 |
| 88 | | |
If you are satisfied with this, you can now perform a sorting algorithm to sort it by column and there you have it.
References:
No comments:
Post a Comment