Algorithm Design Paradigm

Algorithm Design Paradigm

1. Divide and conquer

   • Divide and conquer algorithm is a design paradigm that recursivelly divides a problem into two or more subproblems related, until becomes simple and easy enouth to solve the solution and then combine it to become the solution to the original given problem. 1. Divide: Break the given problem into subproblems of same type. 2. Conquer: Recursively solve these subproblems 3. Combine: Appropriately combine the answers
   • Sorting Algorithms
     • Comparison Algorithm
       • A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.
       • Quick Sort
         • Quick sort is a O (n log(n)) sorting algorithm that recursivelly divides the array into small arrays sorting using a pivot as a reference where to the left are the smaller values compared to the pivot and to the right are the greater ones.
       • Merge Sort
         • Merge Sort is a recursive sorting algorithm and has as a worst, everage and best case complexity of O ( n log(n) ). It basically divides an array into 2 halves, it sorting the array. calls itself for the two halves and then merges the two sorted halves. Merge sort keeps on dividing the list into equal halves until it can no more be divided. By definition, if it is only one element in the list, it is sorted. Then, merge sort combines the smaller sorted lists keeping the new list sorted too.
         • Differences
           • Auxiliary Space : Mergesort uses extra space, quicksort requires little space and exhibits good cache locality. Quick sort is an in-place sorting algorithm. In-place sorting means no additional storage space is needed to perform sorting. Merge sort requires a temporary array to merge the sorted arrays and hence it is not in-place giving Quick sort the advantage of space.
           • Extra Space
             • Auxiliary Space : Mergesort uses extra space, quicksort requires little space and exhibits good cache locality. Quick sort is an in-place sorting algorithm. In-place sorting means no additional storage space is needed to perform sorting. Merge sort requires a temporary array to merge the sorted arrays and hence it is not in-place giving Quick sort the advantage of space.
           • Worst Cases
             • The worst case of quicksort is O(n^2), but it can be avoided by using randomized quicksort. It can be easily avoided with high probability by choosing the right pivot. Obtaining an average case behavior by choosing right pivot element makes it improvise the performance and becoming as efficient as Merge sort.
           • Locality of reference
             • Quicksort in particular exhibits good cache locality and this makes it faster than merge sort in many cases like in virtual memory environment.
           • Large Data Structure
             • Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage.

Images and files in the map