Higher Sort and Selection Algorithms

Question 1

QuickSort Idea

Answer 1

• divide and conquer
  
  • a three element list can be divided into left right and mid
  • we split the list into three element lists sorted around a pivot element
  • we merge all the three element lists

Question 2

Merge Sort Idea

Answer 2

• divide and conquer
  
  • take a pivot index
  • split the lists recursively until you end up with one element lists
  • then merge the results by comparing the elements
• the merge function does the comparison and composition

Question 3

QuickSort Sample Execution: [10,2,3,4,5,1]

Answer 3

QuickSort: [10,2,3,4,5,1]
Split: [10,2,3,4,5,1] => [2,3,1],[4],[10,5]
QuickSort: [2,3,1]
Split: [2,3,1] => [2,1],[3],[]
QuickSort: [2,1]
Split: [2,1] => [],[1],[2]
Merge: [],[1],[2] => [1,2]
Merge: [1,2],[3],[] => [1,2,3]
QuickSort: [10,5]
Split: [10,5] => [],[5],[10]
Merge: [],[5],[10] => [5,10]
Merge: [1,2,3],[4],[5,10] => [1,2,3,4,5,10]

Question 4

QuickSort Python Code

Answer 4

**def** **QuickSort**(list): **if** (len(list) \<= **1**): **return** list less, greater, equal = Partition2(list) less = QuickSort(less) greater = QuickSort(greater) result = less + equal + greater **return** result

Question 5

MergeSort Python Code

Answer 5

**def** **Merge**(list1, list2): i = **0** j = **0** result = [] **while**( i \< len(list1) **and** j \< len(list2)): **if** (list1[i] \<= list2[j]): result.append(list1[i]) i = i + **1****else**: result.append(list2[j]) j = j +**1****while** (i \< len(list1)): result.append(list1[i]) i = i + **1****while**(j \< len(list2)): result.append(list2[j]) j = j +**1****return** result **def** **MergeSort**(list): **if** (len(list) \<= **1**): **return** list; pivot = len(list) // **2** left = list[:pivot] right = list[pivot:] left = MergeSort(left) right = MergeSort(right) **return** Merge(left, right)

Question 6

Heap Indexing

Answer 6

• leftIndex: (i * 2) + 1 / (i * 2)
• rightIndex: (i * 2) + 2 / (i * 2) + 1
• lastParent: len(list) / 2 - 1 / len(list) / 2

Question 7

Heap Sort Idea

Answer 7

• We apply the tournament principle
• Two elements play against eachother
• We hipify each element by comparing it with the two child nodes starting from the last parent
• When we have hipified all nodes we have a MaxHeap which means that every parent is greater than it’s children
• We know that our first element is the greatest
• We iterate through the heap swap the first element with the last element and hipify in order to end up with a sorted list

Question 8

Heap Sort Hipify function Python Code

Answer 8

**def** **MaxHipify**(list,i): leftIndex = (i\***2**) + **1** rightIndex = (i\***2**) + **2** chosenIndex = i **if** (leftIndex \< len(list) **and** list[leftIndex] \> list[i]): Swap(list, leftIndex, i) chosenIndex = leftIndex **if** (rightIndex \< len(list) **and** list[rightIndex] \> list[i]): Swap(list, rightIndex, i) chosenIndex = rightIndex **if** (chosenIndex != i): MaxHipify(list, chosenIndex)

Question 9

Heap Sort Python Code

Answer 9

**def** **HeapSort**(list): lastParentIndex = (len(list) // **2**) - **1****while**(lastParentIndex \>=**0**): MaxHipify(list, lastParentIndex) lastParentIndex = lastParentIndex -**1**i = len(list) -**1**result = [] # as we have a max heap the first element is the greatest**while**i \>=**0**: result.insert(**0**, list[**0**]) # swap the first element with the last Swap(list,**0**, i) list = SubList(list, len(list) -**1**) # hipify in order to position greatest at top MaxHipify(list,**0**) i = i -**1****return** result

Question 10

QuickSelect Idea

Answer 10

• we resort to the idea of QuickSort by recursively partitioning around a pivot element until we have isolated the first k-Elements consisting of the left and the right part

Question 11

Quick Select Python Code

Answer 11

**def** **QuickSelect**(list, k): **if** (k \> len(list)): **return** None leftList, rightList = Partition(list) **if** (len(leftList) == k): **return** leftList[k-**1**] **else**: **if** (len(leftList) \< k): # less than k elements in the left list we have to search in the right list**return** QuickSelect(rightList, k - len(leftList)) **else**: **return** QuickSelect(leftList, k)

Question 12

Heap Select Python Code

Answer 12

**def** **BuildHeap**(list): index = (len(list) // **2**) - **1****while**(index \>=**0**): Heapify(list, index) index = index -**1****def** **HeapSelect**(list,k): **if** (k \> len(list)): **return** None BuildHeap(list) **for** index **in** range(**1**,k): Swap(list, **0**, len(list)-**1**) list = SubList(list, len(list)-**1**) Heapify(list, **0**) **return** list[**0**]

Question 13

Self-Organizing lists strategies

Answer 13

• MF-Strategy: Move to Front
  
  • Element is moved to the top immediatly after access
• T-Strategy
  
  • Element is moved one position to the front after it has been accessed
• FC-Strategy
  
  • Elements are sorted according to their frequency count

Question 14

Complexity Classes

Answer 14

• LOGSPACE - the class of all problems which have a logarithmic memory complexity
• P - the class of all problems which have a time complexity underlying polynomial function T(n) in {O(n) | n >= 2}
• NP - the class of all problems which don’t necessarily have a polynomial time complexity function but a polynominal time complexity function which would be required to verify the calculation
• PSPACE - the class of all problems which have a polynomial memory space function
• EXPTIME - the class of all problems which have an exponential time complexity function

Question 15

Was macht die Funktion Heapify or Durchsickern?

Answer 15

Wir haben einen Parent A und zwei Kinder B und C. Das Ziel ist es A an die Stelle des Maximums von B und C zu bekommen, falls A kleiner als B oder C.