Quick Sort: Algorithm & Implementation

1️⃣ What is Quick Sort?

🔹 Quick Sort is a divide-and-conquer sorting algorithm.
🔹 It selects a pivot element and partitions the array so that:

• Elements smaller than pivot go to the left.
• Elements greater than pivot go to the right.
  🔹 The process repeats recursively until the array is sorted.

✅ Time Complexity

Case	Complexity
Best Case (Balanced Partitioning)	O(n log n)
Average Case	O(n log n)
Worst Case (Already Sorted, Unbalanced Partitioning)	O(n²)

✅ Space Complexity

• O(log n) (for recursive stack calls)

✅ Is it Stable?

❌ No (Relative order of equal elements may change)

---

2️⃣ How Quick Sort Works

🔹 Select a pivot element.
🔹 Partition the array so that:

• Left part contains elements < pivot
• Right part contains elements > pivot
  🔹 Recursively sort left and right partitions.

Step-by-Step Example

📝 Input: [10, 80, 30, 90, 40, 50, 70]
Pivot = 70 (can be any element, commonly last, first, or random)

Step	Array State	Partitioning Around Pivot
1	[10, 30, 40, 50, 70, 90, 80]	Pivot 70 placed correctly
2	`[10, 30, 40, 50]	70
3	`[10, 30]	40

🔹 Final Sorted Array: [10, 30, 40, 50, 70, 80, 90]

---

3️⃣ Quick Sort Algorithm

🔹 Pseudocode

QuickSort(arr, low, high):
    if low < high:
        pivotIndex = Partition(arr, low, high)
        QuickSort(arr, low, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, high)

Partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1:
        if arr[j] < pivot:
            i++
            Swap arr[i] and arr[j]
    Swap arr[i+1] and arr[high]
    return i+1

---

4️⃣ Quick Sort Implementation in C

#include <stdio.h>

// Function to swap two elements
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function to place pivot in correct position
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // Choosing last element as pivot
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 10 80 30 90 40 50 70
Sorted array: 10 30 40 50 70 80 90

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Faster than other O(n²) algorithms like Selection and Insertion Sort.
✔ Efficient for large datasets (O(n log n) in average case).
✔ In-place sorting (O(log n) extra space for recursion).

❌ Disadvantages

❌ Worst case O(n²) if pivot selection is poor (already sorted or reversed).
❌ Not stable (relative order of equal elements may change).
❌ Uses recursion, which may cause stack overflow for large arrays.

---

6️⃣ When to Use Quick Sort?

🔹 Best for large datasets (better than Bubble, Insertion, or Selection Sort).
🔹 Useful when in-place sorting is required (O(1) extra space).
🔹 Not ideal if stable sorting is required (use Merge Sort instead).

💡 For best performance, use a randomized or median pivot selection! 🚀

 

Selection Sort: Algorithm & Implementation

1️⃣ What is Selection Sort?

🔹 Selection Sort is a simple comparison-based sorting algorithm.
🔹 It selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part.
🔹 It continues this process until the entire array is sorted.

✅ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n²)
Average Case	O(n²)
Worst Case (Reversed Order)	O(n²)

✅ Space Complexity

• O(1) (In-place sorting)

✅ Is it Stable?

❌ No (It may change the relative order of equal elements)

---

2️⃣ How Selection Sort Works

🔹 The algorithm divides the array into sorted and unsorted parts.
🔹 It finds the minimum element in the unsorted part and swaps it with the first element of the unsorted part.
🔹 This process is repeated for all elements.

Step-by-Step Example

📝 Input: [29, 10, 14, 37, 13]

Step	Array State	Minimum Found	Swap Performed
1	[29, 10, 14, 37, 13]	10	Swap 29 ↔ 10
2	[10, 29, 14, 37, 13]	13	Swap 29 ↔ 13
3	[10, 13, 14, 37, 29]	14	No swap needed
4	[10, 13, 14, 37, 29]	29	Swap 37 ↔ 29
5	[10, 13, 14, 29, 37]	37	No swap needed

🔹 Final Sorted Array: [10, 13, 14, 29, 37]

---

3️⃣ Selection Sort Algorithm

🔹 Pseudocode

for i = 0 to n-2:
    minIndex = i
    for j = i+1 to n-1:
        if arr[j] < arr[minIndex]:
            minIndex = j
    Swap arr[i] and arr[minIndex]

---

4️⃣ Selection Sort Implementation in C

#include <stdio.h>

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find the minimum element in the remaining unsorted array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum element with the first element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Simple & easy to implement
✔ Works well for small datasets
✔ Performs well when memory writes are costly (e.g., flash memory)
✔ Does not require extra memory (O(1) space complexity)

❌ Disadvantages

❌ Inefficient for large datasets (O(n²))
❌ Slower than Quick Sort & Merge Sort
❌ Not a stable sorting algorithm

---

6️⃣ When to Use Selection Sort?

🔹 Best for small datasets (e.g., <100 elements).
🔹 Good when memory writes are expensive (fewer swaps).
🔹 Not ideal for large datasets; use Merge Sort or Quick Sort instead. 🚀

 

Selection Sort: Algorithm & Implementation

1️⃣ What is Selection Sort?

🔹 Selection Sort is a simple comparison-based sorting algorithm.
🔹 It selects the smallest (or largest) element from the unsorted part and swaps it with the first element of the unsorted part.
🔹 It continues this process until the entire array is sorted.

✅ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n²)
Average Case	O(n²)
Worst Case (Reversed Order)	O(n²)

✅ Space Complexity

• O(1) (In-place sorting)

✅ Is it Stable?

❌ No (It may change the relative order of equal elements)

---

2️⃣ How Selection Sort Works

🔹 The algorithm divides the array into sorted and unsorted parts.
🔹 It finds the minimum element in the unsorted part and swaps it with the first element of the unsorted part.
🔹 This process is repeated for all elements.

Step-by-Step Example

📝 Input: [29, 10, 14, 37, 13]

Step	Array State	Minimum Found	Swap Performed
1	[29, 10, 14, 37, 13]	10	Swap 29 ↔ 10
2	[10, 29, 14, 37, 13]	13	Swap 29 ↔ 13
3	[10, 13, 14, 37, 29]	14	No swap needed
4	[10, 13, 14, 37, 29]	29	Swap 37 ↔ 29
5	[10, 13, 14, 29, 37]	37	No swap needed

🔹 Final Sorted Array: [10, 13, 14, 29, 37]

---

3️⃣ Selection Sort Algorithm

🔹 Pseudocode

for i = 0 to n-2:
    minIndex = i
    for j = i+1 to n-1:
        if arr[j] < arr[minIndex]:
            minIndex = j
    Swap arr[i] and arr[minIndex]

---

4️⃣ Selection Sort Implementation in C

#include <stdio.h>

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        
        // Find the minimum element in the remaining unsorted array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // Swap the found minimum element with the first element
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 29 10 14 37 13
Sorted array: 10 13 14 29 37

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Simple & easy to implement
✔ Works well for small datasets
✔ Performs well when memory writes are costly (e.g., flash memory)
✔ Does not require extra memory (O(1) space complexity)

❌ Disadvantages

❌ Inefficient for large datasets (O(n²))
❌ Slower than Quick Sort & Merge Sort
❌ Not a stable sorting algorithm

---

6️⃣ When to Use Selection Sort?

🔹 Best for small datasets (e.g., <100 elements).
🔹 Good when memory writes are expensive (fewer swaps).
🔹 Not ideal for large datasets; use Merge Sort or Quick Sort instead. 

 

Insertion Sort: Algorithm & Implementation

1️⃣ What is Insertion Sort?

🔹 Insertion Sort is a simple sorting algorithm that builds the sorted array one item at a time.
🔹 It compares each element with the previous ones and inserts it at the correct position.
🔹 Best suited for small or nearly sorted datasets.

✅ Time Complexity

Case	Complexity
Best Case (Already Sorted)	O(n)
Average Case	O(n²)
Worst Case (Reversed Order)	O(n²)

