WGU C949 Exam with complete solutions

binary search - Answer- first checks the middle element of the list. If the search key is found, the algorithm returns the matching location. If the search key is not found, the algorithm repeats the search on the remaining left sublist (if the search key was less than the middle element) or the remaining right sublist (if the search key was greater than the middle element) linear search - Answer- may require searching all list elements selection sort - Answer- sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly selects the proper next value to move from the unsorted part to the end of the sorted part. selection sort - Answer- f(numbers, numbersSize) { i = 0 j = 0 indexSmallest = 0 temp = 0 for (i = 0; i < numbersSize - 1; ++i) { indexSmallest = i for (j = i + 1; j < numbersSize; ++j) { if ( numbers[j] < numbers[indexSmallest] ) { indexSmallest = j } } // Swap numbers[i] and numbers[indexSmallest] temp = numbers[i] numbers[i] = numbers[indexSmallest] numbers[indexSmallest] = temp } } insertion sort - Answer- sorting algorithm that treats the input as two parts, a sorted part and an unsorted part, and repeatedly inserts the next value from the unsorted part into the correct location in the sorted part. insertion sort - Answer- f(numbers, numbersSize) { i = 0 j = 0 temp = 0 // Temporary variable for swap for (i = 1; i < numbersSize; ++i) { j = i // Insert numbers[i] into sorted part // stopping once numbers[i] in correct position while (j > 0 && numbers[j] < numbers[j - 1]) { // Swap numbers[j] and numbers[j - 1] temp = numbers[j] numbers[j] = numbers[j - 1] numbers[j - 1] = temp --j } } } shell sort - Answer- sorting algorithm that treats the input as a collection of interleaved lists, and sorts each list individually with a variant of the insertion sort algorithm. shell sort - Answer- Uses gap values to determine the number of interleaved lists shell sort - Answer- def g(numbers, start_index, gap): for i in range(start_index + gap, len(numbers), gap): j = i while (j - gap >= start_index) and (numbers[j] < numbers[j - gap]): temp = numbers[j] numbers[j] = numbers[j - gap] numbers[j - gap] = temp j = j - gap def f(numbers, gap_values): for gap_value in gap_values: