Homework SourseBasic sorting algorithm Simple and Intuitive Selection sort
Solution
SELECTION SORT - A selection sort algorithm is an internal sorting technique as it sorts the list by selecting the largest element in the unsorted list and places it at the appropriate position . In each pass the largeest element in the list is placed at appropriate position if there are n elements in the list
i) in first pass all the elements are compared and largest element is placed at the last position
ii) in second pass first n-1 elements are compared and process continues for the flist of n-2 elements then for n-3 elements and so on until first element
this process is continued untill all the elements are sorted
note- if there are n elements in the list we require n-1 passes
ALGORITHM FOR SELECTION SORT -
algorithm selectionsort ( list,last)
1.set current to 0
2.loop( until last element sorted )
set smallest to current
set walker to current + 1
loop ( walker <= last )
if ( walker key < smallest key )
set smallest to walker
increement walker
end loop
exchange ( current, smallest )
increement current
end loop
end selection sort
example - 23 , 78 , 45,8,32,56 original list unsorted
after pass 1 - 8 , 78 ,45 ,23, 32,56
after pass 2 - 8, 23,45,78,32,56
after pass 3 - 8,23,32,78,45,56
after pass 4 - 8,23,32,45,78,56
after pass 5- 8,23,32,45,56,78 and this is the sorted list .
advantages of selection sort - it is easy to write and understand than insertion sort
it is simple as it does not require many iterations like in bubble sort
selection sort is preffered over bubble sort for the jumbled arrays as it requires less item to exchanged
disadvantages of selection sort - programmer generally does not prefer selection sor because it uses internal sorting mechanism that requires more memory space
the performance of the program would be slow on large amount of data
selection sort fails to recognize sorted list and carry out the sorting on that list which is waste of time as well as memory space .
BUBBLE SORT - bubble sort is an example of exchange sort the name bubble sort is because after each pass the largest element will be bubbled up in the current position ie to sort in ascending order
consider an array of n elements a[0] to a[n-1]
i) in the first pass compare a[0] with a[1].if a[0]>a[1] swap the numbers otherwise leave it compare a[1]witha[2] and swap the numbers if a[1]>a[2] and so on and compare a[n-2] with a[n-1] and swap the numbers if a[n-2]>a[n-1]by the process the first largest element is placed at nth position the element is not compared in the remaining passes.
ii)now consider first (n-1) elements in the list and repeat the above process to place the next largest element at the (n-1)th position repeat this process until all the elements are placed in proper positions after each pass the largest element is bubbled up in correct position and will not be compared in the subsequent passes .bubble sort algorithm for sorting is one of the simplest but inefficient algorithm which organizes the sorting procedure by uniformly checking the two adjacent elements and accordingly adjust their positions . it is inefficient because the number of iterations increases with the increase in the number of elements to be sorted then the number of iterations required are n-1.
example -
23, 78,45,8,56.32 original list
8,23,78,45,32,56 after pass 1
8,23,32,78,45,56 after pass 2
8,23,32,45,78,56 after pass 3
8,23,32,45,56,78 after pass 4 it is sorted .
algorithm for bubblesort ( list,last)
1.set current to 0
2.set sorted to false
3.loop(walker>current)
if( walker data < walker -1 data)
set sorted to false
exchange ( list , walker ,walker-1)
end if
decreement walker
end loop
increement current
end loop
end bubblesort
advantages bubble sort -
1. it is relatively easy to write and understood
2. the performance is good for nearly sorted list
3.works well for smaller list of elements
Disadvantages of bubble sort
it is relatively slow algorithm
it is not used for sorting list of larger size
bubble sort is worse than selection sort for jumbled array as it requires many nnumber of iterations
bubble sort is not capable of minimzing travel through the array like the insertion sort
the time taken for sorting is more than selection and insertion sort .
INSERTION SORT -
as the name suggests , insertion sort is a technique which inserts an element at an appropriate location by comparing each element with the corresponding element present at its left and accordingly moves the rest of the elements of the given array .
for example consider list 9,6,14,2,1
pass 1 - element 9 is compared with element 6
6,9,14,2,1
pass 2 - element 14 is compared with elements 9 as 14>6,9 hence no change in the series
6,9,14,2,1
pass 3 - as element 2 is compared with the 6,9,14 so it is placed in the beginning
2,6,9,14,1
pass 4 - element 1 is compared with the corresponding elements 2,9,6,14 and 1 is less among all the numbers so it is palced in the beginning
1,2,6,9,14 so it is sorted list .
ADVANTAGES OF INSERTION SORT - the implementation is simple
it is simple sorting algorithm in which the elements are sorted by considering ane item at a time
Disadvantages of insertion sort -
it is less efficient on list containing more number of elements
as the number element increases the performance of the program would be slow .
Algorithm for insertionsort ( list,last)
set current to 1
loop( until last element sorted)
move current element to hold
set walker to current -1
loop ( walker <= 0 and hold key < walker key)
move walker element right one element
decreement walker
end loop
move hold to walker + 1 element
increement current
end loop
end insertion sort