✅ Space Complexity

• O(1) (In-place sorting)

✅ Is it Stable?

✔ Yes (Preserves order of equal elements)

---

2️⃣ How Insertion Sort Works

🔹 The algorithm divides the array into sorted and unsorted parts.
🔹 It picks an element from the unsorted part and inserts it into the correct position in the sorted part.

Step-by-Step Example

📝 Input: [8, 4, 1, 6, 3]

Step	Key Element	Sorted Part	Unsorted Part	Action
1	4	8	4, 1, 6, 3	Move 8 right, Insert 4
2	1	4, 8	1, 6, 3	Move 8, 4 right, Insert 1
3	6	1, 4, 8	6, 3	Move 8 right, Insert 6
4	3	1, 4, 6, 8	3	Move 6, 4 right, Insert 3

🔹 Final Sorted Array: [1, 3, 4, 6, 8]

---

3️⃣ Insertion Sort Algorithm

🔹 Pseudocode

for i = 1 to n-1:
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key:
        arr[j + 1] = arr[j]  // Shift element right
        j = j - 1
    arr[j + 1] = key  // Insert key at the correct position

---

4️⃣ Insertion Sort Implementation in C

#include <stdio.h>

// Function to perform Insertion Sort
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        // Move elements that are greater than key one position ahead
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

🔹 Output

Original array: 12 11 13 5 6
Sorted array: 5 6 11 12 13

---

5️⃣ Advantages & Disadvantages

✅ Advantages

✔ Simple & easy to implement
✔ Works well for small datasets
✔ Efficient for nearly sorted data (O(n) best case)
✔ In-place sorting (O(1) space)

❌ Disadvantages

❌ Inefficient for large datasets (O(n²) worst case)
❌ Slower than Quick Sort & Merge Sort for large inputs

---

6️⃣ When to Use Insertion Sort?

🔹 Best for small datasets (e.g., <100 elements).
🔹 Great for nearly sorted data (performs in O(n) time).
🔹 Used in real-world scenarios like card sorting or keyboard typing auto-sorting.

💡 For larger datasets, use Merge Sort or Quick Sort! 🚀

 

Sorting in Data Structures

1️⃣ What is Sorting?

Sorting is the process of arranging elements in a particular order (ascending or descending). It helps in efficient searching, data retrieval, and processing.

2️⃣ Types of Sorting Algorithms

Sorting algorithms are mainly categorized into:

• Comparison-based Sorting (Bubble Sort, Selection Sort, Quick Sort, Merge Sort, etc.)
• Non-comparison Sorting (Counting Sort, Radix Sort, Bucket Sort, etc.)

---

3️⃣ Common Sorting Algorithms

Algorithm	Best Case	Worst Case	Average Case	Space Complexity	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌ No
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅ Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ Yes
Quick Sort	O(n log n)	O(n²)	O(n log n)	O(log n)	❌ No
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ No
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(n + k)	✅ Yes
Radix Sort	O(nk)	O(nk)	O(nk)	O(n + k)	✅ Yes

---

4️⃣ Sorting Algorithm Implementations in C

✅ 1. Bubble Sort (Simple but Inefficient)

Bubble Sort repeatedly swaps adjacent elements if they are in the wrong order.

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

✅ Simple but slow (O(n²))
❌ Not suitable for large datasets

---

✅ 2. Insertion Sort (Efficient for Small Datasets)

Insertion Sort builds a sorted array one item at a time.

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {9, 7, 5, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    insertionSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);
    
    return 0;
}

✅ Good for small datasets (O(n²))
✅ Performs well when data is nearly sorted

---

✅ 3. Merge Sort (Efficient, Uses Divide & Conquer)

Merge Sort divides the array into two halves, sorts them, and merges them.

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

✅ Efficient (O(n log n))
❌ Uses extra memory (O(n))

---

✅ 4. Quick Sort (Best for Large Datasets)

Quick Sort picks a pivot, partitions the array, and recursively sorts both halves.

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

✅ Fastest in practice (O(n log n) average case)
❌ Worst-case O(n²) if poorly implemented