What is Sorting?

Sorting ka matlab hota hai kisi data (like numbers, strings, etc.) ko ek specific order mein arrange karna — jaise ascending (small to large) ya descending (large to small) order mein.

Example:

Unsorted Array → [50, 10, 40, 30]

After Sorting → [10, 30, 40, 50] (Ascending Order)

Why is Sorting Important?

1. Fast Searching: Agar data sorted hai to search karna bohot easy ho jaata hai (Binary Search Algorithm sirf sorted data pe kaam karti hai).
2. Data Organization: Sorted data ko samajhna aur process karna easy hota hai — chahe wo student marks ho, product prices ya dates.
3. Optimization in Other Algorithms: Many algorithms (like merge intervals, greedy techniques, etc.) pehle sort karne ke baad kaam karte hain.

Real Life Examples:

• Phone contact list sorted by name
• Leaderboard sorted by score
• Files sorted by date

Sorting Algorithms:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Counting Sort

Bubble Sort

Bubble Sort ek basic sorting algorithm hai jo adjacent (paas-paas) elements ko compare karke sort karta hai. Yeh algorithm har pass mein largest element ko array ki last position tak "bubble" (float) kar deta hai, jaise paani mein bubble upar aate hain.

Definition: Bubble sort ek comparison-based sorting algorithm hai jo:

1. Repeatedly array ko traverse karta hai
2. Har traversal mein adjacent elements ko compare karta hai
3. Agar wo wrong order mein hain (left > right for ascending) toh swap kar deta hai
4. Yeh process tab tak repeat hota hai jab tak pure array sorted na ho jaye

Key Characteristics:

1. Simple but inefficient: Easy to implement but slow for large datasets (O(n²) time)

2. In-place algorithm: Constant extra space (O(1)) use karta hai

3. Stable sort: Equal elements ka original order maintain karta hai

4. Adaptive: Agar array nearly sorted hai toh jaldi sort ho jayega ho jayega

Examples:

1. Input: [5, 3, 8, 1, 2] → Output: [1, 2, 3, 5, 8]
2. Input: [10, 9, 8, 7] → Output: [7, 8, 9, 10]

Approach

Bubble sort algorithm adjacent elements ko compare karti hai aur agar woh sahi order mein nahi hain toh unhe swap kar deti hai. Yeh process har pass mein largest element ko last position pe pahuncha deta hai.

Steps:

1. Outer Loop: Har pass ke liye (n-1 passes)
2. Inner Loop: Adjacent elements ko compare karne ke liye
3. Compare & Swap: Agar left element > right element, toh swap karo
4. Optimization: Agar kisi pass mein koi swap nahi hua, toh array sorted hai

Dry Run

Array: [5, 3, 8, 1, 2]

Pass 1:

• Compare 5 & 3 → swap → [3, 5, 8, 1, 2]
• Compare 5 & 8 → no swap
• Compare 8 & 1 → swap → [3, 5, 1, 8, 2]
• Compare 8 & 2 → swap → [3, 5, 1, 2, 8]

Pass 2:

• Compare 3 & 5 → no swap
• Compare 5 & 1 → swap → [3, 1, 5, 2, 8]
• Compare 5 & 2 → swap → [3, 1, 2, 5, 8]

Pass 3:

• Compare 3 & 1 → swap → [1, 3, 2, 5, 8]
• Compare 3 & 2 → swap → [1, 2, 3, 5, 8]

Pass 4:

• Koi swap nahi hua → array sorted

Code

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {          // Outer loop for passes
        bool swapped = false;                // Optimization flag
        
        for(int j = 0; j < n-i-1; j++) {    // Inner loop for comparisons
            if(arr[j] > arr[j+1]) {         // Compare adjacent elements
                swap(arr[j], arr[j+1]);     // Swap if needed
                swapped = true;              
            }
        }
        
        if(!swapped) break;  // Agar koi swap nahi hua, toh array sorted hai
    }
}

int main() {
    int arr[] = {5, 3, 8, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }    
    bubbleSort(arr, n);
    cout<<endl;
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

Output:

Unsorted array: 5 3 8 1 2

Sorted array: 1 2 3 5 8

Code Explanation:

1. Outer Loop (i): Ye number of passes ko Controls karta hai (n-1 passes needed)
2. Inner Loop (j): Ye adjacent elements ko compare karta hai se
3. Swap Condition: If arr[j] > arr[j+1], swap karo
4. Optimization: swapped flag checks agar koi swap occurred
5. Early Termination: Agar pass mein koi swaps nhi, then array is sorted

Time Complexity Analysis

• Best Case (Already Sorted): O(n) - Sirf ek pass hi need hoti hai
• Worst Case (Reverse Sorted): O(n²) - All passes ki need hoti hai.
• Average Case: O(n²)

Advantages of Bubble Sort

1. Simple to understand and implement
2. Space efficient (O(1) extra space)
3. Stable sort (maintains relative order)

Disadvantages

1. Very slow for large datasets
2. Not practical for real-world applications

Selection Sort

Selection Sort ek simple comparison-based sorting algorithm hai jo array ko sorted aur unsorted dono parts mein divide karke kaam karti hai. Har iteration mein, yeh unsorted part ka minimum element dhundhti hai aur use sorted part ke end mein add kar deti hai.

Definition:

Selection sort ek in-place comparison algorithm hai jo:

1. Array ko logically do parts mein divide karta hai:

• Sorted part (left side -> starting mein empty)
• Unsorted part (right side -> pure array se shuru)

2. Har pass/iteration mein:

• Unsorted part ka minimum element find karta hai
• Use sorted part ke end ke saath swap kar deta hai

3. Yeh process tab tak repeat hota hai jab tak pure array sorted na ho jaye

Key Characteristics:

1. Time Complexity: Best/Worst/Average Case: O(n²) (Har baar pure unsorted part traverse karna padta hai)

2. Space Complexity: O(1) (In-place sorting - extra space nahi leta)

3. Unstable Sort: Equal elements ka original order maintain nahi karta

4. Minimum Swaps: Only O(n) swaps required (Bubble sort se better)

Examples:

1. Input: [5, 3, 8, 1, 2] → Output: [1, 2, 3, 5, 8]
2. Input: [10, 9, 8, 7] → Output: [7, 8, 9, 10]

Approach

Selection sort har pass mein smallest element dhundhta hai aur use apni correct position pe rakhta hai. Yeh algorithm array ko do parts mein divide karta hai:

1. Sorted part (left side)
2. Unsorted part (right side)

Steps:

1. Outer Loop: Har position ke liye (0 se n-1 tak)
2. Find Minimum: Unsorted part mein sabse chota element dhundho
3. Swap: Current position aur minimum element ko swap karo
4. Repeat: Jab tak pure array sorted na ho jaye

Dry Run

Array: [5, 3, 8, 1, 2]

Pass 1:

• Minimum in [5,3,8,1,2] = 1 (index 3)
• Swap 5 and 1 → [1, 3, 8, 5, 2]

Pass 2:

• Minimum in [3,8,5,2] = 2 (index 4)
• Swap 3 and 2 → [1, 2, 8, 5, 3]

Pass 3:

• Minimum in [8,5,3] = 3 (index 4)
• Swap 8 and 3 → [1, 2, 3, 5, 8]

Pass 4:

• Minimum in [5,8] = 5 (already in place)
• No swap needed

Final Sorted Array: [1, 2, 3, 5, 8]

Code

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for(int i = 0; i < n-1; i++) {          // Outer loop for passes
        int min_idx = i;                     // Assume current element is smallest
        
        for(int j = i+1; j < n; j++) {      // Find minimum in unsorted part
            if(arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        
        swap(arr[i], arr[min_idx]);          // Swap with correct position
    }
}

int main() {
    int arr[] = {5, 3, 8, 1, 2};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }    
    
    selectionSort(arr, n);
    cout << endl;
    cout << "Sorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    
    return 0;
}

Output:

Unsorted array: 5 3 8 1 2

Sorted array: 1 2 3 5 8

Code Explanation:

1. Outer Loop (i): Har position ke liye (0 se n-2 tak)

2. Find Minimum:

• min_idx mein current smallest ka index store karo
• Inner loop se unsorted part mein smallest dhundho

3. Swap: Current position aur minimum element ko swap karo

4. Repeat: Jab tak pure array sorted na ho jaye

Time Complexity Analysis

• Best Case: O(n²) - Har baar pure unsorted part ko check karna padta hai
• Worst Case: O(n²) - Same as best case
• Average Case: O(n²)

Advantages of Selection Sort

1. Simple to understand and implement
2. Space efficient (O(1) extra space)
3. Useful for small datasets

Disadvantages

1. Time complexity O(n²) - Large datasets ke liye slow
2. Not stable (equal elements ka order change ho sakta hai)

Insertion Sort

Insertion Sort ek simple comparison-based sorting algorithm hai jo array ko sorted aur unsorted parts mein logically divide karke kaam karta hai. Yeh algorithm playing cards sort karne ke tarah kaam karta hai - jaisa hum apne haath mein cards ko arrange karte hain.

Definition:

Insertion sort ek stable, in-place sorting algorithm hai jo:

1. Array ko do parts mein mantaa hai:

• Sorted part (left side)
• Unsorted part (right side)

2. Har iteration mein:

• Unsorted part ka pehla element uthata hai
• Use sorted part mein correct position par insert karta hai

3. Yeh process tab tak chalta hai jab tak pure array sorted na ho jaye

Key Characteristics

1. Time Complexity:

• Best Case (Already sorted): O(n)
• Worst Case (Reverse sorted): O(n²)
• Average Case: O(n²)

2. Space Complexity: O(1) (In-place sorting)

3. Stable Sort: Equal elements ka original order maintain karta hai

4. Adaptive: Nearly sorted arrays ke liye efficient hota hai

Working Process

Step-by-Step Approach:

1. Pehla element ko sorted part maano
2. Agla element (key) uthao aur sorted part mein iski sahi position dhundho
3. Position milne par, sab elements ko ek position right shift karo
4. Key ko uski correct position par insert karo
5. Pure array sorted ho jane tak repeat karo

Dry Run Example

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

1. Pass 1: [12 | 11,13,5,6] → 12 sorted part mein
2. Pass 2: [11,12 | 13,5,6] → 11 ko 12 se pehle insert kiya
3. Pass 3: [11,12,13 | 5,6] → 13 apni jagah par sahi hai
4. Pass 4: [5,11,12,13 | 6] → 5 ko start mein insert kiya
5. Pass 5: [5,6,11,12,13] → 6 ko 5 aur 11 ke beech insert kiya

Code

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    for(int i=1; i<n; i++) {          // i=1 se start (pehla element sorted)
        int key = arr[i];              // Current element to insert
        int j = i-1;
        
        // Shift elements greater than key to right
        while(j>=0 && arr[j]>key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;               // Correct position for key
    }
}

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

    cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }    
    
    insertionSort(arr, n);
    cout<<endl;
    cout << "Sorted array: ";
    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

Output:

Unsorted array: 12 11 13 5 6

Sorted array: 5 6 11 12 13

Advantages & Disadvantages

Advantages:

1. Simple implementation
2. Small datasets ke liye efficient
3. Nearly sorted data ke liye best (O(n) time)
4. Online algorithm (new elements aane par easily sort kar sakte hain)

Disadvantages:

1. Large datasets ke liye slow (O(n²) time)
2. Bubble sort aur selection sort se thoda complex

Merge Sort

Merge Sort ek divide-and-conquer sorting algorithm hai jo array ko recursively smaller subarrays mein divide karke sort karta hai, fir sorted subarrays ko merge karke final sorted array produce karta hai.

Definition:

Merge sort ek stable, comparison-based sorting algorithm hai jo:

1. Array ko divide karta hai - middle point se do equal (or nearly equal) parts mein
2. Conquer karta hai - dono halves ko recursively sort karta hai
3. Combine karta hai - do sorted halves ko merge karke final sorted array banata hai

Key Characteristics

1. Time Complexity: Best/Worst/Average Case: O(n log n)

2. Space Complexity: O(n) (Auxiliary space for merging)

3. Stable Sort: Equal elements ka original order maintain karta hai

4. Not In-place: Extra space use karta hai

Working Process

Step-by-Step Approach:

1. Divide: Array ko middle point se do equal parts mein divide karo
2. Recursively Sort: Dono halves ko separately sort karo
3. Merge: Do sorted halves ko merge karke final sorted array banao

Dry Run Example

Array: [38, 27, 43, 3, 9, 82, 10]

1. Divide: [38,27,43,3] and [9,82,10]

2. Left Half Sort:

• [38,27] and [43,3]
• [27,38] and [3,43]
• Merge: [3,27,38,43]

3. Right Half Sort:

• [9,82] and [10]
• [9,82] and [10]
• Merge: [9,10,82]

4. Final Merge: [3,9,10,27,38,43,82]

Code

#include <iostream>
using namespace std;

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // Temporary arrays
    int L[n1], R[n2];
    
    // Copy data to temp arrays
    for(int i=0; i<n1; i++) L[i] = arr[l+i];
    for(int j=0; j<n2; j++) R[j] = arr[m+1+j];
    
    // Merge temp arrays back
    int i=0, j=0, k=l;
    while(i<n1 && j<n2) {
        if(L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    
    // Copy remaining elements
    while(i<n1) arr[k++] = L[i++];
    while(j<n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int l, int r) {
    if(l >= r) return;
    
    int m = l + (r-l)/2;
    mergeSort(arr, l, m);
    mergeSort(arr, m+1, r);
    merge(arr, l, m, r);
}

int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr)/sizeof(arr[0]);

    cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }        
    mergeSort(arr, 0, n-1);
    
    cout<<endl;
    cout << "Sorted array: ";
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    
    return 0;
}

Output:

Unsorted array: 38 27 43 3 9 82 10

Sorted array: 3 9 10 27 43 82

Advantages & Disadvantages

Advantages:

1. Consistent O(n log n) time complexity
2. Stable sort (order maintain karta hai)
3. Large datasets ke liye suitable
4. External sorting ke liye best (jab data memory se zyada ho)

Disadvantages:

1. Extra space requirement (O(n))
2. Small datasets ke liye thoda slow (recursive overhead)
3. In-place implementation complex hoti hai

Quick Sort

Quick Sort ek popular divide-and-conquer sorting algorithm hai jo array ko recursively sort karta hai. Yeh algorithm ek pivot element select karta hai aur array ko rearrange karta hai such that:

• Pivot ke left side mein sab elements chote hote hain
• Pivot ke right side mein sab elements bade hote hain

Definition:

Quick sort ek comparison-based, unstable sorting algorithm hai jo:

1. Pivot select karta hai (usually last element)
2. Partition karta hai array ko pivot ke around
3. Recursively sort karta hai left and right partitions

Key Characteristics

1. Time Complexity:

• Best/Average Case: O(n log n)
• Worst Case: O(n²) (when array already sorted)

2. Space Complexity: O(log n) (recursion stack)

3. Unstable Sort: Equal elements ka order change ho sakta hai

4. In-place: Extra space negligible (except recursion stack)

Working Process

Step-by-Step Approach:

1. Pivot Selection: Last element as pivot

2. Partitioning:

• Elements < pivot ko left mein move karo
• Elements > pivot ko right mein move karo
• Pivot ko correct position par place karo

3. Recursion:

• Left partition ko sort karo
• Right partition ko sort karo

Dry Run Example

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

1. Initial: [10,80,30,90,40,50,70] (pivot=70)

2. Partition 1:

• 10 < 70 → swap with itself
• 80 > 70 → skip
• 30 < 70 → swap with 80 → [10,30,80,90,40,50,70]
• Final swap pivot → [10,30,50,40,70,90,80]

3. Left Sort: [10,30,50,40]

4. Right Sort: [90,80]

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

Code

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Pivot as last element
    int i = low - 1;       // Index of smaller element
    
    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);
    }
}

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

   cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }    
    
    quickSort(arr, 0, n-1);
   
    cout<<endl;    
    cout << "Sorted array: ";
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    
    return 0;
}

Output:

Unsorted array: 10 80 30 90 40 50 70

Sorted Array: 10 30 40 50 70 80 90

Advantages & Disadvantages

Advantages:

1. Average case mein fastest (O(n log n))
2. Space efficient (in-place)
3. Cache friendly (good locality of reference)
4. Tail recursion optimized

Disadvantages:

1. Worst case O(n²) (but avoidable)
2. Unstable sort
3. Pivot selection critical for performance

Counting Sort

Counting Sort ek non-comparison based sorting algorithm hai jo elements ko unki frequency count ke basis pe sort karti hai. Yeh algorithm specifically useful hai jab:

1. Elements ki range (max-min) reasonably small ho
2. Elements integers ho (ya integer representation possible ho)

Definition:

Counting sort ek stable, integer sorting algorithm hai jo:

1. Har element ki frequency count ko karti hai
2. Cumulative count calculate karti hai
3. Elements ko unki correct position par place karti hai

Key Characteristics

1. Time Complexity: O(n + k) where k = range of input

2. Space Complexity: O(n + k) (auxiliary space)

3. Stable Sort: Equal elements ka original order maintain karta hai

4. Non-Comparison Based: Elements ko compare nahi karta

Working Process

Step-by-Step Approach:

1. Find Range: Maximum element in array
2. Count Frequency: Har element kitni baar aaya hai
3. Cumulative Count: Position determine karne ke liye
4. Place Elements: Correct position par elements place karo
5. Copy Back: Sorted array ko original array mein copy karo

Dry Run Example

Array: [4, 2, 2, 8, 3, 3, 1]

1. Step 1: Max element = 8

2. Step 2: Count array = [0,1,2,2,1,0,0,0,1]

3. (indices 0-8, values 1-8)

4. Step 3: Cumulative count = [0,1,3,5,6,6,6,6,7]

5. Step 4: Place elements:

• 1 at position 1-1=0 → [1,0,0,0,0,0,0]
• 3 at position 5-1=4 → [1,0,0,3,0,0,0] etc.

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

Code

#include <iostream>
#include <vector>
using namespace std;

void countingSort(int arr[], int n) {
    // Find maximum element
    int max = arr[0];
    for(int i=1; i<n; i++) {
        if(arr[i] > max) max = arr[i];
    }

    // Create count array
    vector<int> count(max+1, 0);
    
    // Store count of each element
    for(int i=0; i<n; i++) {
        count[arr[i]]++;
    }

    // Modify count array to cumulative count
    for(int i=1; i<=max; i++) {
        count[i] += count[i-1];
    }

    // Build output array
    vector<int> output(n);
    for(int i=n-1; i>=0; i--) {
        output[count[arr[i]] = arr[i];
        count[arr[i]]--;
    }

    // Copy output to original array
    for(int i=0; i<n; i++) {
        arr[i] = output[i];
    }
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Unsorted array: ";
    for(int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }    

    countingSort(arr, n);
    cout<<endl;

    cout << "Sorted array: ";
    for(int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}

Output:

Unsorted array: 5 3 8 1 2

Sorted array: 1 2 3 5 8

Advantages & Disadvantages

Advantages:

1. Linear time complexity O(n+k)
2. Stable sort (order maintain karta hai)
3. Comparison-based sorts se faster when k is small
4. Deterministic running time

Disadvantages:

1. Only integers ke liye suitable
2. Large range (k) ke liye inefficient
3. Extra space requirement (not in-place)