Process:
- First, find the smallest value in the array
- Next, swap the the values where the smallest value is located w/ the 1st index value of the array
- Then, Find the next smallest value in the array and swap the values where the next smallest is located w/ the 2nd index value of the array.
Advantages:
Selection Sorting is efficient in sorting records because it only moves one record at a time.
Disadvantages:
If the array is already sorted, the function " if " is still executed, at that moment, time is wasted.
Implementation:
int min, temp;
int numArr [] = {2,5,1,3,4};
for(int x = 0 ; x < sizeOfArray-1 ; x++){
min = x;
for(int y = x+1 ; y < sizeOfArray ; y++){
if(numArr[y] < numArr[min]){
min = y;
}
}
temp = numArr[x];
numArr[x] = numArr[min];
numArr[min] = temp;
}
Insertion Sort
Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2), thus being slower than heap sort, merge sort and also shell sort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.[1]
Process:
Let a0, ..., an-1 be the sequence to be sorted. At the beginning and after each iteration of the algorithm the sequence consists of two parts: the first part a0, ..., ai-1 is already sorted, the second part ai, ..., an-1 is still unsorted (i
0, ..., n). In order to insert element ai into the sorted part, it is compared with ai-1, ai-2 etc. When an element aj with aj
ai is found, ai is inserted behind it. If no such element is found, then ai is inserted at the beginning of the sequence. After inserting element ai the length of the sorted part has increased by one. In the next iteration, ai+1 is inserted into the sorted part etc. While at the beginning the sorted part consists of element a0 only, at the end it consists of all elements a0, ..., an-1.[1]
Advantages:
Disadvantages:
Moving the elements to the right in order to make room for the element to be inserted takes linear time anyway.[1]
Implementation:
int temp;
int arrNum[] = {2,3,5,4,1};
for(int x = 0 ; x < sizeOfArray ; x++){
int y = x;
temp = arrNum[x];
while(y > 0 && a[y-1] > temp){
arrNum[y] = arrNum[y-1];
y--;
}
arrNum[y] = temp;
}
Bubble Sort
Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.[2]
Process:
- Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
- If at least one swap has been done, repeat step 1.
Advantages:
Bubble sort is stable and adaptive.[2]
Disadvantages:
Bubble sort is inefficient when sorting large data files because it has the running time of O(n2).
Implementation:
bool swapped = false;
int j = 0;
int temp;
while(){
swapped = false;
j++;
for(int x = 0; x < sizeOfArray-j ; x++){
if(arrNum[x] > arrNum[x+1]){
temp = arrNum[x];
arrNum[x] = arrNum[x+1];
arrNum[x+1] = temp;
swapped = true;
}
}
}
Shell Sort
Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.[3]
Process:
- Arrange the data sequence in a two-dimensional array.
- Sort the columns of the array.[3]
Disadvantages:
It is inefficient in terms of processing speed, because it uses other sorting algorithm to perform its own sorting algorithm.
Implementation:
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;
}
}
}[3][1] Insertion Sort
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htm
[2] Bubble Sort
http://www.algolist.net/Algorithms/Sorting/Bubble_sort
[3] Shell Sort
http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm
