CSC 2200 Lecture Notes - Lecture 24: Shellsort, Sorting Algorithm, Insertion Sort

7 views3 pages
CSC 2200 lecture 24
Shell sort
•Shell sort is a highly efficient sorting algorithm and is based on
insertion sort algorithm.
•This algorithm avoids large shifts as in case of insertion sort, if the
smaller value is to the far right and has to be moved to the far left.
•This algorithm uses insertion sort on a widely spread elements, first
to sort them and then sorts the less widely spaced elements.
•This spacing is termed as interval
Shell sort
•This interval is calculated based on Knuth's formula as −
h = h * 3 + 1 where h is interval with initial value 1
•This algorithm is quite efficient for medium-sized data sets as its
average and worst case complexity are of Ο(n), where n is the number of items.
How Shell Sort Works?
•Let us consider the following example to have an idea of how shell
sort works.
•We
take the same array we have used in our previous examples.
•For our example and ease of understanding, we take the interval of 4.
•Make a virtual sub-list of all values located at the interval of 4positions.
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.