Divide And Conquere

Question 1

What are the principles of Divide and Conquer

Answer 1

Divide − We divide the original problem into multiple sub-problems until they cannot be divided further.

Conquer − Then these subproblems are solved separately with the help of recursion

Combine − Once solved, all the subproblems are merged/combined together to form the final solution of the original problem.

Question 2

How does merge sort work?

Answer 2

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

https://www.geeksforgeeks.org/merge-sort/

Question 3

What is the complexity of Merge Sort?

Answer 3

+ On time O(N Log N)
+ + On Space O(N) as auxilarty array to sort the elements.

Question 4

How do you create a seudo code of these steps:

Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Answer 4

procedure mergesort( a[])
   if ( n == 1 ) return a

   al[] = a[0] ... a[n/2]
   ar[] = a[n/2+1] ... a[n]

   al = mergesort( al )
   ar = mergesort( ar )

   return merge( al, ar )
end procedure

Question 5

What is the steps of Quicksot Algorithm?

Answer 5

Creating a recursive Algorithm that:

Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively

Being Step 2 (Partition) the key of the algorith, finding the pivot.

Question 6

What is the complexity of QuickSort?

Answer 6

+ On time, Best case O(n log n) ; Worse Case O(n^2)
+ O(1) on space, the space required for swaping.

Question 7

What is the key steo of QuikSort algorith and how does it work?

Answer 7

The partion.

We start from the leftmost element and keep track of the index of smaller (or equal) elements as i. While traversing, if we find a smaller element, we swap the current element with arr[i]. Otherwise, we ignore the current element

https://www.geeksforgeeks.org/quick-sort/

Question 8

Ho

How Does Insertion Algotih work?

Answer 8

To sort an array of size N in ascending order iterate over the array and compare the current element (key) to its predecessor, if the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

This Algorithm is not considered into the Divided And Conquere category.

https://www.geeksforgeeks.org/insertion-sort/

Question 9

What is the complexity of Insertion Sort?

Answer 9

+ On Time: O(N^2) but O(N) in the best case, all the elements are sorted.
+ On space: O(1), it requieres 1 space for swaping.

Question 10

How Does Buble Sort work?

Answer 10

1.Traverse from left and compare adjacent elements and the higher one is placed at right side.
2. In this way, the largest element is moved to the rightmost end at first.
3. This process is then continued to find the second largest and place it and so on until the data is sorted.

This Algorithm is not considered into the Divided And Conquere category.

https://www.geeksforgeeks.org/bubble-sort/

Question 11

What is the complexity of Bubble Sort?

Answer 11

+ On Time: O(N^2)
+ On space: O(1), it requieres 1 space for swaping.

Question 12

How does selection sort work?

Answer 12

election sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.

This Algorithm is not considered into the Divided And Conquere category.

https://www.geeksforgeeks.org/sorting-algorithms/

Question 13

What is the complexity of Selection Sort?

Answer 13

+ On Time: O(N^2)
+ On Space: O(1), it requieres 1 space for swaping

Question 14

How does Heap Sort work?

Answer 14

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to the selection sort where we first find the minimum element and place the minimum element at the beginning. Repeat the same process for the remaining elements.

It is not considered an Divided And Conquere Algorith.

https://www.geeksforgeeks.org/heap-sort/

Question 15

What is the node that replace the top node in a Heap Tree and what happends in that moment?

Answer 15

In this case, is the last item of the array that represents the Heap.
One you replace the last node as the new root, you need to compare its children and swap the hieghst, repeate the comaration until it becames a leaf or there is no greatest children.

Question 16

How is the Heap’s array is arranged?

Answer 16

+ The array is base 1, where the index 1 is the root.
+ The children of a node is calculated as:
a. Left Idx = idx parent * 2
b. Right Idx = idx parent * 2 +1

Question 17

What is the complexity of Heap Sort?

Answer 17

+ On Time: O(N log N) each operation requieres its time.
+ On Space: O(1) besides the space of the array and the arrange is made over the same array.

Question 18

How does a Tree Sort work?

Answer 18

• Step 1: Take the elements input in an array.
• Step 2: Create a Binary search tree by inserting data items from the array into the binary search tree.
• Step 3: Perform in-order traversal on the tree to get the elements in sorted order.

Question 19

What is the complexity of Tree Sort?

Answer 19

On time: O(N Log N) as long as the tree is a Self-Balancing Tree
On Space: O(N) as an auxiliar space to allocate the Tree.

Question 20

Write a pseudocode for insertion sort

Answer 20

arr is an array base index = 0
```cpp
for i=1; i< arr.size(); i++
{
j=i
while(j>0 && arr[j]<arr[j-1])
{
swap(arr[j],arr[j-1])
j–
}
}
~~~

Time Complexity is O(n^2), Space Com O(1)

https://www.hackerrank.com/challenges/insertionsort2/problem

Question 21

Write a pseudocode for quicksort

Answer 21

```cpp
partition(a[], ibeg, iend) : int
midx = ibeg;
for i=ibeg+1; i < iend
swap(a[midx+1], a[i])
midx++
swap(a[midx], a[ibeg])
return midx

quicksort(a[], ibeg, iend)
if ibeg < iend
pivot = partition(a, ibeg, iend)
quicksort(a, ibeg, pivot)
quicksort(a, pivot+1, iend)

quicksort(a[])
quicksort(a, 0, len(a))
~~~

https://en.wikipedia.org/wiki/Quicksort