SNA INSTRUCTION

SNA INSTRUCTION

SPA INSTRUCTION

SPA INSTRUCTION

  ISZ INSTRUCTION

MORRIS MANO ASSEMBLY LEVEL LANGUAGE

INSERTION SORT ALGORITHM STEP BY STEP

INSERTION SORT ALGORITHM STEP BY STEP

🎯 What is Insertion Sort?

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time by inserting each element into its correct position in the already sorted part.

---

📌 Definition

Insertion Sort is a comparison-based algorithm in which each element is picked and inserted into its correct position in a sorted subarray.

---

🧠 How Insertion Sort Works

Steps:

1. Start from the second element
2. Compare it with elements before it
3. Shift larger elements one position right
4. Insert the element in correct position
5. Repeat for all elements

---

📊 Example

Unsorted Array:

A = [12, 11, 13, 5, 6]

---

🔁 Step-by-step

---

Pass 1 (Insert 11)

Compare 11 with 12 → shift 12

[11, 12, 13, 5, 6]

---

Pass 2 (Insert 13)

Already in correct position

[11, 12, 13, 5, 6]

---

Pass 3 (Insert 5)

Shift 13, 12, 11

[5, 11, 12, 13, 6]

---

Pass 4 (Insert 6)

Shift 13, 12, 11

[5, 6, 11, 12, 13]

---

📌 Final Sorted Array

[5, 6, 11, 12, 13]

---

💻 Algorithm (Pseudocode)

InsertionSort(A, n)

1. for i = 1 to n-1
2.     key = A[i]
3.     j = i - 1
4.     while j >= 0 AND A[j] > key
5.         A[j + 1] = A[j]
6.         j = j - 1
7.     A[j + 1] = key

---

🐍 Python Program for Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1

        arr[j + 1] = key

    return arr

# Example
arr = [12, 11, 13, 5, 6]

result = insertion_sort(arr)

print("Sorted Array:", result)

---

Output:

Sorted Array: [5, 6, 11, 12, 13]

---

⚡ Time Complexity

Case	Complexity
Best Case	O(n)
Worst Case	O(n²)
Average Case	O(n²)

---

📊 Space Complexity

• O(1) (in-place sorting)

---

🆚 Insertion Sort vs Other Sorting

Feature	Insertion Sort	Bubble Sort	Selection Sort
Method	Insert element in correct position	Swap adjacent elements	Select minimum element
Best Case	O(n)	O(n)	O(n²)
Efficiency	Good for small/nearly sorted data	Poor	Poor
Stability	✅ Stable	✅ Stable	❌ Not stable

---

📌 Advantages

• Simple to implement
• Efficient for small or nearly sorted data
• Stable sorting algorithm
• Works in-place (no extra memory)

---

❌ Disadvantages

• Slow for large datasets
• O(n²) complexity in worst case

---

🧠 Real Life Example

• Arranging playing cards in hand 🃏
• Inserting a new book in a sorted bookshelf 📚

---

📌 Summary

• Insertion Sort builds a sorted list step by step
• Each element is inserted in correct position
• Best performance when data is already nearly sorted
• Simple but not suitable for large datasets

---

❓ Important Questions

Short Questions

1. What is insertion sort?
2. What is key element in insertion sort?
3. What is best case complexity?
4. Is insertion sort stable?
5. Give one real-life example.

---

Long Questions

1. Explain insertion sort with example.
2. Write algorithm of insertion sort.
3. Write Python program for insertion sort.
4. Compare insertion sort with bubble and selection sort.
5. Explain advantages and disadvantages of insertion sort.

RADIX SORT ALGORITHM STEP BY STEP

RADIX SORT ALGORITHM STEP BY STEP

SEARCHING ALGORITHM

1. LINEAR SERACH ALGORITHM - CLICK HERE
2. BINARY SEARCH ALGORITHM - CLICK HERE

BINARY SEARCH ALGORITHM STEP BY STEP

BINARY SEARCH ALGORITHM STEP BY STEP

🎯 What is Binary Search?

Binary Search is a fast searching technique used to find an element in a sorted array by repeatedly dividing the search space into half.

---

📌 Definition

Binary Search is a divide-and-conquer algorithm that finds an element in a sorted list by comparing the target value with the middle element.

---

⚠️ Important Condition

✔ The array must be sorted (ascending or descending)
❌ Binary search does NOT work on unsorted data

---

🧠 How Binary Search Works

Steps:

1. Find middle element
2. Compare middle element with target
3. If match → stop
4. If target is smaller → search left half
5. If target is larger → search right half
6. Repeat until found or range becomes empty

---

📊 Example

Sorted Array:

A = [10, 20, 30, 40, 50, 60, 70]

Target:

Find 50

---

Step-by-step:

Step	Low	High	Mid	Value	Action
1	0	6	3	40	50 > 40 → right half
2	4	6	5	60	50 < 60 → left half
3	4	4	4	50	✅ Found

---

💻 Algorithm (Pseudocode)

BinarySearch(A, key)

1. low = 0
2. high = n - 1

