Selection sort performs sorting by repeatly putting the largest element in the unprocessed portion of the array to the end of the this unprocessed portion until the whole array is sorted.
It works by repeatedly element. It works as follows: first 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, and continue in this way 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 "naïve 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.
The Selection sort spends most of its time trying to find the minimum element in the "unsorted" part of the array.
Example how to implement:
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;
}
}
2. Insertion Sort
Insertion sort is an algorithm to arrange a sequence of elements R1, R2, …, Rn into order. Elements are removed one by one from the unsorted sequence and inserted into the correct position in a new, sorted sequence S.
Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n2), thus being slower than heapsort, merge sort and also shellsort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.
Sorting is usually implemented in-place. As elements are removed from the end of sequence R, the space freed up is used to extend sequence S. After i insertions, R1, …, Rn-i remain unsorted and the sorted sequence S1, …, Si is stored in elements Rn-i+1, …, Rn.
Pseudo Code for Insertion Sort:
function insertion_sort R
i ← length R
while i > 0 do
j ← i
temp ← Rj
while j < length R and Rj+1 < temp do
Rj ← Rj+1
j ← j + 1
Rj ← temp
i ← i - 1
i ← length R
while i > 0 do
j ← i
temp ← Rj
while j < length R and Rj+1 < temp do
Rj ← Rj+1
j ← j + 1
Rj ← temp
i ← i - 1
Insertion sort requires n passes to sort a sequence of n elements. With each pass the sorted sequence S increases by one element. On average, Insertion sort will move and compare half of the sorted sequence each pass. The average number of move / compare operations is (n²-n)/4.
The worst case is a sequence sorted in reverse order which requires (n²-n)/2 move / compare operations. Insertion sort runs in Ο(n²) time.
Insertion sort is a stable sorting algorithm. The relative order of equal elements is maintained.
3. Bubble Sort
Bubble Sort is an elementary sorting algorithm. It works by repeatedly exchanging adjacent elements, if necessary. When no exchanges are required, the file is sorted. It is an alternate way of putting the largest element at the highest index in the array uses an algorithm.
The bubble sort is quick for nearly sorted files. For example, files which have been recently sorted but may have had a few more records added at the end.
Like selection sort, the idea of bubble sort is to repeatedly move the largest element to the highest index position of the array. As in selection sort, each iteration reduces the effective size of the array. The two algorithms differ in how this is done. Rather than search the entire effective array to find the largest element, bubble sort focuses on successive adjacent pairs of elements in the array, compares them, and either swaps them or not. In either case, after such a step, the larger of the two elements will be in the higher index position. The focus then moves to the next higher position, and the process is repeated. When the focus reaches the end of the effective array, the largest element will have ``bubbled'' from whatever its original position to the highest index position in the effective array.
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;
}
}
}
}
4. 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.
This algorithm is a simple extension of Insertion sort. Its speed comes from the fact that it exchanges elements that are far apart (the insertion sort exchanges only adjacent elements).
The idea of the Shell sort is to rearrange the file to give it the property that taking every hth element (starting anywhere) yields a sorted file. Such a file is said to be h-sorted.
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;
}
}
REFRENCES:
No comments:
Post a Comment