Selection Sort
This type of sorting is called selection sort because it works by repeatedly element. It works as follows: first to find the smallest in the array and exchange it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, then continue until the entire array is sorted.
Selection sort is among the simplest of sorting techniques and it work very well for small files. Furthermore, despite its evident “naive approach “Selection sort has a quite important application because each item is actually moved at most once, Section sort is a method of choice for sorting files with very large objects (records) and small keys.
Algorithm
- 1st iteration selects the smallest element in the array, and swaps it with the first element.
- 2nd iteration selects the 2nd smallest element (which is the smallest element of the remaining elements) and swaps it with the 2nd element.
- The algorithm continues until the last iteration selects the 2nd largest element and swaps it with the 2nd last index, leaving the largest element in the last index.
Implementation:
void selectionSort(int numbers[], int array_size)
{
int i, j;
int min, temp;
for (i = 0; i < array_size-1; i++)
{
min = i;
for (j = i+1; j < array_size; j++)
{
if (numbers[j] < numbers[min])
min = j;
}
temp = numbers[i];
numbers[i] = numbers[min];
numbers[min] = temp;
}
}
Insertion Sort
Insertion sort is a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists. The algorithm is almost the same with the selection sort. It has two imaginary parts – sorted part that contains the first or the last element of the array, and unsorted contains the rest element. The algorithm is comparing the element of unsorted part into the elements of the sorted part. The element of the unsorted part is placed in the correct position at the sorted part. The algorithm stops when the unsorted part is empty.
This kind of sorting technique is quite similar to Selection sort. The difference of the two is, the Selection sort scan all the remaining elements to find the smallest element. While in Insertion sort, it only scans as many elements as needed to determine the correct location of the unsorted element of the array.
Implementation:
void insertionSort(int numbers[], int array_size){
int i, j, index;
for (i = 1; i < array_size; i++){
index = numbers[i];
j = i;
while ((j > 0) && (numbers[j − 1] > index)){
numbers[j] = numbers[j − 1];
j = j − 1;
}
numbers[j] = index;
}
}
Bubble Sort
It is a sorting technique that works by comparing each adjacent pair of elements in an array and swapping the elements if necessary and repeating the pass until all the elements in the array are sorted.
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.
Implementation:
void bubbleSort(int numbers[], int array_size)
{
int i, j, temp;
for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (numbers[j-1] > numbers[j])
{
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
}
}
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 you’re not satisfied. You can still repeat the process.
This sorting technique is similar of Insertion sorting but the difference is, instead of comparing adjacent elements, this sorting technique repeatedly compares elements that are distance away from each other where ( d represents the distance ). The value of d starts out as half the input size and is halved after each pass through the array. The elements are compared and swapped when needed.
Equation of the distance: d = (n + 1) / 2
Implementation:
void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;
increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
