Sorting Algorithms, Inversion Counting & Complexity
Hybrid Merge-Insertion Sort
[2-1 Hybrid Merge-Insertion Sort]
Stops recursion when a subarray size ≤ k and uses insertion sort for that subarray; MERGE is unchanged.
Pseudocode
INSERTION_SORT(A, p, r)
for j = p+1 to r
key = A[j]
i = j - 1
while i >= p and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
HYBRID_MERGE_SORT(A, p, r, k)
if r - p + 1 <= k
INSERTION_SORT(A, p, r)
else if p < r
q = floor((p + r) / 2)
HYBRID_MERGE_SORT(A, p, q, k)
Algorithm Analysis and Design: Key Concepts Explained
Q1. Explain the significance of Asymptotic Analysis in algorithm design.
Asymptotic analysis helps in evaluating the efficiency of an algorithm by measuring its time and space requirements as the input size grows large. It allows comparison of algorithms independent of hardware, programming language, or machine implementation. By using notations like Big-O, Big-Ω, and Big-Θ, it focuses on growth rate rather than exact execution time, helping designers choose scalable and efficient algorithms.
Q2.
Read MoreData Structures Concepts: Lists, Dictionaries, Trees, Graphs
Lists
Ordered (different from sorted) and linear.
Duplicates allowed.
Implementation: Array list: good for iteration, resizable; add = slide to right, remove = slide to left to close gap. Linked list: nodes & pointers, no shifting, grows dynamically, good for lots of insertions/deletions.
Core operations: add(newEntry), add(pos, newEntry), remove(pos, newEntry), replace(pos, newEntry), getEntry(pos), contains(entry), toArray(), getLength – numberOfEntries, isEmpty(), clear(). Helper methods: ensureCapacity,
Data Structures and Algorithms Code Snippets
Data Structures and Algorithms Implementations
Merge Sort Implementation
The mergeSort method recursively divides the array and then merges the sorted halves.
public static void mergeSort(int[] array) {
int length = array.length;
if (length <= 1)
return;
int middle = length / 2;
int[] leftArray = new int[middle];
int[] rightArray = new int[length - middle];
int j = 0;
for (int i = 0; i < length; i++) {
if (i < middle)
leftArray[i] =Data Structure Algorithms: Linked Lists, Trees, and Hashing
SINGLY LINKED LIST
// Insert at beginning 0
Algorithm InsertAtBeginning(data)
:1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->next = head4. head = newNode
// Insert at endAlgorithm InsertAtEnd(data):1. NewNode = (Node*)malloc(sizeof(Node))2. NewNode->data = data3. NewNode->next = NULL4. If head == NULL:
head = newNodeElse:temp = headWhile temp->next != NULL:temp = temp->nexttemp->next = newNode;
// Insert at position Algorithm InsertAtPos(data, pos):1.
Read MoreEssential C Programming Examples: Data Structures & Algorithms
Fundamental C Operations (String and Math)
String Reversal Without Built-in Functions
This program demonstrates manual string reversal using pointers and loops, calculating the string length without relying on strlen().
#include <stdio.h>
#include <string.h>
int main() {
char str[100], original[100];
char *start, *end, temp;
int length = 0;
printf("Enter a string: ");
scanf("%s", str); // accepts string without spaces
strcpy(original, str); // keep a copy of original