3. while low <= high
4.     mid = (low + high) / 2
5.     if A[mid] == key
6.         return mid
7.     else if key < A[mid]
8.         high = mid - 1
9.     else
10.        low = mid + 1

11. return -1

---

🐍 Python Program for Binary Search

def binary_search(arr, key):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == key:
            return mid
        elif key < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1

    return -1

# Example
arr = [10, 20, 30, 40, 50, 60, 70]
key = 50

result = binary_search(arr, key)

if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

---

Output:

Element found at index: 4

---

⚡ Time Complexity

Case	Complexity
Best Case	O(1)
Worst Case	O(log n)
Average Case	O(log n)

---

📊 Why Binary Search is Fast?

Each step reduces search space by half:

Example:

• 8 elements → 4 → 2 → 1

So it grows very slowly compared to linear search.

---

🆚 Binary Search vs Linear Search

Feature	Linear Search	Binary Search
Data Requirement	Unsorted	Sorted
Speed	Slow (O(n))	Fast (O(log n))
Method	Sequential	Divide & Conquer
Efficiency	Low	High

---

📌 Advantages of Binary Search

• Very fast for large datasets
• Reduces comparisons drastically
• Efficient algorithm

---

❌ Disadvantages

• Requires sorted data
• Not suitable for dynamic/unsorted lists
• More complex than linear search

---

🧠 Real Life Example

• Finding a word in dictionary 📖
• Searching a name in sorted telephone directory 📞

---

📌 Summary

• Binary search works only on sorted data.
• It divides the list into halves repeatedly.
• It is much faster than linear search.
• Time complexity is O(log n).

---

❓ Important Questions

Short Questions

1. What is binary search?
2. What is the condition for binary search?
3. What is time complexity of binary search?
4. What is mid element?
5. Give one real-life example.

---

Long Questions

1. Explain binary search with example.
2. Write algorithm of binary search.
3. Write Python program for binary search.
4. Compare linear and binary search.
5. Explain time complexity of binary search.

LINEAR SEARCH ALGORITHM STEP BY STEP

LINEAR SEARCH ALGORITHM STEP BY STEP

🎯 What is Linear Search?

Linear Search is a simple searching technique used to find an element in a list or array by checking each element one by one from the beginning to the end.

---

📌 Definition

Linear Search is a sequential searching algorithm where each element is compared with the target value until a match is found or the list ends.

---

🧠 How Linear Search Works

• Start from the first element
• Compare each element with the target value
• If match found → Stop
• If not found → Move to next element
• Continue until end of list

---

📊 Example

Array:

A = [10, 25, 30, 45, 60]

Target:

Find 30

---

Step-by-step Process:

Step	Element Checked	Result
1	10	Not match
2	25	Not match
3	30	✅ Match found

---

💻 Algorithm (Pseudocode)

LinearSearch(A, n, key)

1. for i = 0 to n-1
2.     if A[i] == key
3.         return i
4. return -1

---

🐍 Linear Search Program (Python)

def linear_search(arr, key):
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

# Example
arr = [10, 25, 30, 45, 60]
key = 30

result = linear_search(arr, key)

if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

---

Output:

Element found at index: 2

---

⚡ Best Case, Worst Case

Case	Condition	Complexity
Best Case	Element at first position	O(1)
Worst Case	Element at last or not present	O(n)
Average Case	Random position	O(n)

---

📌 Advantages of Linear Search

• Very simple to understand
• Works on unsorted data
• No extra memory required

---

❌ Disadvantages

• Slow for large data sets
• Not efficient compared to binary search

---

🆚 Linear Search vs Binary Search

Feature	Linear Search	Binary Search
Data Requirement	Unsorted	Sorted
Speed	Slow	Fast
Method	Sequential	Divide & Conquer

---

🧠 Real Life Example

• Searching a name in attendance register
• Finding a contact in phone list (unsorted)

---

📌 Summary

• Linear search checks elements one by one.
• It is simple but inefficient for large data.
• Best used for small or unsorted datasets.

---

❓ Important Questions

Short Questions

1. What is linear search?
2. What is time complexity of linear search?
3. Give one advantage of linear search.
4. Is sorting required in linear search?
5. Write one real-life example.

---

Long Questions

1. Explain linear search with example.
2. Write algorithm of linear search.
3. Write a program for linear search.
4. Compare linear and binary search.
5. Explain best and worst case of linear search.

GRAPH THEORY

1. GRAPH THEORY ALGORITHMS - CLICK HERE

2. GRAPH THEORY N.DEO CHAPTER WISE QUESTION - CLICK HERE

GRAPH THEORY ALGORITHMS

 1. DEPTH FIRST SEARCH - CLICK HERE

 2. BREADTH FIRST SEARCH - CLICK HERE

 3. FLOYD ALGORITHM - 

 4. WARSHALL ALGORITHM - 

 5. PRIM'S ALGORITHM - CLICK HERE

 6. KRUSKAL'S ALGORITHM -CLICK HERE

 7. DYSTRA'S ALGORITHM -  CLICK HERE