Chapter-5 Sorting
Sorting is a process of arranging an element in ascending or descending order.
We can sort a collection of numbers in ascending (increasing) or descending
(decreasing) order. If the collection is of strings, we can sort it in an alphabetical
order (a-z or z-a).
Bubble Sort
Bubble sort is the simplest sorting algorithm that works by repeatedly swapping
the adjacent elements in case they are unordered in n-1 passes.
How does bubble sort works.
1. Starting with first element.
2. Compare the current element with next element.
3. If the current element is greater than the next element, then of the list
swap both the elements; if not move to the next element.
4. Repeat Step 1-3 until we get the sorted list.
Example on Bubble sort.
1. Consider 7, 6, 4, 3 numbers in list, sort them using bubble sort technique.
________________________________________________________________
[Link] 1
2. Consider 5,3,4,2 numbers in list, sort them using bubble sort technique.
Try this, Sort them using bubble sort technique
a) 4, 1, 3, 9, 7
b) 10, 6, 5, 4, 3, 1
c) -2, 45, 0, 11, -9
________________________________________________________________
[Link] 2
Algorithm for Bubble sort.
Implementation of bubble sort using Python.
________________________________________________________________
[Link] 3
Selection Sort
The selection sort makes (n-1) number of passes through the list. The list is
considered to be divided into two lists -- the left list containing the sorted
elements, and the right list containing the unsorted elements. Initially, the left
list is empty, and the right list contains all the elements.
How does Selection sort works.
1. First we find the smallest element and swap it with the first element. This
way we get the smallest element at its correct position.
2. Then we find the smallest among remaining elements (or second smallest)
and swap it with the second element.
3. We keep doing this until we get all elements moved to correct position.
Example on Selection sort.
1. Consider 22,13,64,12,33 numbers in list, sort them using selection sort
technique.
________________________________________________________________
[Link] 4
2. Consider 42,16,84,12,77,26,53 numbers in list, sort them using selection
sort technique.
Try this, Sort them using selection sort technique
a) 17,16,3,13,6
b) 8,5,7,1,9,3
c) 20,12,10,15,2
________________________________________________________________
[Link] 5
Algorithm for Selection sort.
Implementation of bubble sort using Python.
________________________________________________________________
[Link] 6
________________________________________________________________
[Link] 7
________________________________________________________________
[Link] 8