Sorting Techniques

3
(Insertion Sort, Selection Sort and Bubble Sort Algorithms)

“First, master the fundamentals.”

–Larry Bird

“I long to accomplish great and noble task, but

it is my chief duty to accomplish small tasks as
if they were great and noble.”
–Helen Keller

“Success is neither magical nor mysterious. Success

is the natural consequence of consistently applying
the basic fundamentals.”
–Jim Rohn
3.1. Sorting.
 In computer science, sorting means “Ordering”.
 The process of arrangement of elements of a list or elements of a set or records of a file in a particular order based upon
the condition is called Sorting. Here, elements may be numeric values(numbers) or alphabets(characters) or alphanumeric
values (combination of both alphabets and numbers). Here, order may be ascending order or descending order or
lexicographical order.
 If the elements that are arranged based on their sequence order rule, then the sequence is called “Collating sequence”
Example: - alphabetical sequence or numeric sequence number.
 The elements are said to in ascending order, if and only if they are arranged from smaller to larger.
Example: - if e1,e2,e3,….,ei are in ascending order iff e1≤e2≤e3≤….≤ei
 The elements are said to in descending order, if and only if they are arranged from larger to smaller.
Example: - if e1,e2,e3,….,ei are in ascending order iff e1≥e2≥e3≥….≥ei
 The words or strings are said to in lexicographical order if and only if they are in the same way what they appear in
the dictionary. Hence it is also called dictionary order or alphabetical order.
Examples:
Unsorted List: Sorted List:
{34,12,78,65,90,11,45} {11,12,34,45,65,78,90}
{tea,coffee,cocoa,milk,malt,choclate} {choclate,cocoa,coffee,malt,milk,tea}
{n12n,m34b,n24x,a78h,g56v,m12k,k34d} {a78h,g56v,k34d,m12k,m34b,n12n,n24x}

3.2. General terms used in sorting

(a)Sort order: - Sort order is the sequence in which data is arranged based on certain criteria such by letters, dates,
numbers, etc., The sort order determines how the data items are organized.
Examples: -
Common data sorted in ascending sequence are the dictionary and the telephone book.
Common data sorted in descending sequence are the percentages of marks, etc.,
(b)Sort stability: - sort stability is an attribute of a sort, indicating that the data with equal keys maintain their relative input
order in the output.
 A sorting algorithm is said to be stable if elements with the same value appear in the same order after sorting as
they were before sorting.
Example: - Suppose we have student records sorted by marks is as follows
Name Marks
Rama 85
Sita 90
Laxman 85
Ravan 95

Here Rama and Laxman both have 85 marks

After sorting by marks in ascending order then the marks is as follows.

[Link] 2
 Name Marks
Rama 85
Laxman 85
Sita 90
Ravan 95
Here Rama appears before Laxman, same as in original list. So, sort is stable
Some of stable sorting algorithms are Bubble sort, Insertion sort, Merge sort.
 A sorting algorithm is said to be unstable if elements with the same value not appear in the same order after
sorting as they were before sorting.
After sorting by marks in ascending order then the marks is as follows.
Name Marks
Laxman 85
Rama 85
Sita 90
Ravan 95
Here, the order of Rama and Laxman changed. So, sort is unstable.
Some of unstable sorting algorithms are Quick sort, Heap sort, Selection sort.
(c)Sort efficiency: - Sort efficiency is the measure of how much amount of space and time taken to sort the data by the
sorting algorithm.
Algorithm name Best Case Average case Worst case efficiency

Insertion sort O(n) O(n2) O(n2) Good for small data

Bubble sort O(n) O(n2) O(n2) Less efficient

Merge sort O(n log n) O(n log n) O(n log n) More efficient

Quick sort O(n log n) O(n log n) O(n2) Very efficient (average case)

(d)Sort pass: - A sort pass is one complete traversal of the list during sorting, where comparisons and possible swaps are
performed. Depending up on the algorithm, the sort pass may traverse the whole list or just a selection of the
list.

3.3. Classification of Sorting’s.

Depending up on the consideration of memory for sorting, we classify them into two types.

Sorting’s

Internal External
Sorting Sorting

[Link] 3
Internal Sorting: -
 When-ever, the size of data is less than the size of main memory then we prefer the internal sorting.
 The process of sorting data which is completely stored in the computer’s main memory (RAM) or Primary memory (or)
internal memory then it is called internal sorting.
 It is mainly used for sorting small and medium sized data.
The following are the features of Internal Sorting
(a) Internal sorting can be used when small amount of data sets or medium sized data sets has to be sorted.
(b) In case of internal sorting process, all data is available in RAM before sorting begins.
(c) In this, data can be accessed randomly.
(d) Internal sorting will execute faster due to high-speed memory access.
(e) Internal Sorting Algorithms are independent of time to read or write the element. Because the read or write time of main
memory is negligible.
Examples of Internal Sorting Algorithms: -Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort, Heap Sort, Shell
Sort, Radix Sort.
Advantages of Internal Sorting’s are as follows
(a) Internal sorting’s are high in speed
(b) These are easy to implement
(c) Less I/O overhead
Disadvantages of Internal Sorting’s are as follows
 It is not suitable for very large datasets that exceed memory size
External Sorting: -
 When-ever, the size of data is greater than the size of main memory then we prefer the external sorting.
 The process of sorting data that is too large to fit entirely into the computer’s main memory (RAM), so external storage
devices like hard disks are used for sorting. Hence it is called external sorting.
 It is mainly used for very large datasets, such as files in databases or large data processing systems.
