Sorting Algorithms

Some Terms
  • In-place Sorting => use constant space to sort (modify only the given array)
  • Stable sorting - When two same values appear in the same relative order in sorted data as in the original array => Eg: Merge Sort, Insertion Sort, Bubble Sort
    ₪ When equal elements are indistinguishable like integers => stability is not an issue.
              →  ----> If stable sorting is used => get shown pic
    ₪ If we sort section-wise & sorting algorithm is unstable => may get random ordering
    ₪ Any given sorting algorithm which is unstable can be modified to be stable
        Augment index along with value → If values are same     → use index as tiebreaker
    → Drawback - extra O(N) space to store index for N element + need extra comparison

  • Counting sort is unstable but can be made stable -
    • 1 6a 8 3 6b 0 6c 4 ---> a, b, c is used just to distinguish ordering of same value
      Stable Algo - 0 1 3 4 6a 6b 6c 8
    • count array - [1, 1, 0, 1, 1, 0, 3, 0, 1]  bcz 6 appears thrice and rest appears once
      • this 3 doesn't clarify that whether 6a is first or 6c → Unstable sort
    • prefix sum - [1, 2, 2, 3, 4, 4, 7, 7, 8] => Logic - pre[i] is the cumulative sum from left => shows how many smaller items are before it => tells the position
      • if go left to right --> tells that 0 should be at 1st position (bcz pre[0]=1)
        4 should be at 4th position (bcz pre[4]=4) and 6 at 7th position
      • pre[6] gives the last occurrence of 6 --> 6c should be kept at 7th position
      • Conclusion - (for stable counting sort)
        count array → prefix sum → iterate original array from backwards
        → place value at pre[value] and ↓ pre[value] by 1
    • NOTE - If take prefix sum from end → [8, 7, 6, 6, 5, 4, 4, 1, 1] → used for sorting in decreasing order → bcz now 1st value, i.e., 1 is put at last position
Non-comparison based Algorithm
  1. Counting sort - Create array of size = Max Element → access using arr[value] in O(1)
    • DEMERITS - space wastage, can't use if max_element is large or values are float

  2. Bucket sort - chutiya algorithm
    • First create 10 buckets => then make array of linked list by adding 10*arr[i] to that bucket => apply insertion sort (or any stable sorting algo) in each bucket

    • Generally, used for values between [0, 1] => decimal numbers 
      • If values are uniformly distributed => best case - O(n) => bcz extra insertion sort use nhi krna pda bcz each bucket has exactly 1 element 
      • Else O(n²) bcz extra sorting needed for each bucket
    • Eg. - [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
  3. Radix sort - similar to bucket sort but apply d times where d = no. of digits
    • Let's the array be [170, 45, 75, 90, 802, 24, 2, 66]
    • Find largest element => 802 which has 3 digits => iterate 3 times
    • If we don't use stable sorting algorithm → radix sort fails
      • [3, 2, 22, 52] → [52, 2, 32, 3] {assume unstable sort + start from unit place}
        → [03, 02, 32, 52] as unstable         algo → 03 may come before 02
      • Logic - at tens place, if value same → pick small unit place (it comes before in array) → bcz array already sorted wrt unit place
    • Use stable counting sort bcz access is in O(1) to sort digits at each place value
    • sorted array based on unit place - [170, 90, 802, 2, 24, 45, 75, 66]
      sorted array based on tens place - [802, 2, 24, 45, 66, 170, 75, 90]
      sorted array based on hundreds place - [2, 24, 45, 66, 75, 90, 170, 802]
      • NOTE - starting from hundreds place may work but very complex → skip

    • time complexity - O(d * (n + b)) and space complexity - O(n + b)
      where d = no. of digits           n = no. of elements
      b = base of the number system --> here 10 bcz decimal numbers
    • space complexity => create buckets for each digit in O(b) and copy elements back to original array from sorted array of size O(n)
    • If elements are in the range 1 to n² --> Sort in linear time => Use radix sort 
      • counting sort will take O(n²) bcz max. value = n²
      • If log₂ (n) bits for every digit => Radix better than Quick Sort for a wide range of input numbers.
        Radix sort uses counting sort as a subroutine => takes extra space to sort

Comparison based Algorithm
  1. BST (binary search tree) sort -
    • First insert n elements to BST → once BST constructed → print inorder traversal
    • Best case - O(n logn) --> Adding each item to a BST on average takes O(log n) 
    • Worst case - O(n²) --> bcz inserting takes O(h) time
      • can improve by using self-balancing BST like Red Black Tree, AVL Tree

  2. Selection sort - place element at its correct position -> minimum at 1st position
    • 4 1 3 9 7 --> select minimum which is 1 and swap with first position --> 1 4 3 9 7
    • Benefit - makes the minimum number of swaps during sorting
      ₪ Use only if array is small bcz O(n²) even in best case

  3. Bubble sort - keep swapping adjacent element if arr[i] > arr[i+1]
    • 4 1 3 9 7 --> take maximum till last --> 4 1 3 7 9 
      • swapping adjacent elements => looks like bubble
      • Best case - O(n) bcz if array is sorted --> no swapping => inner loop break
    • Benefit - fastest on small array or nearly sorted data => bcz once sorted --> no swap made ==> stop the algorithm
      NOTE - selection sort mai aisa nhi kr skte bcz usme find min. at every time and swap once but yahan hr moment pe swap kr rhe taaki bada bnte chla jaaye

  4. Insertion sort - where will new element goes in already sorted array
    • 1 5 7 9 2 --> swap 2 until 2 reaches its correct position
    • Benefit - same as bubble sort

  5. Merge sort - divide array into 2 till 1 element left (which is sorted) -> O(log n)
    • then merge two sorted arrays using extra array to store the sorted result 
      • O(n) time and O(n) space --> Total = O(n*log n) time
    • Benefit - when data structure doesn’t support random access or random access is expensive => use merge sort bcz no random value needed
      ₪ Fast for linked list as to access data at any index => traverse from the head to that index and merge sort accesses data sequentially

  6. Quick sort - assume pivot and divide array into 2 parts -> left has smaller elements and right has greater elements --> do recursively for left & right part
    • pivot can be first element / last element / any random element
    • O(1) space and O(n*log n) time
      • O(n²) time if every time left or right part is empty --> like sorted array

  7. Heap sort - First convert array into max heap using heapify, then highest element is removed (i.e., root element) and remaining are used to create a new max heap. 
    • O(1) space and O(n*log n) time

Comments

Post a Comment

Popular posts from this blog

Templates (for CP)

Next smaller element in left and right side of any element -  Link     (Can easily modify) Next greater element for both sides in one pass -  Link String Hashing -  Link MUST call precalc() inside function Count inversions in any random array (GENERAL)  -  Link Count inversions in binary string -  Link Sum of XOR of all subarrays -  Link  ——₪——  Original question link Sum of XOR of all subsequence -   Link  ——₪——  Original question link Prefix sum of 2-D array -  Link Number of subarrays with sum = k →  Link Number of subarrays with sum divisible by k  →  Link Segment Trees →  Link djikstera algorithm -  Link Prime Factorization of given number n →  Link Count no. of divisors in  O(N ⅓ )  →  Link
Read more

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...
Read more