Sorting
Sorting is the process of arranging elements in a particular order (ascending,
descending, alphabetical, etc.).
• It is essential for easy data retrieval and efficient searching.
• Common applications:
– Dictionaries (alphabetical order)
– Exam seating plans (roll number order)
– Sorting by height, weight, etc.
The three important sorting algorithms are
[Link] sort
[Link] sort
[Link] sort
Bubble sort
Concept
• Compares adjacent elements and swaps them if they are in the wrong
order.
• After each pass, the largest unsorted element “bubbles up” to its correct
position, which will not be considered in the next pass
• Requires n – 1 passes for a list of size n.
Below we show how the bubble sort works taking list as [8,7,13,1, -9,4]
Bubble sort algorithm
BUBBLESORT(numList, n)
1. Set i = 0
2. While i < n repeat:
3. Set j = 0
4. While j < n - i - 1 repeat:
5. If numList[j] > numList[j+1], then
6. Swap numList[j] and numList[j+1]
7. j = j + 1
8. i = i + 1
Implementation of bubble sort using Python.
Selection Sort
Concept
• The list is divided into sorted and unsorted parts.
• The smallest element from the unsorted list is selected and swapped with the first
unsorted element.
• Requires n – 1 passes for n elements.
Below we show how the selection sort works taking list as [8,7,13,1, -9,4]
•
Selection Sort algorithm
SELECTIONSORT(numList, n)
1. Set i = 0
2. While i < n repeat:
3. Set min = i, flag = 0
4. Set j = i + 1
5. While j < n repeat:
6. If numList[j] < numList[min] then
7. min = j
8. flag = 1
9. If flag == 1 then
10. Swap numList[i], numList[min]
11. i = i + 1
Implementation of selection sort using python
Insertion Sort
Concept
• Elements from the unsorted part are picked and inserted into the correct
position of the sorted part.
• Like arranging cards in hand.
Below we show how the selection sort works taking list as [8,7,13,1, -9,4]
Insertion Sort Algorithm
Implementation of selection sort using python
Time Complexity of Algorithms
• The amount of time an algorithm takes to process a given data can be
called its time complexity.
• 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.
• 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
• A loop within a loop (nested loop) will have the time complexity as n2.
Such algorithms are known as Quadratic time algorithms.
• All the sorting algorithms namely, bubble sort, selection sort and
insertion sort have a time complexity of n2.