The following are the features of External Sorting
(a) External sorting can be used when large amount of data sets has to be sorted.
(b) In case of external sorting process, data does not fit completely in RAM. It uses external storage (disk, SSD, etc.).
(c) In this, data can be accessed sequential order.
(d) External sorting will execute slowly due to disk I/O operations are slower than memory access.
(e) External Sorting Algorithms are not independent of time to read or write the element. Because it involves multiple read/write
(I/O) operations.
(f) Data is divided into smaller chunks, sorted separately, and then merged.
Examples of external sorting algorithms: Natural Merge Sort, Balanced Merge Sort, K-way Merge, Polyphase Merge
Advantages of External Sorting’s are as follows
(a) Can handle very large files.
(b) Suitable for database and big data applications.
Disadvantages of External Sorting’s are as follows.
(a) Slower than internal sorting due to disk I/O.
(b) More complex to implement.

[Link] 4
Differences between Internal Sorting and External Sorting:
SNO Internal Sorting External Sorting
1 If we sort the data by using only main memory is called If we sort the data by using both main memory as well as
Internal sorting secondary memory is called External sorting
2 Internal sorting methods are preferred whenever size of External sorting methods are preferred whenever size of
data is small-than the size of main memory. data is larger-than the size of main memory.
3 In case of internal sorting process, all data is available In case of external sorting process, data does not fit
in RAM before sorting begins. completely in RAM. It uses external storage (disk, SSD,
etc.).
4 In this, data can be accessed randomly. In this, data can be accessed sequential order
5 Internal sorting will execute faster due to high-speed External sorting will execute slowly due to disk I/O
memory access. operations are slower than memory access.
6 Internal Sorting Algorithms are independent of time to External Sorting Algorithms are not independent of time
read or write the element. Because the read or write to read or write the element. Because it involves multiple
time of main memory is negligible. read/write (I/O) operations.
7 The cost of accessing data is minimal. The cost of accessing data is high
8 The records are accessed several times. The records are accessed very few times.
9 These internal sorting techniques are simple to These external sorting techniques are complex to
implement. implement.

3.4. Types of Sorting Techniques.

Many sorting algorithms have been invented. Each having its own advantages and dis-advantages. These algorithms can be classified
into families such as
1. Sorting by Insertion
2. Sorting by Selection
3. Sorting by Exchange
4. Sorting by Distribution
5. Sorting by Merging
1. Sorting by insertion is a sorting technique in which elements are sorted by inserting each element into its proper position
in a previously sorted portion of the list.
Example: - Insertion Sort. Binary Insertion Sort, Shell Sort

2. Sorting by selection is a sorting technique in which the smallest (or largest) element is repeatedly selected from the
unsorted portion of the list and placed in its correct position.
Example: - Selection Sort, Heap Sort, Tournament Sort

3. Sorting by exchange (or) Transposition is a sorting technique in which elements are sorted by repeatedly exchanging
(swapping) pairs of elements that are in the wrong order.
Example: - Bubble Sort, Quick Sort, Exchange Sort, Cocktail Shaker Sort (Bidirectional Bubble Sort), Odd-Even Sort

4. Sorting by distribution is a sorting technique in which elements are distributed (placed) into different groups or buckets
based on their values, and then collected back in order to form a sorted list.
Example: - Counting Sort, Bucket Sort, Radix Sort

5. Sorting by merging is a sorting technique in which a list is divided into smaller sub lists, sorted separately, and then
merged together to produce a sorted list.
Example: - Merge Sort and its variants such as Natural Merge, polyphase Merge, balanced Merge.

[Link] 5
Insertion Sort
 Insertion sort as the name indicates that belongs to a family of sorting by Insertion.
 Insertion sort is a comparison-based sorting algorithm and in-place sorting algorithm.
 Insertion sort sorts a list by repeatedly inserting elements into their correct position within the sorted part of the list.
 It’s called “insertion” sort because we insert each element where it belongs in the sorted sequence.
 since each element finds its appropriate position in the sorted list, such a technique is called as sinking or sifting technique.
 It works the same way people arrange playing cards in their hands — one card at a time, placing each card in its correct
position among the already sorted cards.
Working Process:
Step1: -Assume the first element is already sorted.
Step2: -Take the next element.
Step3: -Compare it with elements in the sorted portion.
Step4: -Shift larger elements one position to the right.
Step5: -Insert the element in its correct position.
Step6: -Repeat until all elements are sorted

Example: - Let L= {16,36,4,22,100,1,54} be an unordered list of elements. Apply insertion sort to sort the unordered list in
ascending order and find the following.
(i) Find number of positions moved in each pass and also find total number of positions moved
for the completion of sorting process.
(ii) Find number of comparisons for each pass and also find total number of comparisons required for
completion of sorting process.
(iii) Find total number of passes for the completion of sorting process.

Given number of elements n=7 and List L= {16,36,4,22,100,1,54}

Original 16 36 4 22 100 1 54 Number of Positions Number of comparisons in

List Moved/shifts in each pass each pass
After Pass1 16 36 4 22 100 1 54 0 1
After Pass2 4 16 36 22 100 1 54 2 2
After Pass3 4 16 22 36 100 1 54 1 2
After Pass4 4 16 22 36 100 1 54 0 1
After Pass5 1 4 16 22 36 100 54 5 5
After Pass6 1 4 16 22 36 54 100 1 2

After sorting process, the sorted list L= {1,4,16,22,36,54,100}

Total positions moved for the completion of sorting process=0+2+1+0+5+1=9
Total number of comparisons for the completion of sorting process=1+2+2+1+5+2=13
Total Number of passes for the completion of sorting process=(n-1) = (7-1) =6

Example: - Let L= {34,8,64,51,32,21} be an unordered list of elements. Apply insertion sort to sort the unordered list in
descending order and find the following.
(i) Find number of positions moved in each pass and also find total number of positions moved
for the completion of sorting process.
(ii) Find number of comparisons for each pass and also find total number of comparisons required for
completion of sorting process.
(iii) Find total number of passes for the completion of sorting process.

