Sorting
Sorting:
Sorting is the process of ordering or arranging a given
collection of elements in some particular 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) or according to the length of
the string.
For example,:
1. words in a dictionary are sorted in alphabetical order;
2. seats in an examination hall are ordered according to
candidates’ roll number.
3. We can also sort a list of students based on their height
or weight.
Types of Sorting:
Bubble sort
Selection sort
Insertion sort
Bubble sort
Bubble sort, sorts a given list of elements by repeatedly
comparing the adjacent elements and swapping them if they
are unordered.
In algorithm, every iteration through each element of a list is called a
pass.
For a list with n elements, the bubble sort makes a total of n – 1
passes to sort the list.
In each pass, the required pairs of adjacent elements of the list will
be compared. In order to arrange elements in ascending order, the
largest element is identified after each pass and placed at the correct
position in the list.
This can be considered as the largest element being ‘bubbled up’.
Hence the name Bubble sort. This sorted element is not considered in
the remaining passes and thus the list of elements gets reduced in
successive passes.
Algorithm 5.1: Bubble Sort
BUBBLESORT( numList, n)
Step 1: SET i = 0
Step 2: WHILE i< n REPEAT STEPS 3 to 8
Step 3: SET j = 0
Step 4: WHILE j< n-i-1,REPEAT STEPS 5 to 7
Step 5:IF numList[j] > numList[j+1] THEN Step
6:swap(numList[j],numList[j+1])
Step 7:SET j=j+1
Step 8: SET i=i+1
Implementation of bubble sort using Python.
Selection sort
Selection sort is another sorting technique. To sort a list having n
elements, 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.
In the first pass, all the elements in the unsorted list are traversed to
find the smallest element.
The smallest element is then swapped with the leftmost element of
the unsorted list.
This element occupies the first position in the sorted list, and it is not
considered in further passes.
In the second pass, the next smallest element is selected from the
remaining elements in the unsorted list and swapped with the
leftmost element of the unsorted list.
This element occupies the second position in the sorted list, and the
unsorted list reduces by one element for the third pass.
This process continues until n-1 smallest elements are found and
moved to their respective places. The nth element is the last, and it is
already in place.
Algorithm 5.2:
SELECTIONSORT( numList, n)
Step 1: SET i=0
Step 2: WHILE i< n REPEAT STEPS 3 to 11
Step 3: SET min = i, flag = 0
Step 4: SET j= i+1
Step 5: WHILE j<n, REPEAT STEPS 6 to 10
Step 6: IF numList[j] < numList[min] THEN
Step 7: min = j
Step 8: flag = 1
Step 9: IF flag = 1 THEN
Step 10: swap(numList[i],numList[min])
Step 11: SET i=i+1
Program for Selection sort:
Insertion sort
Insertion sort is another sorting algorithm that can arrange
elements of a given list in ascending or descending order.
In Insertion sort also, the list is divided into two parts - one of sorted
elements and another of unsorted elements.
Each element in the unsorted list is considered one by one and is
inserted into the sorted list at its appropriate position.
In each pass, the sorted list is traversed from the backward direction
to find the position where the unsorted element could be inserted.
Hence the sorting method is called insertion sort.
Algorithm 5.3: Insertion Sort
INSERTIONSORT( numList, n)
Step 1: SET i=1
Step 2: WHILE i< n REPEAT STEPS 3 to 9
Step 3:temp = numList[i]
Step 4:SET j = i-1
Step 5:WHILE j> = 0 and numList[j]>temp,REPEAT
STEPS 6 to 7
Step 6:numList[j+1] = numList[j]
Step 7:SET j=j-1
Step 8:numList[j+1] = temp #insert temp
at position j
Step 9:set i=i+1
Program for Insertion sort
TIME COMPLEXITY OF ALGORITHMS
The amount of time an algorithm takes to process a given
data can be called its time complexity.
1. Constant time algorithms.
Any algorithm that does not have any loop will have time
complexity as 1 since the number of instructions to be executed will
be constant, irrespective of the data size. Such algorithms are
known as Constant time algorithms.
2. Linear time algorithms
Any algorithm that has a loop (usually 1 to n) will have the time
complexity as n because the loop will execute the statement inside
its body n number of times. Such algorithms are known as linear
time algorithms.
3. Quadratic time algorithms
A loop within a loop (nested loop) will have the time complexity as
n2. Such algorithms are known as Quadratic time algorithms.
If there is a nested loop and also a single loop, the time complexity
will be estimated on the basis of the nested loop only.
