Complete DSA Notes - Part 4 @curious_ programmer Array © ae ee Queue Linked List Sirs Tree acisisers Front Linked ListChapter 1: Introduction to DSA @ curious _ programmer What is Data Structure ? A data structure is a way to store and organize data in a computer so that it can be used efficiently. Different data structures are designed for different kinds of data operations +o make data processing more effective. ise 7 -@: GEEDEG) El >SBEB}> Array Stack = Queue Stack What is Algorithm? An algorithm is a finite sequence of well-defined steps 4o solve a specific problem. Tt is like a recipe that defines the exact steps. in a particular order. Cad we A step-bystep procedure to solve a problem Step 1 | ——~> Condition?>> Yes Properties of Algorithms v [Link] : Must terminate after a finite number of steps v 2 Definiteness: Steps must be precisely defined and unambiguous v [Link] Output: Take zero or more inputs, produce at least one outputWhy DSA is important? @ curious_ programmer v Efficient Problem Solving: DSA provides tools 4o solve problems efficiently by choosing the right data structure and algorithm. v Optimal Resource Usage: Helps use memory and time effectively by ensuring minimal resource consumption v Coding Interviews & Competitions: Crucial for coding interviews and programming contests as knowledge of DSA is essential for tackling challenging problems ‘Types of Data Structures v Linear : Linear data structures organize data ina sequential manner where each element is adjacent 4o the previous one Seeger sees Array Queue v Non-Linear: Non-linear data structures organize data hierarchically, connecting elements in.a more complex, branching manner. Binary Tree v Abstract Data Types (ADT) ADTs are. defined by their operations, not by their implementation . Examples include:Time & Space Complexity @ curious programmer v Why complexity analysis? v Evaluate Efficiency: Complexity analysis helps in measuring an algorithms efficiency by evaluating its running Hime. (Time Complexity) and memory usage (Space Complexity). v Compare Algorithms: Helps in comparing different algorithms to choose the most optimal one for a given problem v Scalability: Ensures that our algorithm can bandle large inputs efficiently without degrading performance Best, Average & Worst Case Algorithms are evaluated based on their performance in different scenarios: >— O(n) Target = 1 —— Minimum time WMibesiGase j2i2[3l4isle[7 Zp * 2AX1n) eraigetet Minimum time. v Average Case ——— Isle [117 lef2 ———- a(n) Target = © Expected time v Worst Case gia elec) > * OC") Target = 13 Maximum imeBig-O, Big-Q, Big-O @ curious_ programmer v Why complexity analysis? $ Big-O | v Upper Bound Fin) < O(gin) 4 Big-Q | v Lower Bound F(n) = Q(g(n) t Big-© | v Tight Bound F(n) = O(g(n) These notations provide a measure of the time complexity of an algorithm in relation to the input size. Space Complexity vWhat is Space Complexity? Space Complexity measures the amount of memory an algorithm uses during its execution. —— Input Size ~ att SS oe ie DS SSS ear == A ~» output Space These notations provide a measure of the time. complexih of an algorithm in relation to the input size Space Complexity V What is Space Complexity? Space Complexity: measures the amount of memory an algorithm uses during its execution. ©@& Input Size: Memory needed to store the inputs ©& Aux. Space: (Awe) Space: Extra memory needed apart Output Space: Memory used to store the output data.Complexity of Common Loops & Recursion @ curious programmer vy Complexity of Loops: v Linear Loop: for « =S6in) v Nested Loop: : for (int i= 0; i O(n?) Ge } ¥ Logarithmic Loop: = Complexity of Recursion Algorithms are evaluated based on their performance. in different scenarios v Linear Recursion =) ae void recurse(int n) - O(n) if (VSO) return; @) @) recurse(n -1); ee Oa © Vv Binary (Exponential) Recursion = Void recurse(int n) | a oO) if (VQ =O) return; recurse(n -1); G1) (2) + 2 QO OO ©Chapter 2: Arrays @ curious__ programmer 2.1 Intrroduction to Arrays y An array is a collection of elements of the same data type, stored in contiguous memory locations. It is a data structure that stores elements in a sequential manner Array i Ss baie O° al 2 Ss 3) 4 Index v Characteristics of Arrays The size of an array is defined at the time of declaration and does not change. us Elements:] All elements in an array are of the same data type v Contiguous (Sequential) Memory Locations:) Elements are stored in adjacent memory locations, allowing constant time access Properties of Arrays v Constant Time Access —> O(1): Direct access to any element using its index v Easy Traversal: Simple to loop through all the elements using a for loop. v Effective Data Storage: Useful for storing multiple values of the same type. Homo:2.2 1D Arrays @curious_programmer 2.2 1D Arrays v A 1D array (or one-dimensional array) is a linear data structure that stores a collection of elements of the same data type in a single, contiguous block of memory ¥ Each element in a 1D array is accessed using an index, which represents the element's position a arr[2] = 24 4218] 24!/51/17|30 (Accessed element) OB elias) Se |e alee: Index - > v Declaration & Initialization int arr[5]; Declares an integer array of size 5 without initializing elements. int arr[5] = £3, 7, 1,9, 5}; declares an integer array of size 5 and initializes it with the values Delgo. Memory Representation vy The integer array is stored in a contiguous block of memory, Each element takes 4 bytes of memory (assuming 4 bytes for int) Addi — eu Contiguous Memory Locations (= (3 eee 5 lie my Eo od Be ss 4 Bytes >2.2 2D Arrays @ curious__programmer 2.2 2D Arrays Vv A 2D array (or two-dimensional array) is a collection of elements arranged in rows and columns, forming a matrix- like structure. v It allows storing data in a tabular format, with elements accessible using a pair of indices (row index and column index). a pt sl a Gontens) matrix[2]I] = 10 OM miso ES * (Accessed element Row [Ol [ail 2] 3) 4 Index | O 2 ont 8 |— @Row Index O | D9 4} 10]| 11 | 12 |— @Column Index Row Index v Declaration & Tnitialization int matrix[3][4]; Declares a 3x4 integer array without initializing elements. (Example: ) int matrix(3][4] = (1, 2, 3, 43, Poeo nos {oO 1Ondd, Lets Declares a 3x4 integer array initialized with the given values. Memory Representation v The 2D array is stored in row-major order, where rows are stored in contiguous memory locations. -~Memory Address ————> Row-Major Order 5 1 BS See 10s a eres 204 2s — > | 224 Memory Address2.4 Array Operations @curious_programmer 2.4.1 Insertion Insertion in 1D Arrays VY Array insertion involves adding a new element to a specific position within an array v This shifts the subsequent elements one position to the right to make space for the new element Step 1: Find the position to insert at [Tpsert 25 at index 2 | r 2 ae Z ; I ¥ \ arr:[ 5 | 10 | 30 | 40 | 50 |>[_50 | Opes ss 4 Position 2 Step 2: Shift elements to the right he eS 5 10 | 30 EO ee arr: Step 3: Insert the new element at the found position 25 )|[5 [10 [25| 30[40] 50] 50 | os ie eee! Properties of Insertion vy Time Complexity > O(n): In the worst case, all elements. may need to be shifted, making it linear time v Insertion at the end: O(1) if there's space , as no shifting needed v Full Array: Insertion is not possible when the array is Full and has no space for more elements2.4 Array Operations @curious_programmer 24.2 Deletion Deletion in 1D Arrays v Array deletion involves removing an existing element from a specific position within an array y To fill the gap, the subsequent elements are shifted one position to the left Step 1: Find the position to insert at Delete element at 3 index 2 y vy aes arr: [5 | 15 | 30 | 30 | 40 |—>[ 50 | fis leitsae 2 2|S a Position 2 Step 2: Shift elements to the left ¥ + + : aap 3 arr: [Sn [5.[pso.] 30 ao.p4o a pe eer 4 = Step 3: Fill the last position with a default value optional) 25 [So] 15 bee] 46 ese) Tivo |} o 1s les lei en ee as default value Properties of Deletion v Time Complexity > O(n): In the worst case, all elernents after the deleted position must be shifted wv Deletion from the end: O(1) if no default value is needed, as no shifting is required v Multiple Deletions: Multiple deletions may cause fragmentation, leaving empty slots in the array2.5 Problems on Arrays @ curious_programmer 2.4.2 Deletion Deletion in 1D Arrays v Array deletion involves removing an existing element from a specific position within an array, Y To fill the gap, the subsequent elements are shifted one position to the left. Step 1: Find the position to delete at [Delete clement at e ys | Se) — 5 | 15 [30 [30 [40] Pa oe a | Position 2 iotietas! Step 2: Shift elements to the left [s[2[e[e][3s [4 |4o|> Oz telie? sel sebae| 5 Step 3: Merge Two Sorted Arrays 5 [as [s0[40|[40[40[4oTo ]) | oO eps aisles [PRS Ss 25S [is [3040/9 [iJ[i2) vo as defoult value ips for Solving Array Problems ¥ Plan your approach before coding to understand the problem dearly Y Consider edge cases, like an empty array or arrays with very large or very small values. v Multiple Deletions: Multiple deletions may cause fragmentation, leaving empty slots in the arrayChapter 3: Linked List @ curious_programmer v 3.4 Introduction A Linked List is a data structure used for storing a sequence of elements. Unlike arrays, linked lists consist of nodes where each node contains a value (or a pointer (or reference) to the next node in the sequence Head ~f-E-S-Er-, P a bili (data) Wl Pointer (Next nals) San ¥ Dynamic Size: Linked lists can easily grow and. shrink in size, making them suitable for applications where the number of elements is unknown or varying v Efficient Insertions/Deletions: Elements can be easily inserted or removed without the need to shift other elements, unlike arrays Head -fi-a-Bia- ~. } a Bi a mis (data) @ Pointer (Next node) <-7 v Dynamic Size: Linked lists can easily grow and shrink in size, making them suitable for applications where the number of elements is unknown or varying. v Efficient Insertions/Deletions: Elements can be easily inserted or removed without the need to shift other elements, unlike arrays.Singly Linked List @ curious_programmer v What is a Singly Linked List ? A Singly Linked List is a data structure used for storing a sequence of elements where each element (node) points to the next one through a pointer. It consists of a series of conneded nodes, where each node contains a piece of data and a pointer (reference) to the next node in the sequence. Value (data) v Each node consists of two parts © Data/Value: Holds the actual value (e.g, 10) e Pointer: Stores the memory address of the next node. ¥ Unidirectional: Tt only allows traversal in one direction (from head to the last node) v Memory Efficient: Nodes are dynamically created and memory is allocated as needed ¥ Head Pointer: The list starts with a special pointer called “Head” that points to the first node in the list How to create a new node? Node is created, dynamically v [tofbws 5} >[Pante Wem] > TSTa1 1 + Data/Value (10)@ curious_programmer v What is a Doubly Linked List? A Doubly Linked List is a data structure used for storing a sequence of elements where each element (node) is connected to both its previous and next nodes through two pointers. Brae Tail Prev Data| 2 |->[Data [3 }->[Net[4 |<. we = NULL “Su------------------------------------ v Each node consists of three parts © Prev Pointer: Stores the memory address of the previous node. © Data/Value: Holds the actual value (e.9,20) v Next Pointer: Stores the memory address of the next node v Bidirectional: Supports traversal in both forward and backward directions. v More Memory: Requires extra memory for storing the previous pointer, unlike singly linked lists. v Head & Tail Pointers: The list has two special pointers: Head points to the first node © Tail points to the last node How to create a new node? Node is created. dynamically Bevree> ; Pal S o)>[e [20 pears Sa} + + + Prev Pointer (10) — Data/Value (20) Next Pointer (Points to 2°) (Points to 3)Circular Linked List @ curious_programmer v What is a Circular Linked List ? A Circular Linked List is a data structure used for storing a sequence of elements where each element (node) is connected to both its previous and next nodes through two pointers. Head Back to the -—> First Node ~~. Nea 7a b+ Beb Beals i RE manne" A NULL =” v Forms a Circle: The last node points back to the first node v No NULL Value: Unlike linear linked lists, there is no NULL pointer in a circular linked list because it forms a continuous loop. ¥ Can be Singly or Doubly Linked: 2 Singly Circular: Each node points to the next node, and the last node points back to the first node. y Doubly Circular: Each node points to both the next and previous nodes, and the last node points back to the first node v Head Pointer: Points to the first node in the list. wv How to create a new node? Node is created See dynamically om = es £ >3}>[Net]4 [4]}> A t Prey Pointer (10) ~-* Data/Value (20) Next Pointer (3) Singly Circular: ListInsertion in Linked List @ curious_programmer v How to insert an element into a Linked List ? Inserting an element into a Linked List involves creating a new node and adjusting pointers to link it correctly, There are three common operations: 1. Insert at the Beginning : Add a new node as the first node of the linked list 2. Insert at the End: Add a new node at the last node of the linked list 3. Insert at a Given Position: Add a new node at a specific position in the linked list 1. Insert at the Beginning: re eee 2 | Sf >| Next | 4 > NULL a Head 2. Insert at the End: ->|Head 1p [2 v2 3 bs[Nea[Nott f> nue New Node Node is created dynamically : a — Gait [Head] 1 [>| 2 >[2s/> 3 [=> NULL. b> Singly Circular : ListDeletion in Linked List @ curious_programmer v How to delete an element from a Linked List ? Inserting an element into a Linked List involves adjusting pointers to bypass the node to be deleted. There are three common operations 1. Delete from the Beginning: Remove the first node of the linked list. 2. Delete from the End: Remove the last node of the linked list. 3. Delete at a Given Position: Remove a node from a specific position in the linked list. 1. Delete from the Beginning: >([Head 10} >| 20TS }> [Nes [Sf > nue ———> seis} 2. Delete From the End: > ([Beea10 20 3 > [Ret] 3 nue a Head \ 3. Delete at a Given Position: — — = [Head [10 Fs] 20 |] 20 [3 }>[net | 4 fe nue Seen Singly Circular: ListReverse Linked List @ curious_programmer v How to reverse a Linked List ? Reversing a linked list means changing the direction of the pointers so that the last nade becomes the first node, reversing the list order v Steps to Reverse a Linked List: 1. Initialize three pointers: © Grey): Initially set to NULL © Gurrend): Initially set to Head © Glad: Points to the node after Current 2. Reverse pointers one by one: [Prev 10 [20 [> [Next |= NULL —, Heration continues 3. Move Prev, Current, and Next pointers one step forward. 4. Repeat until Current becomes NULL v Example: Grgiral uit > (NOL S126 SOEs} > wu. @ Prev : NULL © Current: +@ Next Pointer © Next : NULL + © Next »*© NULL wv Reverse List: [Hei So [20 [so S}> oe = >[EasoP ose S13 > =~. = zo > [Beall 36] S25 S59] SS S[No > wor Br] Singly Circular: ListChapter 4: Searching _ @ curious__programmer v4.1 Linear Search Linear Search is a simple searching algorithm that checks each element of a list sequentially until the desired element is found Tt works with both unsorted and sorted arrays. v Steps in Linear Search: 1. Start from the first element. © Srey: Initially set to NULL © Gumenb): Initially set to Head © Qlexd): Points to the node after Current 2. Reverse pointers one by one 3. Move Prev, Current, and Next pointers one step forward, 4. Repeat until Current becomes NULL: Y Example: Head @ NULL @ Start with the first element and compare each element with the target (7) @ When element 7 is found at index 2, return 2. v Ex le: 7 a =i, omple* (Head |10 [20] 20 [Spot s]3} en Y Start with the first element and compare each element with the target (7). Y When element 7 is found at index 2, return 2. { Result: 2 * Target = The value were searching for “7” > [Head [So |S [20 |S 1501-56 1S aa > noLinear Search @ curious__programmer v 4.1 Linear Search Linear Search is a simple searct wing algorithm that checks each element of a list Tt works with both unsorted and sorted arrays. sequentially until the desired element is found Y Steps in Linear Search 1. Start from the first element of the array (index ©) 2. Compare each element with the target value. 3. If the target value matches an element, return the index of the element. 4. TE the target value is not found by the end of the list, return -— 1 Gndicating nat found) v Example: Cea 427 SST e}> on Start —-->|conpare @ Start from the first element of the array Cindex ©) @ Compare 4 with 7 — Not Found, move to next element @ TF the target value matches an element @ Tf the target value is not found by the|Not Found. \ end of the list, return —4.) M Step A: __ Gaeis (AEN SSB TS > won. @ Step 1: Compare 4 with 7 —> Not Found, move to next element @ Step 2: Compare 2 with 72====5=5===525=5=2]) Match Found! Start ot index 2 @ Step 3: 7 equals 7, target found at index 2 + Target = The value were searching for “7”Binary Search @ curious_programmer V4A Linear Search _ Binary Search is an efficient searching algorithm that checks each element of a list sequentially until the desired element is found. It works with both unsorted and sorted arrays v Steps in Binary Search: 1. Initialize three pointers: ° Points to the first index of the array ° CHigh): Points to the last index of the array ° : CLow + High) / 2, points to the middle index 2. Repeat until the target value is found, or the Low pointer exceeds the High pointer 3. Calculate Mid { Mid = [Low +High)/ 2] | 4. Compare the riddle element Carray[Mid}) with the target value. Y Step 1: GCP EBISIBIS} +s @ Step 1: Compare 4 with 7 —> Net Found, move to next element @ Step 2: Compare 2 with 7 —> Search again 2. Gp azz ae Ts Is Te} Best) > Continue this process until the target value is found, or the search interval is empty CLow > High) % Important: The array must be sorted for binary search to workExample : Binary Search @ curious_programmer Bee aciplel Pinang Semen Binary Search is an efficient searching algorithm used to find a target value within a sorted array, It works by repeatedly dividing the search interval in halt, focusing, ‘on the micidle element VY Steps in Binary Search: 1. Initialize three pointers © GESWD: Points to the First index of the array © CHigh): Points to the last index of the array ° Wia> = Clow +High) /2, points to the middle index. 2. Repeat until the target value is found, or the Low pointer exceeds the High pointer: Cita wD ¥ Step 1: Compare 9 with array[3} Mid = [Low + High) /2 = [0+7] = 3. (tewT a [3 i sT77 9 TapsTs}onur Cea et ace Mid = 3, array[Mid] = 7 ---~ Search right half". @ Step 2: Compare 9 with array[5] eee ues Mid = 5, array[Mid] = 11. @ Step 3: Compare 9 with array[41 P a ‘) Mid = 4, array[Mid] = 9 Sse >[Target Found! equals 9 at index 4 until the target value = Continue this proc is found, or the search interval (Low > High). Result > +Example: Binary Search on Answer @ curious_programmer v Find the smallest divisor for which the sum of all quotients is < 7, Array of num{ [45,21, 36,45, 60] Y Steps in Binary Search: 1. Define the search space: Low =1, High is the maximum element of the array, 2. Calculate the Mid value: Mid = CLow + High) / 2. Find the sum of the quotients by dividing each number by Mid and rounding up: 3. Check the condition: If the sum of quotients is $7, narrow the search to the left half CHigh = Mid). fe Yes: narrow search to left half : (High = Mid) @ No: search the right half: (Low = Mid +1) 4. Repeat until Low exceeds High. The smallest divisor is the final value of Low. v Example: @ Calculate Mid: Mid = (Low+ High) / 2=[ 30) <-~. pee ee a 5 Sum of Quetients +i+ 2+2+2=s \<----- Sum >7 (No) @ Step 3: Compare 9 with array[4] (Newel [S[si7loTubstshslepe) Mid = 4, array[Mid] = 9 -------- > Search the right heft [Low = 30 +1. ee 2 ae # Quotient: How many times a number can be divided by the divisor when rounding up to the nearest whole number [@ Lee Pointer [S Mid © Pointer [= High Pointer > Sum of Quotients = 1+14+2+2+2=Applications of Binary Search 22s saree eee @ curious _programmer W Find the smollest divisor for which the sum of all quotients is < 7, Array of (115, 24, 36, 45,60] | >, ¥ Quickly locate items in a sorted list by repeatingly dividing the list in half 2, Searching in infinite space: © Efficiently find solutions in problems with an infinite or continuous space; like finding a threshold or optimal value. 3. Finding the peak element in an array where elements are first increasing and then decreasing 4. Check the condition: If the sum of quotients is < 7, narrow the Search to the left half (High = Mid) Yes: narrow search to left half (High = Mid) @ No: search the right half: CLow = Mid +1) @ Repeat until Low exceeds High. The smallest divisor is the final value, of Low @ Calculate Mid: Mid = (Low+ High) / 2 = [30] <—- Sum of Quotients =1+1+2+2+2=8 |<—————— -- GS Sum 57 (No) © Search the right half: Low = Mid +1 —>Low= 3041 Stow=31 (Nnte 521 [36] 45] so] 45], 60]--- om sa 2 Seg Se 7 Bee G@rcbenis = ent ott ote Sum = 7 (No) _ % Quotient: How many times a number can be divided by the divisor when rounding up to the nesred whole number @ Low Pointer [@ Mid Pointer [@ High PointerChapter 5: Sorting Algorithms @ curious_ programmer Introduction to Sorting Algorithms g Sorting algorithms are methods used to rearrange elements in a list or on array into a specific order (typically ascending Gr descending). They ore fundamental in computer science. for organizing data efficiently 4) Bubble Sort _ (2) Selection Sort _ (3) Insertion Sort ) (4) Merge Sort) (5) Quick Sort ) (6) Heap Sort (6) Heap Sort > (@) Counting Sort) (8) Radix Sort (8) Stobility & in-place Sorting Bubble Sort Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted Exomple: (A214 [61S [a+ [Sorter a | a 1 [é [1 }-~ (Sortedew™ aA Le }+>(Sortedw Linked ListBubble Sort What is Bubble Sort? Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted Bubble Sort Algorithm: For each pass, the largest aa [isisoten=s to n—1 | unsorted element “bubbles up” to the end Seer Oto n— i-1] Bae ee Unsorted Array oan Mees 4 fel 3 fa— Sop if arr{j] > A SA arr{j+1) > [2 [4 (SSS [2 |— Swap if arti > Sse! arrtj+1) Ly, 4 [3] 1 [4 |e J— Lawgest element i moves to end ~~ Pass 2: (i=1) = L2 Pelee | 4 Lé|—> Swap if arrLj] > ae arr{j+1) > ees 2)3]4 [6 |— Sve if arrtj] > ee arr(j+1) Final sorted list: [a [27273 ]4]4le|w For each pass, the largest unsorted element “bubbles up” to the endBubble Sort Example Start: Unsorted Array = [4,2,6,3, 1] Pass 1: Jeo [2] 2J4[e[3]fa Jae J=2 Bae ees G=0) —— SS] See —> —ae [414 [63 [el] t |— ne Suop Se) —- —> 2[/4i3ej2j14 1/6 St G=2) For each pass, the largest unsorted element “bubbles up” to the end Since 4 > 2, Swap 4<—2 Since 6 > 3, Swap 6 <—3 Largest element moves to end. \~ —> Swap if arr{j] > A<—3.<—1 —> Suop 6 > 3, Swap 6<—3 —> Swap if arrfj] > Swap 6 <—1 —> Swap if arrlj] > > (4121314 ][4 [6 |— sorted Array ~ 5 vSelection Sort What is Selection Sort? \- Selection Sort is a straighiforward sorting algorithm that repeatedly selects the minimum element from the unsorted portion of the list and swaps it with the first unsorted element This process is repeated until the entire list is sorted Selection Sort Algorithm: Cake For each pass, (SIS 1281S |— [Set min index= i — a aD eS +1. —~_No 2 tons t a) Yes ena Pass 2:Ci — eS SN —> Set min_index = j See net Find Minimum 1 I> Swop if arrfj] > —> (oa Seen) —> Swap ifarrij} >4 a on Poss 5:(i=4) 4[4Tel~ For each pass, the largest unsorted element “bubbles up” to the end Sorted Array= [4 [213] 414 [elwSelection Sort Example Start: Unsorted Array= [8,5,2,9,5] (SISi2sisi— ess 1s]—--s eins leet: Find Minimum | ————> [2 () Pass 1: (i=0) | 2TSTSTe [Ts ITS15 |—> swoop [Serted}->~—7_ 7 ' Pass 2: ( SiS. 8 |—> Swop — > Swop if arrlj] > [Sorted |» Pass 4: (i= 3) ' (21S (S18 [es Te \— sup [Sorted |» St Poss 5: Aa) (212 TSTST8 TS) sorted Array W Sorted Array= [1 ] 2/3 4[e|w~w For each pass, select the minimum from the unsorted portion and place it at the sorted portionInsertion Sort What is Insertion Sort? gy Insertion Sort is a simple sorting algorithm that builds the final “sorted list one element at a time. Tt takes each element from the unsorted part and inserts it into the correct position in the sorted part of the list. This process is repeated until the entire list is sorted Insertion Sort Algorithm: S2aa=)— aA Find Minimum | | While j 2 OQ and key < arrfjJ Pass 2: (i=1) —> Swap 2 [STSTSTS |—> sorted Array W (ZieIsisisisi>-— Gis is] For each pass, select the minimum from the unsorted portion and place it at the sorted portion sume ZInsertion Sort Example Start: Unsorted Array = L7,4,5,8,91 37) 41 5181S) — | Set key = arid | - + an rey 24 EY ——> Gs) o Insert m correct position w~ Pass 1:(i=1) 2. Shift [Sorted > ” Pass 2: ( 7717 SS |— Sire 5 <7, [Sorted L> Shift 7 to the right W Pass 3: (i=2) 2171818 |— neo suap S5(71[718 [8 |— no suap Pass 4: (i=4) 4[s[7{7lels —> No Swap ‘Sorted Aray- 2 SIaIZ eS) ~ Tn each pass, the key is compared and shifted left until itis placed at the correct sorted position Sorted Array= [4 Siz7leisi~Merge Sort What is Merge Sort? “GG Merge Sort is an efficient sorting algorithm, based on the Divide and Conquer strategy. Tt works by recursively dividing the list into two halves until each half contains a single element. Then, it merges. the halves back together in a sorted manner Merge Sort Algorithm: —— — ey. -Fori=ate Te Ee | Divide | > | _ Divide ory nie into two halves _| Poss 2:(i=2) ———> eae left half | 471717 |— | Merge Sort right half | Sorted }> Pass 3: (i=3) 415171718 [es |— no suap [Sorted >> Pass 4: (i=4) 41515171819 |— no svop Key Properties: ¥ Stability: Merge Sort maintains the relative order of equal elements ¥ Complexity: {2(nlogn) : Best and Average Case. OM login): Worst Case. ¥ Divide: Recursively divides the array into two halves, w Conquer: Combines the sorted halves into a single sorted list. Sorted Array [4] 4] 5 vMerge Sort Example Start: Unsorted Array = [8,3,5,9,4,7,6,2] eee BeSieicicsea | Merge Scr\ both hotves Divide. — — Divide & =y £. = Bis {s[s] {(4[7 (éj2 +4 ty tt +4 (s{3)—> (S12) 47)— Bie [Divide i Divide | |Merge.| at Merge. | Pass 3: Merge (sisisii}+-(sIsIs!>LEtielel7) (Gerted)] ~_=>|Merge}__ >| Merge. | Pass 3: Merge si3\— (Sisi9)\-— (2/4 Tells) (Serted| —____> | Merge} _+ | Merge: | Sorted Aray= [2] 3]4[Slel7[sts|~ ¥ Divide the array into two halves, sort each half, and then merge them to get the sorted array 1. Stability: Merge Sort maintains the relative order of equal elements. 2. Complexity: $1(nlogn): Best and Average Case. O(n logn) = Worst Case. 3. Divide: Recursively divides the array into two halves. 4. Conquer: Combines the sorted halves into a single sorted list. Sorted Aroy= [21S] 4[Slel7[eislvQuick Sort What is Quick Sort? )- Quick Sort is an efficient sorting algorithm based on the Divide and Conquer strategy. It works by selecting a “pivot” element and partitioning the list into elements than or equal to the pivot and elements greater than the pivot. The pros the sublists is recursively applied to Quick Sort Algorithm i @net)) {Less than or equal to pivot = ——» |Greater than pivot (s[sT3] ~l4T2) [slel2) ow oor" aaa \ a — Ei ites isj —-(Ss] Pass 3: Mer ge Start: [Tf left < right? | [Cheese a pivot and partition the array. | amare » [Quick Sort left partition | [Quick Sort ght partition | Key Properties: VY Stability: Quick Sort is not stable v Complexity: O(n logn): Best and Average Case On): Worst Case ¥ Divide: Recursively selects a pivot and partitions the array 4 Conquer: Recursively applics Quick Sort to partitions, combining the sortedQuick Sort Example Start: Unsorted Array = £7,2,1,6,8,5,3,41 | Partition —— ¥ (7l212 Tefs{sl4 yar : ~ - = ae Less than or equal to pivot |———>| Greater than pivot _| ection Pi + Bay Ia) SISTs) — +|sI6) (Ts) Sorted |“ > | Partition | L Merge} | Merge | Pass 1: Partition EESBEe->Bles|— Biviel7 (Seta (Sorted | Pass 2: Partition ae ae Meh) Ble |\— eileie) (Ble\ Sorted | —~ ~ | Partition) ___» | Merge] \ Sorted | Sorted Array = | W Select a pivot, partition the array, and recursively apply Quick Sort to the partitions. 1. Stability: Quick Sort is not stable 2. Complexity: Q(nlegn): Best and Average Case. OW”): Worst Case. 3. Divide: Recursively selects a pivot and partitions the array 4. Conquer: Recursively applies Quick Sort to partitions, combinng the sorted Sorted Array= [EI 2TS 141s 17letsil~wHeap Sort What is Heap Sort? Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to arrange elements in order. It first builds a Max-Heap from the list, then repeatedly removes the maxirnum element from the heap and plac the heap si * at the end of the list, reducing, 5 is repeated until the list is sorted > by one. This proce Heap Sort Algorithm: [Baila MaxcHeop | ——— Ba : be . cece ea El of fa PENRO of N as EE an abe -Sasae rted List | a Sn Swap max (root) with last aor the array a [Reduce heap size by 1 || Heapify the root? | rT ine —+ |[_End Key Properties: ¥ Stability: Heap Sort is not stable wv Complexity: D(n logn): Best and Average Case. OM?) Worst Case 3. Buide: Max-Heap: Builds a Max-Heap from the unsorted list. 4. Sort: Repeatedly removes the maximum element from the heap and appends it to the sorted portion. ee eee OOHeap Sort Example Start: Unsorted Array = [3,9,2,1,4,5,7,8,81 . Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to arrange elements in order. Tt first builds a Max Heap from the heap and places. it at the end of the list, reducing the heap size by one. st, then repeatedly removes the maximum element from the Heap Sort Example: [ Build Max-Heap | S ea / — SS. ¢ Remove, Max ) sae aS os ae: iba =f. ie Ca [Max-Heap |— =” SSESErE Pass 2: Heapify > >. a =a Swap 9 with) wehbe eae > [Max-Heap| Pass 3: Heapify x a (Zi7Tsl4Tsts) pes Se aS) Saeeannel = \ > [MaxHeap | Pass 5: Heapify —_ =. S — BE SesP) Bizl-+-Si— (4) 5/5\7\sisi9\ => ees [Sorted List Y Sorted Array= [AL [-Tsiléi7(sisisis\i~ @ Build a Max-Heap, remove the maximum repeatedly, and place it at the end of the list.Counting Sort “What is Counting Sort? Qg Counting Sort is a non-comparison-based sorting algorithm thot works. by counting the occurrences of each unique element in an input list Tt creates a count array to store the frequency of each element. Using this count array, it then calculates the positions of each element in the sorted output array, Counting Sort is efficient for sorting integers within a known, limited range Unsorted Array: 2 oe ase Ey (24 Gian 2 eS KS) aja j= 2 on Cron a. -lo | Count Occurrences | — SS eee) Pass 1: Heapify =a C=) as — 4 |—_—__+>|817171S5STS8Te61891 Place Elements at Calculated ») Positions; ——> [Max Heap | Pass 5: Heapify —_ - &)__ =>. —— (7l7Teltststs\ (a2) (2) EE) — 12) Ss [ Seta ict (BS) > | Max Heap | Pass 6 GSS SEP TSSTisSE) Key Properti & Stability: Counting Sort is stable Y Complexity: Q(n + KD: Best, Worst al Merage. Case, Omlegn): tc 3. Count Occurrences: Counts the number of occurrences of each element. 2 rmght For the Enput array 4. Sort: Uses the count array to place the elements at their calculated positions in the sorted output array.