Given number of elements n=6 and List L= {34,8,64,51,32,21}

Original 34 8 64 51 32 21 Number of Positions Number of comparisons in

List Moved/shifts in each pass each pass
After Pass1 34 8 64 51 32 21 0 1
After Pass2 64 34 8 51 32 21 2 2
After Pass3 64 51 34 8 32 21 2 3
After Pass4 64 51 34 32 8 21 1 2
After Pass5 64 51 34 32 21 8 1 2

[Link] 6
 After sorting process, the sorted list L= {64,51,34,32,21,8}
Total positions moved for the completion of sorting process=0+2+2+1+1=6
Total number of comparisons for the completion of sorting process=1+2+3+2+2=10
Total Number of passes for the completion of sorting process=(n-1) = (6-1) =5

Example: - Let L= {P, N, M, K, H} be an unordered list of elements. Apply insertion sort to sort the unordered list in
ascending order and find the following.

(i) Find number of positions moved in each pass and also find total number of positions moved
for the completion of sorting process.
(ii) Find number of comparisons for each pass and also find total number of comparisons required for
completion of sorting process.
(iii) Find total number of passes for the completion of sorting process.
Original List P N M K H Number of Positions Number of comparisons in each
Moved/shifts in each pass pass
After Pass1 N P M K H 1 1
After Pass2 M N P K H 2 2
After Pass3 K M N P H 3 3
After Pass4 H K M N P 4 4

After sorting process, the sorted list L= {H,K,M,N,P}

Total positions moved for the completion of sorting process=1+2+3+4=10
Total number of comparisons for the completion of sorting process=1+2+3+4=10
Total Number of passes for the completion of sorting process=(n-1) = (5-1) =4

Advantages of Insertion Sort:

 It is simple to implement.
 It is a simple sorting algorithm in which the elements are sorted by considering one element at a time.
 It works well for small data sets.
 This is stable sort.

Dis-advantages of Insertion Sort:

 As the number of elements increases, the performance of the program will be increases.

Stability of Insertion Sort: -Insertion sort is stable sort. Because it will maintain their relative input order in the output.
Example: -Consider a list L= {31,1,21,32,33,22} here repeated keys have been superscripted with numbers indicative of their relative
orders of occurrence.

Original List 31 1 21 32 33 22 Number of Positions

Moved/shifts in each pass
After Pass1 1 31 21 32 33 22 1
After Pass2 1 21 31 32 33 22 1
After Pass3 1 21 31 32 33 22 0
After Pass4 1 21 31 32 33 22 0
After Pass5 1 21 22 31 32 33 3

From the above, we observe that before sorting, the relative order of elements in input is same as the relative order of elements in
Output after sorting. So, insertion sort is stable sort.

Final Conclusion
Insertion Sort is:
 Efficient for small or nearly sorted arrays
 Quadratic in worst and average cases
 In-place and stable
 Linear in best case
 Adaptive

[Link] 7
Non-Recursive Algorithm for Insertion Sort: -The Non recursive algorithm for insertion sort is as follows.

Algorithm inssort(a[],n)
{
for(i=0;i<n;i++)
{
temp=a[i];
for(j=i;j>0&&a[j-1]>temp;j--)
{
a[j]=a[j-1];
}
a[j]=temp;
}
}
Tracing: - The way of executing each instruction in an algorithm is called “Tracing”.
j=2; 2>0 && a[2-1]>temp
Let an array a=[34,8,52,32,21] and n=5 2>0 && a[1]>temp
2>0 && 34>32True
0 1 2 3 4 a[2]=a[2-1]=a[1]=34 and j—
j=1; 1>0 && a[1-1]>temp
34 8 52 32 21 1>0 && a[0]>temp
1>0 && 8>32False
i=0 ; 0<5True no shifting
temp=a[0]=34
j=0; 0>0False a[1]=32 and i++
no shifting after this array is as follows
a[0]=34 and i++ 0 1 2 3 4
after this array is as follows
0 1 2 3 4 8 32 34 52 21

34 8 52 32 21 i=4; 4<5True
temp=a[4]=21
i=1; 1<5True j=4; 4>0 && a[4-1]>temp
temp=a[1]=8 4>0 && a[3]>temp
j=1; 1>0 && a[1-1]>temp 4>0 && 52>21True
1>0 && a[0]>temp a[4]=a[4-1]=a[3]=52 and j—
1>0 && 34>8True j=3; 3>0 && a[3-1]>temp
a[1]=a[1-1]=a[0]=34 and j— 3>0 && a[2]>temp
j=0; 0>0False 3>0 && 34>21True
no shifting a[3]=a[3-1]=a[2]=34 and j—
a[0]=8 and i++ j=2; 2>0 && a[2-1]>temp
after this array is as follows 2>0 && a[1]>temp
0 1 2 3 4 2>0 && 32>21True
a[2]=a[2-1]=a[1]=32 and j—
8 34 52 32 21 j=1; 1>0 && a[1-1]>temp
1>0 && a[0]>temp
i=2; 2<5True 1>0 && 8>21False
temp=a[2]=52 no shifting
j=2; 2>0 && a[2-1]>temp a[1]=21
2>0 && a[1]>temp after this array is as follows
2>0 && 34>52False 0 1 2 3 4
no shifting
a[2]=52 and i++ 8 21 32 34 52

0 1 2 3 4 After sorting the final sorted array is as follows

8 34 52 32 21 0 1 2 3 4

i=3; 3<5True 8 21 32 34 52
temp=a[3]=32
j=3; 3>0 && a[3-1]>temp
3>0 && a[2]>temp
3>0 && 52>32True
a[3]=a[3-1]=a[2]=52 and j—

[Link] 8
Recursive Algorithm for Insertion Sort: -The working process of recursive insertion sort will involve two phase manner.
1. Recursive Phase (winding Phase)
2. Insertion Phase (Un-winding Phase)
1. Recursive Phase: - The function calls itself until we reach base condition. These recursive calls are stored in the stack.
2. Insertion Phase: - Now for each pop of recursive call, stack unwinding takes place. This phase involves the following steps.
(a) If the array has one or zero elements then it is already sorted so we can return. Otherwise
(b) Recursively sort the first n-1 elements.
(c) Insert the nth element (last element) into its correct position in the sorted part.
The algorithm for recursive insertion sort is as follows.
Algorithm RecInsSort(a[], n)
{
if(n <= 1)
return;
RecInsSort(a, n-1);
last = a[n-1];
j = n-2;
while(j >= 0 && a[j] > last)
{
a[j+1] = a[j];
j = j - 1;
}
a[j+1] = last;
}

Tracing: - The way of executing each instruction in an algorithm is called “Tracing”.

Let an array a=[34,8,52,32,21]

n=5
RecInsSort(a,n)-RecInsSort(a,5)
n<=1-5<=1-False
RecInsSort(a,5-1)
RecInsSort(a,4)

RecInsSort(a,n)-RecInsSort(a,4)
n<=1-4<=1-False
RecInsSort(a,4-1)
RecInsSort(a,3)

RecInsSort(a,n)-RecInsSort(a,3)
n<=1-3<=1-False
RecInsSort(a,3-1)
RecInsSort(a,2)

RecInsSort(a,n)-RecInsSort(a,2)
n<=1-2<=1-False
RecInsSort(a,2-1)
RecInsSort(a,1)

RecInsSort(a,n)-RecInsSort(a,1)
n<=1-1<=1-True
return

Here n=1 so we return to base condition.

The recursive calls happen like this:
RecInsSort(a,5)
└── RecInsSort(a,4)
└── RecInsSort(a,3)
└── RecInsSort(a,2)
└── RecInsSort(a,1)

[Link] 9
For each call: while(j>=0 && a[j]>last)
 last = a[n-1] → element to insert (1>=0 && a[1]>32)
 j = n-2 → compare backward (1>=0 && 34>32)--True
 Shift larger elements right a[j+1]=a[j]-a[1+1]=a[1]-a[2]=34
 Place last in correct location j=j-1-j=1-1=0
Now recursion starts bottom to upwards and insertion
begins while(j>=0 && a[j]>last)
0 1 2 3 4 (0>=0 && a[0]>32)
(0>=0 && 8>32)--False
34 8 52 32 21
a[j+1]=last-a[0+1]=32-a[1]=32
for n=2
last=a[n-1]--last=a[2-1]=a[1]=8 after this array is as follows
j=n-2-j=2-2=0 0 1 2 3 4
while(j>=0 && a[j]>last)
(0>=0 && a[0]>8) 8 32 34 52 21
(0>=0 && 34>8)--True
a[j+1]=a[j]-a[0+1]=a[0]-a[1]=34 for n=5
j=j-1-j=0-1=-1 last=a[n-1]-last=a[5-1]=a[4]=21
j=n-2-j=5-2=3
while(-1>=0 && a[-1]>last) while(j>=0 && a[j]>last)
(-1>=0 && a[0]>8)-False (3>=0 && a[3]>21)
(3>=0 && 52>21)--True
a[j+1]=last-a[-1+1]=last--a[0]=8 a[j+1]=a[j]-a[3+1]=a[3]-a[4]=52
after this array is as follows j=j-1-j=3-1=2
0 1 2 3 4 while(j>=0 && a[j]>last)
(2>=0 && a[2]>21)
8 34 52 32 21 (2>=0 && 34>21)--True
a[j+1]=a[j]-a[2+1]=a[2]-a[3]=34
for n=3 j=j-1-j=2-1=1
last=a[n-1]--last=a[3-1]=a[2]=52
j=n-2-j=3-2=1 while(j>=0 && a[j]>last)
while(j>=0 && a[j]>last) (1>=0 && a[1]>21)
(1>=0 && a[1]>52) (1>=0 && 32>21)--True
(1>=0 && 34>52)--False a[j+1]=a[j]-a[1+1]=a[1]-a[2]=32
j=j-1-j=1-1=0
a[j+1]=last--a[1+1]=52-a[2]=52
after this array is as follows while(j>=0 && a[j]>last)
0 1 2 3 4 (0>=0 && a[0]>21)
8 34 52 32 21 (0>=0 && 8>21)--False

for n=4 a[j+1]=last--a[0+1]=21--a[1]=21

last=a[n-1]-last=a[4-1]=a[3]=32
j=n-2-j=4-2=2 after this array is as follows
while(j>=0 && a[j]>last) 0 1 2 3 4
(2>=0 && a[2]>32) 8 21 32 34 52
(2>=0 && 52>32)--True
a[j+1]=a[j]-a[2+1]=a[2]-a[3]=52
j=j-1-j=2-1=1

Efficiency of Insertion Sort: - Let ‘n’ be the number of elements, temp be the current element and ‘j’ be the index used to move
elements backward.
Step 1: Define Inner Loop Iterations
Let ti be the number of times inner loop executes for index ‘i’
Then total running time:

where:

[Link] 10
 = constant cost of outer loop work
= cost per inner loop iteration

Worst Case (Reverse Sorted)

In reverse sorted array: For each ‘i’, inner loop runs ‘i’ times.
So:

Total time:

Split summation:

= C1 n + C2 (n2 -n)

2
Dominant term:

