Scribd
Upload
9 views3 pages

Selection and Insertion Sort Explained

The document outlines two sorting algorithms: Selection Sort and Insertion Sort, detailing their steps, advantages, and disadvantages. It also explains time complexity, categorizing algorithms into constant, linear, and quadratic time complexities, with a note that sorting algorithms like Bubble sort, Selection sort, and Insertion sort generally have a time complexity of n². The document emphasizes the simplicity and efficiency of both sorting methods for small lists while highlighting their inefficiencies for larger datasets.

Uploaded by

harshadajadhav462
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views3 pages

Selection and Insertion Sort Explained

The document outlines two sorting algorithms: Selection Sort and Insertion Sort, detailing their steps, advantages, and disadvantages. It also explains time complexity, categorizing algorithms into constant, linear, and quadratic time complexities, with a note that sorting algorithms like Bubble sort, Selection sort, and Insertion sort generally have a time complexity of n². The document emphasizes the simplicity and efficiency of both sorting methods for small lists while highlighting their inefficiencies for larger datasets.

Uploaded by

harshadajadhav462
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CHAPTER 5

SORTING

ALGORITHM: SELECTION SORT(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

Advantages
[Link] is simple and easy to understand
[Link] sorts the elements using minimal memory.
3. It makes fewer swaps compared to other algorithms
4. It is good for small list
[Link] is easy to implement.

Disadvantages
[Link] is inefficient for large database
[Link] if list is sorted, it makes still all comparisions.
[Link] is not stable ie it does not maintain the relative order of equal
element.
ALGORITHM: INSERTION SORT (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
Step 9 : SET i = i + 1

Advantages
[Link] is simple and easy to implement
[Link] method is efficient for small list
[Link] provides stable sort ie maintain the relative order of equal
element
[Link] constant extra memory.
[Link] is easy to understand

Disadvantages
[Link] for large database, especially when the list is unsorted
[Link] is slow for large data.
[Link] is not ideal for large data sets.
Time Complexity of Algorithms

Def: The amount of time an algorithm takes to process a given data is


called its time complexity. It includes
[Link] time algorithms
[Link] time algorithms
[Link] time algorithms

[Link] time algorithms


Any algorithm that does not have any loop will have time
complexity as one(1). Since the number of instructions to be executed
will be constant, irrespective of the data size. Such algorithms are
called as constant time algorithms.

[Link] 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 called as linear time
algorithms.

[Link] time algorithms


A loop within a loop (nested loop ) will have the time complexity
as [Link] algorithms are called as quadratic time algorithms.

Note: 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.
Therefore, according to the above rules, all sorting
algorithms namely Bubble sort, Selection sort and Insertion sort
have a time complexity of n2

**************************

You might also like