Summary of CS 3345 Ch 7 Part 4

00:00:00 - 00:20:00

The video explains how to perform a shell sort on an array of integers. The algorithm uses an increment sequence and an insertion sort to produce a sorted array. In the worst case, the shell sort will compare every element in an array with every other element, until it reaches the end of the array.

• 00:00:00 The Shell Sort algorithm sorts an array of objects by comparing their distance and swapping the appropriate elements. The algorithm uses an increment sequence and an insertion sort to produce a sorted array.
• 00:05:00 The video demonstrates how to perform an injection sort on an array of integers. The first subarray is sorted, and the second and third subarrays are sorted in reverse order. The fourth and fifth subarrays are sorted using the insertion sort algorithm, and the sixth and seventh subarrays are sorted using the shell sort algorithm. The increment sequence for the shell sort is 5, 3, 1. The final array is 12, 15, 17, 28, 31, 41, 43, 45, 51, 58, 61, 71, 81, 94.
• 00:10:00 The shell algorithm for sorting an array of nine elements propose an increment sequence of 1, 2, 3, 4, 5, 6, 7, 8, 9. The algorithm is implemented in code, and four sorted files are created. Two sorted files are created by comparing elements at index 2 and index 0, and three sorted files are created by comparing elements at index 3, index 1, and index 2. The smallest element is placed in index 0 and the largest element is placed in index 8.
• 00:15:00 This video explains how to analyze the worst case for the shell sort. In the worst case, the shell sort will compare every element in an array with every other element, until it reaches the end of the array. For each element, it will move the smallest number up one position, and the largest number down one position.
• 00:20:00 The algorithm discussed in this video is Heapsort, which is a sorting algorithm that is based on a lower bound and an extra credit quiz. The lower bound for the algorithm is given by the equation zero, and the upper bound is not known.