Best Case (Already Sorted)

Inner loop condition fails immediately.
So:

Thus:

Average Case
For random array:

Thus:

Space Complexity
 It uses only temp and j as extra variables
 It Sorts array in-place

[Link] 11
Selection Sort
 Selection sort as the name indicates that belongs to a family of sorting by Selection.
 Selection sort is a comparison-based sorting algorithm and In Place sorting algorithm.
 Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the array and places it at the
correct position in the sorted portion.
 It is called “selection” sort because it repeatedly selects the next minimum (or maximum) element.
Working Process:
Step1: - Start from the first element.
Step2: - Find the smallest element in the entire list.
Step3: - Swap it with the element in the first position.
Step4: - Move to the next position.
Step5: - Again, find the smallest element from the remaining unsorted part and swap it with the element in the second position.
Step6: - Repeat the above process until all elements are sorted.

Example: - Let L= {12,21,50,14,2,20} be an unordered list of elements. Apply Selection sort to sort the unordered list in
ascending order and find the following.
(i) Find the total number of swaps for the completion of sorting process.
(ii) Find total number of comparisons required for completion of sorting process.
(iii) Find total number of passes for the completion of sorting process.
Given number of elements n=6 and List L= {12,21,50,14,2,20}

Initial list pass1 pass2 pass3 pass4 pass5

a[0] 12 2 2 2 2 2

a[1] 21 21 12 12 12 12

a[2] 50 50 50 14 14 14

a[3] 14 14 14 50 20 20

a[4] 2 12 21 21 21 21
a[5] 20 20 20 20 50 50

After sorting process, the sorted list L= {2,12,14,20,21,50}

Total number of swaps for the completion of sorting process=(n-1) = (6-1) =5 swaps
Total number of comparisons for the completion of sorting process=(n*(n-1))/2 = (6*(6-1))/2 = (6*5)/2 =30/2 =15
Total Number of passes for the completion of sorting process=(n-1) = (6-1) =5

Advantages of Selection Sort:

 The algorithm is straightforward and easy to code.
 It is In-place Sorting and requires only O(1) extra memory (no additional storage needed).
 It performs at most (n − 1) swaps, which is useful when swapping is costly.
 It is efficient enough for small lists.

Disadvantages of Selection Sort

 Time complexity is O(n²) in best, average, and worst cases.
 It is Not Stable. Because it does not preserve the relative order of equal elements (by default).
 It is not Adaptive. Because it does not perform better on nearly sorted data.
 It is inefficient for Large Datasets. Because much slower compared to advanced algorithms like Merge Sort or Quick Sort.

Stability of Selection Sort: -Selection sort is not stable sort. Because it will not maintain their relative input order in the output.
Example: -Consider a list L= {61,62,2} here repeated keys have been superscripted with numbers indicative of their relative
orders of occurrence.
Original List 61 62 2 Swap elements
1
After Pass1 2 2
6 6 Swap(2,61)
From the above, we observe that before sorting, the relative order of elements in input is not same as the relative order of elements in
output after sorting. So, selection sort is not stable sort

[Link] 12
Non-Recursive Algorithm for Selection Sort: -The Non recursive algorithm for Selection sort is as follows.

