Sorting

Question 1

Sorting is the process…

Answer 1

Converting a list of elements into ascending order

Question 2

What is Selection Sort?

Answer 2

Sorting algorithm that treats the input as 2 parts.
A sorted part and an unsorted part

Question 3

What is Insertion Sort?

Answer 3

An algorithm that starts at the i = 1 element and skips over the 0th element

Question 4

What is a nearly sorted list?

Answer 4

A list that only contains a few elements not in sorted order

Question 5

What is the best case for insertion sort?

Answer 5

When the list is in ascending order

Question 6

What is the worst case for insertion sort?

Answer 6

When the list is in descending order

Question 7

What is QuickSort?

Answer 7

Repeatedly sorts the input into low and high partions and then recursively sorts those parts

Question 8

What is the pivot?

Answer 8

The pivot can be any value but it is commonly the middle of the array
numbers[midpoint val] = pivot

Question 9

What is the formula for the midpoint?

Answer 9

i + (k -i)/ 2
i is the value of the index

Question 10

If the midpoint is calculated and the number of the array is even, what is the number?

Answer 10

Round the number down and that is your midpoint. Example(3/2 = 1.5 round down to 1)

Question 11

The pivot of an even array would be…

Answer 11

The index of the midpoint calculated. Example(Midpoint = 1, index 1 is equal to whatever the number is)

Question 12

How many levels are required for a list of 1024 elements

Answer 12

N -1 = levels
1024 -1 = 1023

Question 13

How many total comparisons are required for a list of 1024 elements

Answer 13

(N-1)N
=(1024-1)1024=1047552

Question 14

What is merge sort?

Answer 14

Divides a list into 2 halves, recursively sorts each half and hen merges the sorted haves to produce a list

Question 15

How many variables are used to keep track of the elements?

Answer 15

3

Question 16

What is the base case for merge sort?

Answer 16

if (i < k)
j = (i + k)/2

Question 17

The Quick Sort Algorithm uses what method?

Answer 17

Divide and Conquer

Question 18

What is insertion sort?

Answer 18

Orders a sequence of values by repeatedly taking each value and inserting it in proper position

Question 19

When using insertion with stacks what 2 temp stacks must you have?

Answer 19

Sorted and Temp

Question 20

What does the sorted stack hold?

Answer 20

Will always be in order and have the smallest item on the top of the stack

Question 21

What will the temp stack hold?

Answer 21

Will hold the temp items that need to shifted out inorder to insert the new item in the proper place