Here we discuss the following: Selection Sort, Insertion Sort, Bubble & Shellsort
In computer science world, sorting is one of the most programming tasks. We say a LIST containing EXAM SCORES, we can sort them from Highest to Lowest or in reverse order. The next one, we say STUDENT RECORD sorted by its surname, student number, so on and so forth. So, with that it is easy for us to search or to look for a thing when it is being sorted.
Selection Sort
Selection sort is the most simple of all sorting algorithms. What make it simple? Because it repeatedly searches for Largest or Smallest value (if you want to sort them from big to small) in a section of the data or in an array.
If we use to find the Largest value. It works like this:
First step, get values for n and the n list items. Second, set the marker for the unsorted section at the end of the list. Third, while the unsorted section of the list is not empty, then do steps 4 through step 6. Forth, select the largest number in the unsorted section of the list. Fifth, exchange this number with the last number in the unsorted section of the list. Sixth, move the marker for the unsorted section left one position. Lastly, stop when the list is empty.
Example:
Uses Find the Largest algorithm.
Sort: 34 8 64 51 32 21
34 8 64 51 32 21 - set marker at 21 and search for largest
34 8 21 51 32 64 - 34-32 is considered unsorted list
34 8 21 32 51 64 - repeat this process until unsorted list is empty
32 8 21 34 51 64
21 8 32 34 51 64
8 21 32 34 51 64
Here is the code for a simple selection sort:
for(int x=0; x<n; x++)
{
int index_of_min = x;
for(int y=x; y<n; y++)
{
if(array[index_of_min]>array[y])
{
index_of_min = y;
}
}
int temp = array[x];
array[x] = array[index_of_min];
array[index_of_min] = temp;
}
Insertion Sort
Insertion sort occurs in our daily life it's like playing card. To sort a card in your hand you extract a card, shift the remaining cards, and then insert the extracted card in the correct place. Repeat the process until all the cards are in its right order. According to my readings, insertion sorts keeps making the left side of the array sorted until the whole array is sorted.
Here's the basic algorithm, repeat the following steps until the value is in correct sequence.
1st step: Pull out current value into a temp variable
2nd step: Check index's value - if less than temp then move it to left
Example:
Sort: 34 8 64 51 32 21
34 8 64 51 32 21 - pull out 8 into Temp
34 8 64 51 32 21 - compare 34 and 8 - move 34 up a spot
34 34 64 51 32 21 - spot is found for 8 - place it where it belongs
8 34 64 51 32 21
8 34 64 51 32 21 - pull out 64 into Temp
8 34 64 51 32 21 - compare 64 and 34 - place 64 back into slot 2
8 34 64 51 32 21
8 34 64 51 32 21 - pull out 51 into Temp
8 34 64 51 32 21 - compare 51 and 64 - move 64 to the right
8 34 64 64 32 21 - compare 51 and 34 - place 51 into slot 2
8 34 51 64 32 21
8 34 51 64 32 21 - pull out 32 into Temp
8 34 51 64 32 21 - compare 32 and 64 - move 64 to the right
8 34 51 64 64 21 - compare 32 and 51 move 51 to the right
8 34 51 51 64 21 - compare 32 and 34 - move 34 to the right
8 34 34 51 64 21 - compare 32 and 8 - place 32 in slot 1
8 32 34 51 64 21
Bubble Sort
It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in wrong order. The pass through the list is repeated until no swaps are needed, which indicates the list is sorted.
Example:
Sort: 34 8 64 51 32 21
Pass 1 Pass 2
34 8 64 51 32 21 8 34 51 32 21 64
8 34 64 51 32 21 8 34 51 32 21 64
8 34 51 64 32 21 8 34 51 32 21 64
8 34 51 32 64 21 8 34 32 51 21 64
8 34 51 32 32 64 8 34 32 21 51 64
8 34 32 21 51 64
Repeat until no swaps are made. Not practical for list with large n- except when list is very close to sorted.
Shell Sort
A brief history of shellsort, it was invented by Donald Shell in 1959. it was the 1st algorithm to break the quadratic time barrier but few years, a sub quadratic time bound was proven.
ShellsortShellsort uses an increment sequence denoted as floor(n/2), n means number to be sorted. The best case of shellsort is when the array is already sorted in the right order. Therefore, the number of comparison is less. When is talks of Best there's always worst, so, the worst case is when the running time depends on the choice of increment sequence. The problem with shell's increment is that pairs of increment are not necessarily relatively prime and smaller increments can have little effect.
Example:
There are 8 inputs to be sorted, Shells increment will be floor(n/2); n=8
floor(8/2) = floor(4) = 4
Sort: 18 32 12 5 38 33 16 2
(visualized underlining)
increment 4: 1 2 3 4
18 32 12 5 38 33 16 2
Step1) Only look at 18 and 38 and sort in order; 18 and 38 stays at its current position because they are in order.
Step2.) Only look at 32 and 33 and sort in order; 32 and 33 stays at its current position because they are in order.
Step3.) Only look at 12 and 16 and sort in order; 12 and 16 stays at its current position because they are in order.
Step4.) Only look at 5 and 2 and sort in order; 2 and 5 need to be switched to be in order.
Resulting numbers after increment 4 pass:
18 32 12 2 38 33 16 5
We know that increment is 4, after that alteration the increment will change into:
floor(4/2) = floor(2) = 2
increment 2: 1 2
18 32 12 2 38 33 16 5
Step1.) Look at 18, 12, 38, 16 and sort them in their appropriate location.
12 32 16 2 18 33 38 5
Step2.) Look at 32, 2, 33, 5 and sort them in their appropriate location.
12 2 16 5 18 32 38 33
we do the same thing for increment:
floor(2/2) = 1
increment1: 1
12 2 16 5 18 32 38 33
2 5 12 16 18 32 33 38 - here we use the insertion sort algorithm for the last increment of shellsort.
Reference:
http://www.slidefinder.net/s/selection_sort_insertion_sort_bubble/24241852
http://en.wikipedia.org/wiki/Adjacent
http://wiki.answers.com/Q/What_is_the_difference_between_bubble_sort_and_selection_sort
http://en.wikipedia.org/wiki/Bubble_sort
http://en.wikipedia.org/wiki/Insertion_sort
http://en.wikipedia.org/wiki/Bubble_sort
http://en.wikipedia.org/wiki/Shell_sort
No comments:
Post a Comment