Selection Sort
* It is a combination of searching and sorting. It is among the simplest sorting techniques and it will work very well for small files. The disadvantage of it is, this kind of sorting technique is inefficient on large lists.
Here is a sample code for this sorting technique:
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;
}
}
* This is how it works:
- First, find the smallest element in the array.
- If the smallest element of the array was found, exchange it with the element in first position in the array.
- Find the second smallest element in the array.
- Exchange the second smallest element in the array with the element in the second position in the array.
- Continue this way until the entire array is sorted.
* For me, Selection sort is not difficult to analyze because it is one of the simplest sorting techniques that we are using.
* Here is an example of a Selection Sort: array A = (5,2,1,4,7,6,3)
unsorted = 5 2 1 4 7 6 3
- Scan for the smallest element in the array which is 1. Exchange it with the first element in the array.
1 2 5 4 7 6 3
- Scan for the next smallest element in the array which is two and exchange it with the second position. Since element 2 is already in its proper position, scan again for the next smaller element and exchange it in the third position.
1 2 3 4 7 6 5
- Since elements 1 2 3 4 is already in their proper position, scan for another smaller element and exchange it with the 5th position in the array.
1 2 3 4 5 6 7
- And now, we have the sorted array using the Selection Sort.
Insertion Sort
* 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.
* Here is a sample code for Insertion Sort:
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;
}
}
* This is how it works:
- First we have an unsorted array. It scans all the elements first and looks for the necessary element to be positioned to the correct location.
- If the first few elements of the array are already sorted, an unsorted element can now be inserted in the sorted elements and place the unsorted element in its proper place.
- Continue this way until all the elements in the array is in their proper position.
* Here is an example of an Insertion sort:
array A = (5,2,4,6,1,3)
5 2 4 6 1 3
- Since from the first few elements, 2 is the smallest element, this is what will happen:
2 5 4 6 1 3
- Since 4 is less than 5,
2 4 5 6 1 3
- Since elements 2 4 5 6 are already sorted, look for the unsorted element after the last sorted element. The next unsorted element is 1. Position it to its proper place. This is what will happen:
1 2 4 5 6 3
- Since element 3 is the last unsorted element, place it in its proper position. This is:
1 2 3 4 5 6
- And we have now the sorted array using the Insertion Sort.
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.
* Here is a sample code for Bubble Sorting:
// This is a sample code of Bubble Sorting for Descending Order
void BubbleSort(apvector <int> &num)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = num.length( );
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] > num[j]) // ascending order simply changes to <
{
temp = num[j]; // swap elements
num[j] = num[j+1];
num[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
* This is how it works:
- First it compares the first two elements in the array.
- If the first element is greater than the second element, swap the first and second element. But if the first element is less than the second, elements will remain in their position.
- Next, compare the second element and third element.
- If the second element is greater than the third element, swap the second and third element. But if the second element is less than the third, elements will remain in their position.
- Continue this process until the elements in the array are sorted.
* Here is a sample of Bubble Sorting: we have array A = (2 1 5 3 4 6)
[2 1 5 3 4 6] → [1 2 5 3 4 6] : we swap 1 and 2 because 1<2.
- Now compare the second element and the third element. Since 5 > 2, they will remain in their position.
- Next, compare the third and fourth element. Since 3 < 5, swap them.
[1 2 5 3 4 6] → [1 2 3 5 4 6]
- We have now sorted the first three elements in the array. There were still remaining unsorted elements.
- Now compare the 4th and 5th element. Since 4 < 5, swap them.
[1 2 3 5 4 6] → [1 2 3 4 5 6]
- Now compare the last two elements in the array. Since they’re already in their proper position, Finally, we the sorted array and the algorithm can terminate.
Shell Sort
* This Sorting technique was named after its inventor D. L. Shell.
* 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
* Here is a sample cod for Shell sorting:
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;
}
}
* This is how it works: We have array a = (91 94 86 76 69 84)
- First we have to equate the distance. Since we have 6 elements in the array,
d = (6 +1)/2 = 3 : Compare the 1st and 4th, 2nd and 5th, 3rd and 6th items (since they are 3 positions away from each other)
[ 76 69 84 91 94 86 ]
- The last resulting distance is 3. So, we will equate another distance.
d = (3 + 1)/2 = 2 : The new distance now is two. So, we will compare the first element with the next element which is 2 distance away from the first element.
[ 76 69 84 91 94 86 ]
- We will equate another distance.
d = (2 + 1)/2 = 1 : This is our new distance. Compare again each element until all the elements in the array are sorted.
[76 69 84 91 94 86] → [69 76 84 91 86 94] → [69 76 84 86 91 94]
- And now, we have the sorted array using Shell Sorting.
No comments:
Post a Comment