Lab Assignment 9

Homework:

1. Double-ended Simple Selection Sort

The basic operation of simple selection sort is to scan a list x1,….,xn to locate the smallest element and to position it at the beginning of the list. A variation of this approach is to locate both the smallest and the largest elements while scanning the list and to position them at the beginning and at the end of the list respectively. On the next scan, this process is repeated for the sublist x2,..,xn-1 and so on. This is double-ended simple selection sort.

2. Shell sort

Linear insertion sort performs best for small lists or partially sorted list. Shell sort is an insertion sort that uses linear insertion sort to sort small sublists to produce larger partially ordered sublists. Specifically one begins with a ‘gap’ of a certain size ‘g’ and then uses linear insertion to sort sublists of elements that are ‘g’ apart, first x[1],x[1+g],x[1+2g],…, then the sublist x[2],x[2+g],x[2+2g],.. then x[3],x[3+g],x[3+3g],.., so on. Next the size of ‘g’ is reduced and the process is repeated. This continues until the gap ‘g’ is 1 and the final linear insertion sort results in the sorted list.

3. Converting ‘expression’ into binary tree (take input of ‘expression’ as String)

For example, Convert (A – B) – C into binary tree where leaf is operand and non-leaf is operator.

Note: User can give any type of input and check validity also.

Class work: Take preparation of sorting techniques lectured in classes.