Insertion and Selection Sort
Selection sort finds the largest element in the array and exchanges it with the element in the last position. The same process is repeated for the second largest and the following elements until whole of the array is sorted. Selection sort is O(n^2). In Insertion sort, in each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place. Insertion sort is O(n^2).
Summary
Selection sort finds the largest element in the array and exchanges it with the element in the last position. The same process is repeated for the second largest and the following elements until whole of the array is sorted. Selection sort is O(n^2). In Insertion sort, in each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place. Insertion sort is O(n^2).
Things to Remember
- Selection sort finds the largest element in the array and exchanges it with the element in the last position.
- The same process is repeated for the second largest and the following elements until whole of the array is sorted.
- Selection sort is O(n^2).
- In Insertion sort, in each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place.
- Insertion sort is O(n^2)
MCQs
No MCQs found.
Subjective Questions
Q1:
Write a short note on Gentamicin.
Type: Short Difficulty: Easy
Show/Hide Answer
Answer: <p><strong>Gentamycin</strong></p>
<p>It was obtained from Micromonospora purpurea in 1964. It is effective against a large number of gram-negative bacilli and used for severe infection. Gentamycin injection for IM or IV route is a clear, colorless to slightly yellow solution.</p>
<p><strong> Mechanism of action</strong></p>
<p>Destroys gram-negative bacteria by irreversibly binding to 30S subunit of bacterial ribosomes and blocking protein synthesis, resulting in misreading of genetic code and separation of ribosomes from messenger RNA</p>
<p> <strong>Preparation</strong></p>
<p>Cream: 0.1%</p>
<p>Injection: 10 mg/ml (pediatric), 40 mg/ml (adult)</p>
<p>I.V. infusion (premixed in normal saline solution): 40 mg, 60 mg, 70 mg, 80 mg, 90 mg, 100 mg, 120 mg</p>
<p>Ointment: 0.1%</p>
<p> <strong>Indications</strong></p>
<ul>
<li>Serious infections caused by Pseudomonas aeruginosa, Escherichia coli, and Proteus, Klebsiella, Serratia, Enterobacter, Citrobacter, or Staphylococcus species</li>
<li> Endocarditis prophylaxis before surgery</li>
<li> External ocular infections caused by susceptible organisms</li>
</ul>
<p> <strong>Dose</strong></p>
<p>Adults: 3 mg/kg/day in three divided doses I.M. or I.V. infusion q 8 hours. For life-threatening infections, up to 5 mg/kg/day in three to four divided doses; reduce to 3 mg/kg/day as indicated.</p>
<p>Children: 2 to 2.5 mg/kg q 8 hours I.M. or I.V. infusion</p>
<p>Infants older than 1 week: 2.5 mg/kg q 8 hours I.M. or I.V. infusion</p>
<p>Neonates younger than 1 week, preterm infants: 2.5 mg/kg q 12 hours I.M. or I.V.</p>
<p> <strong>Contraindications</strong></p>
<ul>
<li>Hypersensitivity to drug or other aminoglycosides</li>
</ul>
<p><strong> Adverse reactions</strong></p>
<p>CNS: dizziness, vertigo, tremors, numbness, depression, confusion, lethargy, headache</p>
<p>EENT: visual disturbances, dry eyes, nystagmus</p>
<p>GI: nausea, vomiting, stomatitis, increased salivation, splenomegaly, anorexia</p>
<p>GU: increased urinary casts, polyuria, dysuria, erectile dysfunction</p>
<p>Respiratory: apnea</p>
<p>Skin: exfoliative dermatitis, rash, pruritus, urticaria, purpura, alopecia</p>
<p><strong> General implications</strong></p>
<ul>
<li>Watch for signs and symptoms of hypersensitivity reactions (nephrotoxicity or ototoxicity).</li>
</ul>
<ul>
<li>Assess fluid intake and output, urine specific gravity, and urinalysis for signs of nephrotoxicity.</li>
<li>Monitor CBC, BUN, creatinine level, and creatinine clearance.</li>
<li>Weigh patient regularly.</li>
<li>Assess for signs and symptoms of ototoxicity (hearing loss, tinnitus, ataxia, and vertigo).</li>
<li>Advise patient to report signs and symptoms of ototoxicity (hearing loss, ringing in ears, vertigo).</li>
</ul>
<p> </p>
<p>It was obtained from Micromonospora purpurea in 1964. It is effective against a large number of gram-negative bacilli and used for severe infection. Gentamycin injection for IM or IV route is a clear, colorless to slightly yellow solution.</p>
<p><strong> Mechanism of action</strong></p>
<p>Destroys gram-negative bacteria by irreversibly binding to 30S subunit of bacterial ribosomes and blocking protein synthesis, resulting in misreading of genetic code and separation of ribosomes from messenger RNA</p>
<p> <strong>Preparation</strong></p>
<p>Cream: 0.1%</p>
<p>Injection: 10 mg/ml (pediatric), 40 mg/ml (adult)</p>
<p>I.V. infusion (premixed in normal saline solution): 40 mg, 60 mg, 70 mg, 80 mg, 90 mg, 100 mg, 120 mg</p>
<p>Ointment: 0.1%</p>
<p> <strong>Indications</strong></p>
<ul>
<li>Serious infections caused by Pseudomonas aeruginosa, Escherichia coli, and Proteus, Klebsiella, Serratia, Enterobacter, Citrobacter, or Staphylococcus species</li>
<li> Endocarditis prophylaxis before surgery</li>
<li> External ocular infections caused by susceptible organisms</li>
</ul>
<p> <strong>Dose</strong></p>
<p>Adults: 3 mg/kg/day in three divided doses I.M. or I.V. infusion q 8 hours. For life-threatening infections, up to 5 mg/kg/day in three to four divided doses; reduce to 3 mg/kg/day as indicated.</p>
<p>Children: 2 to 2.5 mg/kg q 8 hours I.M. or I.V. infusion</p>
<p>Infants older than 1 week: 2.5 mg/kg q 8 hours I.M. or I.V. infusion</p>
<p>Neonates younger than 1 week, preterm infants: 2.5 mg/kg q 12 hours I.M. or I.V.</p>
<p> <strong>Contraindications</strong></p>
<ul>
<li>Hypersensitivity to drug or other aminoglycosides</li>
</ul>
<p><strong> Adverse reactions</strong></p>
<p>CNS: dizziness, vertigo, tremors, numbness, depression, confusion, lethargy, headache</p>
<p>EENT: visual disturbances, dry eyes, nystagmus</p>
<p>GI: nausea, vomiting, stomatitis, increased salivation, splenomegaly, anorexia</p>
<p>GU: increased urinary casts, polyuria, dysuria, erectile dysfunction</p>
<p>Respiratory: apnea</p>
<p>Skin: exfoliative dermatitis, rash, pruritus, urticaria, purpura, alopecia</p>
<p><strong> General implications</strong></p>
<ul>
<li>Watch for signs and symptoms of hypersensitivity reactions (nephrotoxicity or ototoxicity).</li>
</ul>
<ul>
<li>Assess fluid intake and output, urine specific gravity, and urinalysis for signs of nephrotoxicity.</li>
<li>Monitor CBC, BUN, creatinine level, and creatinine clearance.</li>
<li>Weigh patient regularly.</li>
<li>Assess for signs and symptoms of ototoxicity (hearing loss, tinnitus, ataxia, and vertigo).</li>
<li>Advise patient to report signs and symptoms of ototoxicity (hearing loss, ringing in ears, vertigo).</li>
</ul>
<p> </p>
Videos
Gentamicin
Insertion and Selection Sort
Selection Sort
Basic Idea:
- Find the largest element in the array
- Exchange it with the element in the last position
- Find the second largest element and exchange it with the element in the second last position
- Continue until the array is sorted
- After each selection and swapping, the number of sorted elements is increased and that of unsorted ones decreases.
Algorithm: Selection-Sort(A,n)
loop1 i = n-1 to i>0; i=i-1
MAX = A[0]
index = i
loop2 j=1 to j <= i ; j = j+1
if A[j] > Max
Max = A[j]
index = j
Endif
Endloop2
A[index] = A[i]
A[i] = Max
Endloop1
Example:
| 35 | 65 | 30 | 60 | 20 | scan 0-4, largest=65, swap 65 and 20 |
| 35 | 20 | 30 | 60 | 65 | scan 0-3, largest 60, swap not needed |
| 35 | 20 | 30 | 60 | 65 | scan 0-2, largest 35, swap 35 and 30 |
| 30 | 20 | 35 | 60 | 65 | scan 0-1, largest 30, swap 30 and 20 |
| 20 | 30 | 35 | 60 | 65 | done |
Analysis of Selection Sort
- The inner for loop executes the size of the unsorted part minus 1 (from 1 to n-1), and in each iteration, we make one key comparison.
- Number of key comparisons = 1 + 2 + . . . + n-1 = n*(n-1)/2
- So, Selection sort is O(n2)
- The best case, the worst case, and the average case of the selection sort algorithm are same. All of them are O(n2)
- This means that the behavior of the selection sort algorithm does not depend on the initial organization of data.
- Since O(n2) grows so rapidly, the selection sort algorithm is appropriate only for small n.
- Although the selection sort algorithm requires O(n2) key comparisons, it only requires O(n2) key comparisons, it only requires O(n) moves.
- A selection sort could be a good choice if data moves are costly but key comparisons are not costly (short keys, long records).
Insertion Sort
Basic Idea:
- Insertion sort is a simple sorting algorithm that is appropriate for small items.
- Most common sorting technique used by card players.
- Start with an empty left hand and the cards facing down on the table.
- Remove one card at a time from the table, compare it with each of the cards already in the hand, from right to left, and insert it into the correct position in the left hand.
- The list is divided into two parts: sorted and unsorted.
- In each pass, the first element of the unsorted part is picked up, transferred to the sorted sublist, and inserted at the appropriate place.
Algorithm: Insertion-Sort(A,n)
for j = 2 to A.length
key = A[j]
// Insert A[j] into the sorted sequenece A[1 . . j-1]
i = j - 1
while i>0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
Example:
| 5 | 2 | 4 | 6 | 1 | 3 | key = 2 |
| 2 | 5 | 4 | 6 | 1 | 3 | key = 4 |
| 2 | 4 | 5 | 6 | 1 | 3 | key = 6 |
| 2 | 4 | 5 | 6 | 1 | 3 | key = 1 |
| 1 | 2 | 4 | 5 | 6 | 3 | key = 3 |
| 1 | 2 | 3 | 4 | 5 | 6 | Sorted |
Insertion Sort - Analysis
- Running time depends on not only the size of the array but also the contents of the array.
- Best-case: O(n)
- Array is already sorted in ascending order
- Inner llop will not be executed
- The number of moves = 2*(n-1) = O(n)
- The number of key comparisons: (n-1) = O(n)
- Worst-case: O(n2)
- Array is in reverse order
- Inner loop is executed i-1 times, for i = 2,3,. . . , n
- Number of moves: 2*(n-1)+(1+2+3+. . .+n-1) = n*(n-1)/2 = O(n2)
- Average-case: O(n2)
- We have to look at all the possible initial data organizations.
- So, Insertion Sort is O(n2)
References:
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”
- G. Brassard and P. Bratley, “Fundamentals of Algorithms”
- R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”
Lesson
Sorting
Subject
Computer Engineering
Grade
Engineering
Recent Notes
No recent notes.
Related Notes
No related notes.