Algorithm SelectionSort(a[], n){

for(i=0;i<=(n – 2);i++){
min=i;
for(j=i + 1;j<= (n – 1);j++){
if(a[j] < a[min]){
min=j
}
if(min != i){
temp=a[i];
a[i]=a[min]
a[min]=temp
}
}
}
Tracing: - The way of executing each instruction in an algorithm is called “Tracing”.
after this array is as follows
Let an array a=[34,8,52,32,21] and n=5 0 1 2 3 4

0 1 2 3 4 8 21 52 32 34

34 8 52 32 21 i=2; 2<=(5-2)--2<=3--True
min=i--min=2
i=0; 0<=(5-2)--0<=3--True j=i+1;j<=(n-1)--j=2+1;3<=(5-1)-j=3;3<=4-True
min=i--min=0 if(a[3]<a[2])--if(32<52)--True
j=i+1;j<=(n-1)--j=0+1;1<=(5-1)-j=1;1<=4-True min=3 and j++
if(a[1]<a[0])--if(8<34)--True j=4;4<=4-True
min=1 and j++ if(a[4]<a[3]--if(34<32)--False so j++
j=2;2<=4-True j=5;5<=4-False
if(a[2]<a[1]--if(52<8)--false so j++ if(min!=i)-if(3!=2)--True
j=3;3<=4-True temp=a[2]temp=52
if(a[3]<a[1])-if(32<8)--false so j++ a[i]=a[min]-a[2]=a[3]--a[2]=32
j=4;4<=4-True a[min]=temp-a[3]=52
if(a[4}<a[1])-if(21<8)--false so j++ i++
j=5;5<=4-false after this array is as follows
if(min!=i)-if(1!=0)--True 0 1 2 3 4
temp=a[0]temp=34
a[i]=a[min]-a[0]=a[1]--a[0]=8 8 21 32 52 34
a[min]=temp-a[1]=34
i++ i=3; 3<=(5-2)--3<=3--True
after this array is as follows min=i--min=3
0 1 2 3 4 j=i+1;j<=(n-1)--j=3+1;4<=(5-1)-j=4;4<=4-True
if(a[4]<a[3])--if(34<52)--True
8 34 52 32 21 min=4 and j++
j=5;5<=4-False
i=1; 1<=(5-2)--1<=3--True if(min!=i)-if(4!=3)--True
min=i--min=1 temp=a[3]temp=52
j=i+1;j<=(n-1)--j=1+1;2<=(5-1)-j=2;2<=4-True a[i]=a[min]-a[3]=a[4]--a[3]=34
if(a[2]<a[1])--if(52<34)--False so j++ a[min]=temp-a[4]=52
j=3;3<=4-True i++
if(a[3]<a[1]--if(32<34)--True after this array is as follows
min=3 and j++ 0 1 2 3 4
j=4;4<=4-True
if(a[4]<a[3])-if(21<32)--True 8 21 32 34 52
min=4 and j++ i=4; 4<=(5-2)--4<=3--False so stop
j=5;5<=4-false
if(min!=i)-if(4!=1)--True After sorting the final sorted array is as follows
temp=a[1]temp=34
a[i]=a[min]-a[1]=a[4]--a[1]=21 0 1 2 3 4
a[min]=temp-a[4]=34
i++ 8 21 32 34 52

[Link] 13
Recursive Algorithm for Selection Sort: -The algorithm for recursive selection sort is as follows.
recselsort(a, n, i){
if(i ≥ n – 1){
return;
}
min=i;
for(j=i+1;j<=(n-1);j++){
if(a[j] < a[min])
min=j;
}
if(min ≠ i){
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
recselsort(a,n,i+1);
}
Tracing: - The way of executing each instruction in an algorithm is called “Tracing”.

Let an array a=[34,8,52,32,21] and n=5 after this the array becomes:
0 1 2 3 4 0 1 2 3 4
34 8 52 32 21 8 21 52 32 34

recselsort(a,n,i)recselsort(a,5,0) recselsort(a,n,i+1)-recselsort(a,5,1+1)--recselsort(a,5,2)
if(i>=n-1)-(0>=5-1)-(0>=4)-False if(i>=n-1)-(2>=5-1)-(2>=4)-False
min=i-min=0 min=i-min=2
j=i+1-j=0+1-j=1;1<=(5-1)-True j=i+1-j=2+1-j=3;3<=(5-1)-True
if(a[1]<a[0])-if(8<34)-True. if(a[3]<a[2])-if(32<52)-True.
mid=1 and j++ min=3 and j++
j=2-2<=(5-1)-True j=4-4<=(5-1)-True
if(a[2]<a[1])-if(52<8)-False. So j++ if(a[4]<a[3])-if(34<32)-False. So j++
j=3-3<=(5-1)-True j=5-5<=(5-1)-False. So exit
if(a[3]<a[1])-if(32<8)-False. So j++ if(min!=i)-if(3!=2)-True
j=4-4<=(5-1)-True temp=a[i]-temp=a[2]-temp=52
if(a[4]<a[1])-if(21<8)-False. So j++ a[2]=a[3]-a[2]=32
j=5-5<=(5-1)-False. So exit a[3]=temp-a[3]=52
if(min!=i)-if(1!=0)-True after this the array becomes:
temp=a[i]-temp=a[0]-temp=34 0 1 2 3 4
a[0]=a[1]-a[0]=8
a[1]=temp-a[1]=34 8 21 32 52 34
after this the array becomes:
0 1 2 3 4 recselsort(a,n,i+1)-recselsort(a,5,2+1)--recselsort(a,5,3)
if(i>=n-1)-(3>=5-1)-(3>=4)-False
8 34 52 32 21 min=i-min=3
j=i+1-j=3+1-j=4;4<=(5-1)-True
recselsort(a,n,i+1)-recselsort(a,5,0+1)--recselsort(a,5,1) if(a[4]<a[3])-if(34<52)-True.
if(i>=n-1)-(1>=5-1)-(1>=4)-False min=4 and j++
min=i-min=1 j=5-5<=(5-1)-False. So exit
j=i+1-j=1+1-j=2;2<=(5-1)-True if(min!=i)-if(4!=3)-True
if(a[2]<a[1])-if(52<34)-False. So j++ temp=a[i]-temp=a[3]-temp=52
j=3-3<=(5-1)-True a[3]=a[4]-a[3]=34
if(a[3]<a[1])-if(32<34)-False. So j++ a[4]=temp-a[4]=52
j=4-4<=(5-1)-True after this the array becomes:
if(a[4]<a[1])-if(21<34)-True. 0 1 2 3 4
mid=4 and j++
j=5-5<=(5-1)-False. So exit 8 21 32 34 52
if(min!=i)-if(4!=1)-True
temp=a[i]-temp=a[1]-temp=34 recselsort(a,n,i+1)-recselsort(a,5,3+1)--recselsort(a,5,4)
a[1]=a[4]-a[1]=21 if(i>=n-1)-(4>=5-1)-(4>=4)-False
a[4]=temp-a[4]=34 min=i-min=4
j=i+1-j=4+1-j=5;5<=(5-1)-False. So exit
if(min!=i)-if(4!=4)-False
recselsort(a,n,i+1)-recselsort(a,5,4+1)--recselsort(a,5,5)
if(i>=n-1)-(5>=5-1)-(5>=4)-True
return
[Link] 14
Efficiency of Selection Sort: - let us consider the selection sort algorithm
Algorithm SelectionSort(a[], n){
for(i=0;i<=(n – 2);i++){
min=i;
for(j=i + 1;j<= (n – 1);j++){
if(a[j] < a[min]){
min=j
}
if(min != i){
temp=a[i];
a[i]=a[min]
a[min]=temp
}
}
}

Now consider outer Loop

for(i = 0; i <= n-2; i++)
This runs (n-1) times

Now consider inner loop

for(j = i+1; j <= n-1; j++)

Number of iterations depends on i.

When:
i = 0 → j runs from 1 to n−1 → n−1 comparisons
i = 1 → j runs from 2 to n−1 → n−2 comparisons
i = 2 → j runs from 3 to n-3 -n−3 comparisons
...
i = n−2 → 1 comparison

Total Comparisons =(n-1)+(n-2)+(n-3)+……..+1

Ignoring constants and lower-order terms:

T(n)=

The best, average and worst time complexity of selection sort is

Space Complexity: Extra variables used are i, j, min, temp. These require constant [Link] extra arrays are used.
So,space used is independent of n.

Selection Sort is an in-place quadratic sorting algorithm.

[Link] 15
Bubble Sort
 Bubble sort belongs to a family of sorting by exchange or sorting by Transposition.
 Bubble sort is a comparison-based sorting algorithm and In Place sorting algorithm.
 Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order.
 It is called “bubble” sort because after each pass, the largest unsorted element “bubbles up” to its correct position at the
end of the array.
Working Process:
Step1: -Compare the first two elements.
Step2:- Swap if the first is greater than the second.
Step3:- Move to the next pair.
Step4:- Continue until the end of the array.
Step5:- Repeat the process for the remaining unsorted part.
Example: - Let L= {12,21,50,14,2,20} be an unordered list of elements. Apply Bubble sort to sort the unordered list in
ascending order and find the following.
(i) Find the total number of swaps for the completion of sorting process.
(ii) Find total number of comparisons required for completion of sorting process.
(iii) Find total number of passes for the completion of sorting process.

Given L={12,21,50,14,2,20} and number of elements n=6 Pass 4: Take pass 3 sorted list L=[12,2,14,20,21,50]
Compare adjacent elements
Pass 1: Take the list L={12,21,50,14,2,20} (12,2) --swap(12,2) --[2,12,14,20,21,50]
Compare adjacent elements (12,14) ---No swap --[2,12,14,20,21,50]
(12,21) --No swap --[12,21,50,14,2,20]
(21,50) ---No swap --[12,21,50,14,2,20] Now largest element 14 is now at the fourth end
(50,14) ---swap(50,14) --[12,21,14,50,2,20] After pass 4 the sorted list L=[2,12,14,20,21,50]
(50,2) ---swap(50,2) --[12,21,14,2,50,20]
(50,20)---swap(50,20) --[12,21,14,2,20,50] Pass 5: Take pass 4 sorted list L=[2,12,14,20,21,50]
Compare adjacent elements
Now largest element 50 is now at the end (2,12) --No swap --[2,12,14,20,21,50]
After pass 1 the sorted list L=[12,21,14,2,20,50]
Now largest element 12 is now at the fifth end
Pass 2: Take pass 1 sorted list L=[12,21,14,2,20,50] After pass 5 the sorted list L=[2,12,14,20,21,50]
Compare adjacent elements
(12,21) --No swap --[12,21,14,2,20,50] After sorting process, the sorted list L= {2,12,14,20,21,50}
(21,14) ---swap(21,14) --[12,14,21,2,20,50] Total number of swaps for the completion of sorting
(21,2) ---swap(21,2) --[12,14,2,21,20,50] process= 8 swaps
(21,20) ---swap(21,20) --[12,14,2,20,21,50] Total number of comparisons for the completion of sorting
process=(n*(n-1))/2 = (6*(6-1))/2 = (6*5)/2 =30/2 =15
Now largest element 21 is now at the second end Total Number of passes for the completion of sorting
After pass 2 the sorted list L= [12,14,2,20,21,50] process=(n-1) = (6-1) =5

Pass 3: Take pass 2 sorted list L=[12,14,2,20,21,50]

Compare adjacent elements
(12,14) --No swap --[12,14,2,20,21,50]
(14,2) ---swap(14,2) --[12,2,14,20,21,50]
(14,20) ---No swap --[12,2,14,20,21,50]

Now largest element 210 is now at the third end

After pass 3 the sorted list L=[12,2,14,20,21,50]

Advantages of Bubble Sort:

 It is easy to implement because it requires only two loops and a swap operation.
 It is In-place Sorting because it does not require extra memory.
 It maintains relative order of equal elements. Hence it is a stable sort.
 It is efficient for small or nearly sorted arrays.
Disadvantages of Bubble Sort
 Time complexity is O(n²) in average, and worst cases.
 Too many comparisons
 Performs more swaps compared to selection sort.
 It is inefficient for Large Datasets.

[Link] 16
Stability of Bubble Sort: -Bubble sort is stable sort. Because it will maintain their relative input order in the output.
Example: -Consider a list L= {71 ,72, 73,6} here repeated keys have been superscripted with numbers indicative of their relative
orders of occurrence.
Original List 71 72 73 6
After Pass1 7 1
7 2
6 73
2
After Pass2 71 6 7 73
After Pass3 6 71 72 73
From the above, we observe that before sorting, the relative order of elements in input is same as the relative order of elements in
output after sorting. So, bubble sort is stable sort

Non-Recursive Algorithm for Bubble Sort: -The Non recursive algorithm for Bubble sort is as follows.
Algorithm BubbleSort(a[], n){
for(i=0;i<=(n – 2);i++){
for(j=0;j<= (n – 2-i);j++){
if(a[j] > a[j+1]){
temp=a[j];
a[j]=a[j+1]
a[j+1]=temp
}
}
}
}
i=1; 1<=(5-2)--1<=3--True
Let an array a=[34,8,52,32] and n=4 j=0;0<=(4-2-1)--True
if(a[0]>a[0+1])--if(a[0]>a[1])-if(8>34)--False
0 1 2 3 and j++
0 1 2 3
34 8 52 32
8 34 32 52
i=0; 0<=(5-2)--0<=3--True j=1;1<=(4-2-1)--True
j=0;0<=(4-2-0)--True if(a[1]>a[1+1])--if(a[1]>a[2])-if(34>32)--True
if(a[0]>a[0+1])--if(a[0]>a[1])-if(34>8)--True temp=a[1]-temp=34
temp=a[0]-temp=34 a[j]=a[j+1]-a[1]=a[1+1]-a[1]=a[2]-a[1]=32
a[j]=a[j+1]-a[0]=a[0+1]-a[0]=a[1]-a[0]=8 a[1+1]=temp-a[2]=temp-a[2]=34 and j++
a[0+1]=temp-a[1]=temp-a[1]=34 and j++
0 1 2 3
0 1 2 3
8 32 34 52
8 34 52 32
j=2;2<=(4-2-1)--False. So i++
j=1;1<=(4-2-0)--True i=2; 2<=(5-2)--2<=3--True
if(a[1]>a[1+1])--if(a[1]>a[2])-if(34>52)--False j=0;0<=(4-2-2)--True
and j++ if(a[0]>a[0+1])--if(a[0]>a[1])-if(8>32)--False
0 1 2 3 and j++
0 1 2 3
8 34 52 32
8 32 34 52
j=2;2<=(4-2-0)--True
if(a[2]>a[2+1])--if(a[2]>a[3])-if(52>32)--True j=1;1<=(4-2-2)--False. So i++
temp=a[2]-temp=52
a[j]=a[j+1]-a[2]=a[2+1]-a[2]=a[3]-a[2]=32 i=3; 3<=(5-2)--3<=3--True
a[2+1]=temp-a[3]=temp-a[3]=52 and j++ j=0;0<=(4-2-3)--False. So i++
0 1 2 3 i=4; 4<=(5-2)--4<=3---False. So exit.
8 34 32 52
Final sorted list is as follows
j=3;3<=(4-2-0)--False. So i++ 0 1 2 3
8 32 34 52

[Link] 17
Recursive Algorithm for Bubble Sort: -The algorithm for recursive Bubble sort is as follows.
recbubsort(a[], n){
if(n = 1)
return
for(i=0;i<=(n – 2);i++){
if( a[i] > a[i + 1]){
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
}
}
recbubsort(a, n - 1)
}
How It Works
Step1: -Each recursive call places the largest element at the end of the array.
Step2: -The problem size reduces by 1 (n - 1) each time.
Step3: -Stops when n = 1.

Tracing: - The way of executing each instruction in an algorithm is called “Tracing”.

Let an array a=[34,8,52,32] and n=4 i=1;1<=(3-2)---True

0 1 2 3 if(a[1]>a[1+1])--if(a[1]>a[2])-if(34>32)--True
temp=a[i]-temp=a[1]-temp=34
34 8 52 32 a[1]=a[2]-a[1]=32
a[2]=temp-a[2]=34 and i++
recbubsort(a,n)recselsort(a,4) after this the array becomes:
if(n=1)-(4=1)-False
i=0;0<=(4-2)---True 0 1 2 3
if(a[0]>a[0+1])--if(34>8)--True
temp=a[i]-temp=a[0]-temp=34 8 34 32 52
a[0]=a[1]-a[0]=8
a[1]=temp-a[1]=34 and i++ i=2;2<=(3-2)--False
after this the array becomes: after this the array becomes:
0 1 2 3 0 1 2 3
8 34 52 32 8 32 34 52

i=1;1<=(4-2)---True recbubsort(a,n-1)recselsort(a,3-1)--recbubsort(a,2)
if(a[1]>a[1+1])--if(a[1]>a[2])-if(34>52)--False. So i++ if(n=1)-(2=1)-False
i=2;2<=(4-2)--True i=0;0<=(2-2)---True
if(a[2]>a[2+1)--if(a[2]>a[3])--if(52>32)--True if(a[0]>a[0+1])--if(8>32)--False. So i++
temp=a[i]-temp=a[2]-temp=52
a[2]=a[3]-a[2]=32 i=1;1<=(2-2)---False
a[3]=temp-a[3]=52 and i++ after this the array becomes:
after this the array becomes: 0 1 2 3
0 1 2 3 8 32 34 52
8 34 32 52
recbubsort(a,n-1)recselsort(a,2-1)--recbubsort(a,1)
i=3;3<=(4-2)--False if(n=1)-(1=1)-True
return
recbubsort(a,n-1)recselsort(a,4-1)--recbubsort(a,3) after completion of sorting process, the final sorted array is as follows.
if(n=1)-(3=1)-False 0 1 2 3
i=0;0<=(3-2)---True 8 32 34 52
if(a[0]>a[0+1])--if(8>34)--False. So i++

[Link] 18
Efficiency of Bubble Sort: - Let array size = n
Number of Comparisons
Pass 1 → n − 1
Pass 2 → n − 2
Pass 3 → n − 3
...
Pass n−1 → 1

Ignoring constants and lower-order terms:

T(n)= Θ(n²)

The average and worst time complexity of bubble sort is Θ(n²)

Without optimization, best case is also Θ(n²). otherwise it is Θ(n)

Space Complexity: Extra variables used are i, j, temp. These require constant memory. No extra arrays are used.
So, space used is independent of n.

Bubble Sort is an in-place sorting algorithm.

Comparison between Bubble sort, Selection Sort and Insertion Sort

Feature Bubble sort Selection Sort Insertion Sort

Principle Swaps adjacent elements if they are in Selects the minimum element Inserts each element into its
wrong order and places it in correct position correct position in sorted portion
Best Case O(n) (optimized version) O(n²) O(n)
Time
Average Case O(n²) O(n²) O(n²)
Time
Worst Case O(n²) O(n²) O(n²)
Time
Number of O(n²) swaps O(n²) swaps O(n²) swaps
Swaps
Stability Stable Stable Stable
Adaptive yes (if optimized) No yes
Space O(1) O(1) O(1)
Complexity
Suitable For Small datasets When swaps must be minimized Nearly sorted arrays

[Link] 19