Sorting Algorithm

What is sorting algorithm?

A Sorting Algorithm is used to rearrange a given array
or list of elements according to a comparison operator
on the elements. The comparison operator is used to
decide the new order of elements in the respective data
structure.
 Sorting technique
• Types of Sorting Techniques
There are various sorting algorithms are used in data
structures. The following two types of sorting
algorithms can be broadly classified:
• Comparison-based: We compare the elements in a
comparison-based sorting algorithm)
• Non-comparison-based: We do not compare the
elements in a non-comparison-based sorting
algorithm)
Sorting technique
 Insertion sort
Insertion sort is a simple sorting algorithm that works
similar to the way you sort playing cards in your hands.
The array is virtually split into a sorted and an unsorted
part. Values from the unsorted part are picked and placed
at the correct position in the sorted part.
 Sorting Integers

How to sort the integers in this array?

20 8 5 10 7

5 7 8 10 20
 Insertion Sort

• Basic idea (sorting cards):

– Starts by considering the first two elements of
the array data, if out of order, swap them
– Consider the third element, insert it into the
proper position among the first three elements.
– Consider the forth element, insert it into the
proper position among the first four elements.
–……
 Algorithm
0 1 2 3 4 5 6 7 8
Insertionsort (A,n) 9 6 5 0 8 2 7 1 3

For j=1 to A(length) {

Key = A[j]
i = j-1
While (i> 0 ֆֆ A[i] >key) {
A[i+1] = A[i]
i= i-1
}
A[i+1] = key
}
 Insertion Sort: Pseudocode

Step 1 − If it is the first element, it is already sorted. return 1;

Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is
greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
 Insertion Sort Analysis
• Run time of this algorithm is very much
dependent on the given input.
• If the given numbers are sorted, this algorithm
runs in O(n) time. If the given numbers are in
reverse order, the algorithm runs in O(n2) time.
• Worst-case time complexity: O(n^2)
• Best case time complexity: O(n)
 Algorithm
def insertion_sort(array, size):
for i in range(1, size):
key = array[i] j = i
while (j > 0) and (array[j-1] > key):
array[j] = array[j-1]
j = j-1
array[j] = key
arr = [67, 44, 82, 17, 20]
n = len(arr)
print("Array before Sorting: ")
print(arr) insertion_sort(arr, n);
print("Array after Sorting: ")
print(arr)
 Advantages and disadvantages
• Very efficient in the case of a small number of elements.
• If the elements are already in sorted order it won’t spend much time
in useless operations and will deliver a run time of O(n).
• It is more efficient when compared to other simple algorithms like
Bubble sort and Selection Sort.
Disadvantages
• One of the major disadvantages of Insertion sort is its Average Time
Complexity of O(n^2).
• If the number of elements is relatively large it can take large time as
compared to Quick Sort or Merge Sort.
 Practice examples
1. Array [8, 5, 3, 1, 9, 4, 6, 2, 7]
2. Array [7, 2, 4, 1, 5, 3, 9, 6, 8]
3. Array [14, 33, 27, 10, 35, 19, 44, 42]
4. Array [4, 3, 6, 5, 1]
5. Array [17, 13, 23, 2, 7, 1 34]
Bubble sort
 Bubble sort
• Bubble sort is a simple sorting algorithm. This sorting
algorithm is comparison-based algorithm in which each pair of
adjacent elements is compared and the elements are swapped
if they are not in order.
• This algorithm is not suitable for large data sets as its average
and worst case complexity are of O(n2) where n is the number
of items.
• Bubble Sort is an elementary sorting algorithm, which works
by repeatedly exchanging adjacent elements, if necessary.
When no exchanges are required, the file is sorted.
 Algorithm
• Step 1 − Check if the first element in the input array is greater
than the next element in the array.
• Step 2 − If it is greater, swap the two elements; otherwise
move the pointer forward in the array.
• Step 3 − Repeat Step 2 until we reach the end of the array.
• Step 4 − Check if the elements are sorted; if not, repeat the
same process (Step 1 to Step 3) from the last element of the
array to the first.
• Step 5 − The final output achieved is the sorted array.
BubbleSort(A, n)
1. Repeat the following steps for i = 0 to
n-1:
a. Set a flag `swapped` = false.
b. Repeat for j = 0 to n-i-1:
i. If A[j] > A[j+1], then:
- Swap A[j] and A[j+1]
- Set `swapped` = true
c. If `swapped` is false:
- Break out of the loop (array is
sorted)
2. End
 Analysis
Here, the number of comparisons are
• 1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)
• Clearly, the graph shows the n2 nature of the
bubble sort.
Bubble sort(A,n)
{
Pass for (i=0;i<n-1;i++)
{
For (j=0;j<n-1-i;j++)
{
if(A[j]>A[j+1])
{
temp=A[j]
A[j]=A[j+1]
A[j+1]=temp
}
}
}
}
 Example
• We take an unsorted array for our example. Bubble sort takes
Ο(n2) time so we're keeping it short and precise.

• Bubble sort starts with very first two elements, comparing them to check
which one is greater.

• In this case, value 33 is greater than 14, so it is already in sorted locations.

Next, we compare 33 with 27.
 Example

• We find that 27 is smaller than 33 and these two values must be swapped.

• Next we compare 33 and 35. We find that both are in already sorted
positions.
Example
 Advantages and disadvantages (Bubble sort)

Advantages disadvantages
The primary advantage of the bubble sort The main disadvantage of the bubble sort
is that it is popular and easy to is the fact that it does not deal well with a
implement. list containing a huge number of items.
In the bubble sort, elements are swapped The bubble sort requires n-squared
in place without using additional processing steps for every n number of
temporary storage. elements to be sorted.
The bubble sort is mostly suitable for
The space requirement is at a minimum academic teaching but not for real-life
applications
 Practice examples
1. arr = [64, 34, 25, 12, 22, 11, 90]
2. arr = [5, 3, 8, 1, 2]
3. arr = [67 44 82 17 20]
Selection sort
 Selection sort
• Selection sort is an in-place comparison sort
algorithm. In this algorithm, we repeatedly select the
smallest remaining element and move it to the end of
a growing sorted list. It is one of the simplest sorting
algorithm. Selection sort is known for its simplicity. It
has performance advantages over more complicated
algorithms in certain situations.
• This algorithm is not suitable for large data sets as its
average and worst case complexities are of Ο(n2),
where n is the number of items.
 Selection sort
Algorithm:
Step 1: Set MIN to location 0
Step 2: Search the minimum element in the list
Step 3: Swap with value at location MIN
Step 4: Increment MIN to point to next element
Step 5: Repeat until list is sorted
For i1 to n-1 do
min ji;
min xA[i];
for j i+1 to n do
if A[j]<min x then
min xA[j]
A[min j] A[i]
A[i]min x
For i-1 to n-1
min=i
for j=i+1 to n
if list[j]<list[min] then
min=j;
end if
end for
swap list[min] and list [i]
end for
 Selection sort
Advantages of Selection Sort Algorithm
• Simple and easy to understand.
• Works well with small datasets.
Disadvantages of the Selection Sort Algorithm
• Selection sort has a time complexity of O(n^2) in the
worst and average case.
• Does not work well on large datasets.
• Does not preserve the relative order of items with
equal keys which means it is not stable.
 Practice example (Selection sort)

• Arr = [29, 72, 98, 43 87,66, 52, 56,13]

• Arr = [4, 9, 5, 1, 0]
• Arr = [20, 12, 10, 15, 2]
• Arr = [22, 11, 9 15,4]