Essay --

DATA STRUCTURES AND ALGORITHM Topic: SHELL SORT Names: Maryum Waris Tahir Khan Isra Jameil Farrukh Ahsan Semester : III Section : A Submitted to : Sajid Saleem INTRODUCTION: Shell sort, also known as 'diminishing increment sort', was devised by Donald Shell in 1959.It is known to be one of the long-standing sorting algorithm. The basic logic of this sort is that it virtually divides the original list into smaller list, which consists of elements which are present at a specified gap, and performs sorting. As the gap decreases original list becomes more and more sorted ,finally when gap is reduced to one, comparison between adjacent elements of list occurs which finally sorts the list. Shell sort utilizes insertion sort. SHELL SORT: While sorting a list, insertion sort compares first two elements of list (we consider a list with array based implementation) and sorts them, such that first and second element of list are arranged in required order. After this initial step, third element is involved and is sorted according to the two elements previously sorted and so on. Short comings of insertion sort: While performing insertion sort if list is arranged in most unsorted manner(worst case) or list of to be sorted is lengthy, the process can be extremely time consuming as it involves the comparison and arrangement of every new element considered with other elements already sorted. Improvements with shell sort: If the list is comparatively sorted with slight disordering, it is easier to sort the list as it will require less swapping upon comparison of elements in the list Shell sort improves the sorting process because it compares and non adjoining elements which are far apart, and swaps th... ... and 10 while SPACE ≠¥ 1 3- Set J := SPACE + 1 [initialize counter J] 4- Repeat step 5 ,6 and 9 while J ≠¤ N 5- Set K := J - SPACE [initialize counter K] 6- Repeat step 7 and 8 while K ≠¥ 1 7- If ARRAY[K+SPACE] a- Interchange ARRAY[K+SPACE] and ARRAY[K] [end of if structure] 8- Set K := K-SPACE [decrements counter K ] [end of while loop in step 6] 9- Set J := J+1 [increments counter J ] [end of while loop in step 4] 10- Set SPACE := SPACE/2 [decrements counter SPACE] [end of while loop in step 2] 11- Return [takes control back to calling function]