Sorting Flashcards
Sorting is the process…
Converting a list of elements into ascending order
What is Selection Sort?
Sorting algorithm that treats the input as 2 parts.
A sorted part and an unsorted part
What is Insertion Sort?
An algorithm that starts at the i = 1 element and skips over the 0th element
What is a nearly sorted list?
A list that only contains a few elements not in sorted order
What is the best case for insertion sort?
When the list is in ascending order
What is the worst case for insertion sort?
When the list is in descending order
What is QuickSort?
Repeatedly sorts the input into low and high partions and then recursively sorts those parts
What is the pivot?
The pivot can be any value but it is commonly the middle of the array
numbers[midpoint val] = pivot
What is the formula for the midpoint?
i + (k -i)/ 2
i is the value of the index
If the midpoint is calculated and the number of the array is even, what is the number?
Round the number down and that is your midpoint. Example(3/2 = 1.5 round down to 1)
The pivot of an even array would be…
The index of the midpoint calculated. Example(Midpoint = 1, index 1 is equal to whatever the number is)
How many levels are required for a list of 1024 elements
N -1 = levels
1024 -1 = 1023
How many total comparisons are required for a list of 1024 elements
(N-1)N
=(1024-1)1024=1047552
What is merge sort?
Divides a list into 2 halves, recursively sorts each half and hen merges the sorted haves to produce a list
How many variables are used to keep track of the elements?
3
What is the base case for merge sort?
if (i < k)
j = (i + k)/2
The Quick Sort Algorithm uses what method?
Divide and Conquer
What is insertion sort?
Orders a sequence of values by repeatedly taking each value and inserting it in proper position
When using insertion with stacks what 2 temp stacks must you have?
Sorted and Temp
What does the sorted stack hold?
Will always be in order and have the smallest item on the top of the stack
What will the temp stack hold?
Will hold the temp items that need to shifted out inorder to insert the new item in the proper place
