Shell sort

Shell sort works by comparing elements that are distinct rather than adjacent elements in an array. It is an improvement over Insertion sort. The increment sequences in shell sort can be Shell's original sequence, Hibbard's increments, etc. The average performance of shell sort is thought to be O(n^(5/4)).

Summary

Things to Remember

Shell sort works by comparing elements that are distinct rather than adjacent elements in an array.
It is an improvement over Insertion sort.
The increment sequences in shell sort can be Shell's original sequence, Hibbard's increments, etc.
The average performance of shell sort is thought to be O(n^(5/4)).

MCQs

No MCQs found.

Subjective Questions

Q1:

Write a short note on Myocardial Infarction.

Type: Short Difficulty: Easy

Show/Hide Answer

Answer: <h4>Myocardial infarction</h4>
Definition
A heart attack usually occurs when a blood clot blocks the flow of blood through a coronary artery &mdash; a blood vessel that feeds blood to a part of the heart muscle. The interrupted blood flow that occurs during a heart attack can damage or destroy a part of the heart muscle.
A heart attack also called a myocardial infarction, can be fatal. Treatment for heart attack has improved dramatically over the years. It is crucial to promptly recognize symptoms and call 911 or emergency medical help if you think you might be having a heart attack.
 
<img src="https://d1vzuwdl7rxiz0.cloudfront.net/content/ehj/early/2012/08/23/eurheartj.ehs184/F2.large.jpg" alt="Image result for Myocardial Infarction" width="394" height="257" />
Causes
_ Vasospasm of coronary artery
_ Prinz mental's variant angina
_ Decreased oxygen supply
_ Acute blood loss anemia,low BP
_ Increased demand for oxygen
_ Rapid heart rate, thyrotoxicosis,ingestion of cocaine.
Risk factor
Non- modifiable - family history, increasing age, sex ( 3 times more in men )
Modifiable - high blood cholesterol level,smoking, tobacco,DM, HTN, obesity
Symptoms
Common heart attack symptoms include:
- A feeling of fullness, nausea, indigestion, heartburn
- Shortness of breath
- Sweating or a cold sweat
- Feelings of anxiety or an impending sense of doom
- Fatigue
- Trouble sleeping
- Lightheadedness or dizziness
Diagnosis
<ol>
<li>ECG</li>
<li>Troponin</li>
<li>Myoglobin</li>
<li>LHD</li>
<li>Increased CPK - MB</li>
<li>Leukocytosis appears on the second day after MI and disappears in 1 week.</li>
</ol>
Management
_ High flow oxygen.
_ IV access
_ IV analgesia and antiemetics
_ Serial ECG Monitoring
_ IV analgesia : 5-10 mg morphine with metoclopramide 10 mg.
_ Avoid intramuscular injection.
_ Thrombolytic therapy has been shown to improve survival rates in MI
_ Angiography provides essential knowledge of the extent of coronary disease
_ Anticoagulants : subcutaneous heparin 12500 units twice daily with an addition to oral aspirin.
Nursing intervention
<ol>
<li>Monitor ECG results to detect ischemia, injury new or extended infarction, arrhythmia and conduction defects.</li>
<li>Monitor, record vital signs and hemodynamic variable to monitor response to the therapy and detect complications.</li>
<li>Administer oxygen as prescribed to improve oxygen supply to the heart.</li>
<li>Obtain an ECG reading during acute pain to detect myocardial ischemia, injury or infarction.</li>
<li>Maintain the patient's prescribed diet to reduce fluid retention and cholesterol level.</li>
<li>Allay the patient's anxiety because the anxiety increases oxygen demand.</li>
</ol>
Complications
_ Left ventricular failure
_ Ventricular arrhythmia
_ Papillary miscle rupture
_ Pericarditis
_ Post MI angina
_ Ventricular aneurism

Videos

Myocardial Infarction

Shell sort

Shell Sort

Shell sort is also known as diminishing increment sort. It was invented by Donald Shell in 1959. Shell sort works by comparing elements that are distinct rather than adjacent elements in an array. It is the improvement on simple insertion sort. The distance between comparisons decreased as the sorting algorithm runs until the last phase in which adjacent elements are compared.

The basic approach is

Divide and conquer approach to insertion sort
- Sort many small sub arrays using insertion sort
- Sort progressively larger arrays
- Finally sort the entire array

These arrays are elements separated by a gap
- Start with large gap
- Decrease the gap on each pass

Increment Sequences in Shell Sort:

Shell's Original Sequence: n/2, n/4, . . . , 1 (repeatedly divide by 2)

Hibbard's Increments: 1, 3, 7, . . . , 2^K - 1; k = 1,2,...

Knuth's Increments: 1, 4, 13, . . ., (3^K - 1)/2 ; k = 1,2,3,. . .

Sedgewick's Increments: 1, 5, 19, 41, 109, . . ., 9 * 4^k - 9 * 2^k + 1

Algorithm: ShellSort(A,n)

Input: A, an array of size n

Output: Sorted A

loop1 gap = n/2 to gap > 0; gap = gap/2

loop2 p = gap to p < n ; p = p + 1

temp = A[p]

loop3 j = p to j >= gap && temp < A[j-gap]; j = j - gap

A[j] = A[j-gap]

Endloop3

A[j] = temp

Endloop2

Endloop1

Stop

Example: Sort 18 32 5 38 33 16 2

Steps: Shell's increment will be floor(n/2) = floor(8/2) = 4

Step 1: Only look at 18 and 38 and sort in order;

18 and 38 stay at their current position because they are in order

Step 2: Only look at 32 and 33 and sort in order;

32 and 33 stay at their current position because they are in order.

Step 3: Only look at 12 and 16 and sort in order;

12 and 16stay at their current position because they are in order.

Step 4: Only look at 5 and 2 and sort in order;

2 and 5 need to be switched to be in order.

Resulting numbers after increment 4 pass:

Step 1: Look at 18,12,38,16 and sort them in their appropriate location:

Step 2: Look at 32,2,33,5 and sort them in their appropriate location:

Resulting numbers after increment 2 pass:

floor1

The last increment of phase of Shell sort is basically an Insertion Sort Algorithm.

Analysis of Shell Sort:

Shell Sort's worst-case performance using Hibbard's increments is O(n^3/2)

The average performance is thought to be about O(n^5/4)

For mid-sized data : O(nlogn) sorts.

References

1. http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L12-ShellSort.htm

2.T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

Lesson

Sorting

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.