Contents

Sorting in C++ STL................................................................................................................................................. 8

Example: Sorting with sort() ............................................................................................................................. 8
Sorting in Descending Order ................................................................................................................................. 9
Sorting with a Custom Order (Using Comparator Function)............................................................................. 9
Conclusion ............................................................................................................................................................. 10
Sorting using Built-in Methods in Java............................................................................................................... 10
Sorting using Built-in Methods in Java............................................................................................................... 15
1. [Link]() ...................................................................................................................................................... 15
2. [Link]() ............................................................................................................................................... 17
Conclusion ............................................................................................................................................................. 19
1. Sorting Arrays of Primitive Types................................................................................................................... 20
2. Sorting a Subarray ............................................................................................................................................ 20
3. Sorting Non-Primitive Types Using Comparable Interface .......................................................................... 20
4. Sorting Using Comparator Interface .............................................................................................................. 21
5. Reversing Order (Descending) with Wrapper Classes .................................................................................. 22
6. Sorting Integers Based on Even and Odd Numbers ...................................................................................... 22
Key Notes: .............................................................................................................................................................. 22
[Link]() in Java .............................................................................................................................................. 23
Example 1: Basic Sorting and Reverse Sorting ...................................................................................................... 23
Code: ...................................................................................................................................................................... 23
Output: ................................................................................................................................................................... 23
Explanation: .......................................................................................................................................................... 23
Note: ....................................................................................................................................................................... 23
Example 2: Sorting Using the Comparable Interface ......................................................................................... 23
Code: ...................................................................................................................................................................... 24
Output: ................................................................................................................................................................... 24
Explanation: .......................................................................................................................................................... 24
Example 3: Sorting Using the Comparator Interface ......................................................................................... 24
Code: ...................................................................................................................................................................... 24
Output: ................................................................................................................................................................... 25
Explanation: .......................................................................................................................................................... 25
[Link]() vs [Link]()............................................................................................................................ 25
Conclusion: ............................................................................................................................................................ 25
Stability in Sorting Algorithms .................................................................................................................................... 26
What is a stable sorting algorithm?..................................................................................................................... 26
Example of stable sorting ..................................................................................................................................... 26
Where are stable sorting algorithms useful? ...................................................................................................... 26
Which sorting algorithms are stable? ................................................................................................................. 27
 Which sorting algorithms are unstable? ............................................................................................................. 27
Can we make any sorting algorithm stable?....................................................................................................... 27
Bubble Sort Algorithm ................................................................................................................................................. 28
How Bubble Sort Works........................................................................................................................................... 28
First Pass: .............................................................................................................................................................. 28
Second Pass: .......................................................................................................................................................... 28
Third Pass: ............................................................................................................................................................. 28
Illustration of Bubble Sort Process.......................................................................................................................... 29
C++ Code Implementation of Bubble Sort ............................................................................................................. 29
Code: ...................................................................................................................................................................... 29
Output: ................................................................................................................................................................... 30
Time and Space Complexity..................................................................................................................................... 30
Conclusion: ............................................................................................................................................................ 30
Selection Sort ................................................................................................................................................................. 30
Flowchart of the Selection Sort ............................................................................................................................ 30
How Selection Sort Works ................................................................................................................................... 30
Approach: .............................................................................................................................................................. 32
C++ Implementation:............................................................................................................................................ 32
Output: ................................................................................................................................................................... 32
Time and Space Complexity: ............................................................................................................................... 32
Insertion Sort Algorithm .............................................................................................................................................. 33
Characteristics of Insertion Sort: ............................................................................................................................ 33
How Insertion Sort Works ....................................................................................................................................... 33
First Pass: .............................................................................................................................................................. 33
Second Pass: .......................................................................................................................................................... 33
Third Pass: ............................................................................................................................................................. 33
Fourth Pass: ........................................................................................................................................................... 34
Illustration of Insertion Sort .................................................................................................................................... 34
Insertion Sort Algorithm .......................................................................................................................................... 34
Steps to sort an array of size N in ascending order: ........................................................................................... 34
C++ Code Implementation of Insertion Sort .......................................................................................................... 34
Code: ...................................................................................................................................................................... 34
Output: ................................................................................................................................................................... 35
Time and Space Complexity..................................................................................................................................... 35
Conclusion: ............................................................................................................................................................ 35
Merge Two Sorted Arrays ............................................................................................................................................ 35
Examples:............................................................................................................................................................... 36
Method 1: (Time Complexity: O(n1×n2)O(n1 \times n2), Space Complexity: O(n1+n2)O(n1 + n2)) ........... 36
Method 2: (Time Complexity: O(n1+n2)O(n1 + n2), Space Complexity: O(n1+n2)O(n1 + n2)) ................... 36
 Below is a dry run of the above approach: ......................................................................................................... 36
C++ Implementation:............................................................................................................................................ 36
Java Implementation: ........................................................................................................................................... 37
Output: ................................................................................................................................................................... 38
Time and Space Complexity: ............................................................................................................................... 38
Merge Function of Merge Sort .................................................................................................................................... 38
Examples:............................................................................................................................................................... 38
Method 1: (Time Complexity: O(n1×n2)O(n1 \times n2), Space Complexity: O(n1+n2)O(n1 + n2)) ........... 38
Method 2: (Time Complexity: O(n1+n2)O(n1 + n2), Space Complexity: O(n1+n2)O(n1 + n2)) ................... 39
C++ Implementation:............................................................................................................................................ 39
Output: ................................................................................................................................................................... 40
Time Complexity: .................................................................................................................................................. 40
Method 3: Using Maps (Time Complexity: O(nlog⁡n+mlog⁡m)O(n \log n + m \log m), Space
Complexity: O(n+m)O(n + m)) ............................................................................................................................ 40
C++ Implementation:............................................................................................................................................ 40
Output: ................................................................................................................................................................... 41
Time Complexity: .................................................................................................................................................. 41
Conclusion: ............................................................................................................................................................ 41
Merge Sort ............................................................................................................................................................. 41
Steps of Merge Sort ................................................................................................................................................... 41
Algorithm Diagram (Visual) .................................................................................................................................... 42
Merge Sort Implementation ..................................................................................................................................... 42
Time Complexity Analysis........................................................................................................................................ 43
Auxiliary Space Complexity..................................................................................................................................... 44
Key Characteristics of Merge Sort .......................................................................................................................... 44
Conclusion ............................................................................................................................................................. 44
Merge Sort Analysis ...................................................................................................................................................... 44
How Merge Sort Works............................................................................................................................................ 44
Time Complexity of Merge Sort .............................................................................................................................. 45
Applications of Merge Sort ...................................................................................................................................... 45
1. Sorting Linked Lists.......................................................................................................................................... 45
2. External Sorting ................................................................................................................................................ 45
3. Inversion Count Problem ................................................................................................................................. 45
Advantages of Merge Sort ........................................................................................................................................ 45
1. Time Complexity ............................................................................................................................................... 45
2. Stability .............................................................................................................................................................. 46
3. Easy Implementation ........................................................................................................................................ 46
4. Suitable for External Sorting ........................................................................................................................... 46
5. Parallelization .................................................................................................................................................... 46
6. Memory Efficiency ............................................................................................................................................ 46
Drawbacks of Merge Sort......................................................................................................................................... 46
1. Slower for Small Datasets................................................................................................................................. 46
2. Extra Memory ................................................................................................................................................... 46
3. Unnecessary Sorting ......................................................................................................................................... 46
4. More Complex Implementation ....................................................................................................................... 46
Recent Articles on Merge Sort ................................................................................................................................. 47
Solution for Extra Storage: Use Linked Lists......................................................................................................... 47
Conclusion ............................................................................................................................................................. 47
Naive Partition in Quicksort ................................................................................................................................ 47
Naive Partition Algorithm Steps .......................................................................................................................... 47
Quicksort Using Naive Partition .......................................................................................................................... 48
Output: ................................................................................................................................................................... 49
Time and Space Complexity of Naive Partition ................................................................................................. 49
Advantages and Disadvantages of Naive Partition ............................................................................................ 49
Lomuto Partition in Quicksort ............................................................................................................................ 50
Lomuto Partition Algorithm: ............................................................................................................................... 50
Quicksort using Lomuto Partition: ..................................................................................................................... 50
Output: ................................................................................................................................................................... 51
Time and Space Complexity: ............................................................................................................................... 51
Key Observations: ................................................................................................................................................. 52
Conclusion: ............................................................................................................................................................ 52
Hoare Partition in Quicksort ............................................................................................................................... 52
Hoare Partition Algorithm ................................................................................................................................... 52
Hoare Partition Algorithm Implementation in C++ .......................................................................................... 53
Output: ................................................................................................................................................................... 54
Time and Space Complexity of Hoare Partition ................................................................................................ 54
Advantages and Disadvantages of Hoare Partition ........................................................................................... 54
Summary ................................................................................................................................................................ 54
QuickSort: A Divide and Conquer Algorithm ................................................................................................... 54
Steps in QuickSort: ............................................................................................................................................... 55
Partitioning Process: ............................................................................................................................................. 55
QuickSort Algorithm (Recursive): ...................................................................................................................... 55
Example Walkthrough: ........................................................................................................................................ 56
Time Complexity Analysis: .................................................................................................................................. 56
Space Complexity:................................................................................................................................................. 57
Advantages of QuickSort: .................................................................................................................................... 57
Disadvantages of QuickSort:................................................................................................................................ 57
Conclusion: ............................................................................................................................................................ 57
QuickSort Analysis Overview .............................................................................................................................. 57
Is QuickSort Stable? ............................................................................................................................................. 57
Is QuickSort In-place? .......................................................................................................................................... 57
What is 3-Way QuickSort? .................................................................................................................................. 58
How to Implement QuickSort for Linked Lists? ............................................................................................... 58
Can We Implement QuickSort Iteratively? ........................................................................................................ 58
Why QuickSort is Preferred Over MergeSort for Sorting Arrays? ................................................................. 58
Why MergeSort is Preferred Over QuickSort for Linked Lists? ..................................................................... 59
How to Optimize QuickSort for O(log n) Extra Space? .................................................................................... 59
Advantages of QuickSort...................................................................................................................................... 59
Disadvantages of QuickSort ................................................................................................................................. 59
Time Complexity Analysis of QuickSort............................................................................................................. 59
Summary of QuickSort ......................................................................................................................................... 60
Tail Call Elimination in QuickSort ..................................................................................................................... 60
What is Tail Recursion? ....................................................................................................................................... 60
Example of Tail Recursion ................................................................................................................................... 60
Tail Recursion in QuickSort ................................................................................................................................ 61
Explanation of Tail Call Elimination in QuickSort ........................................................................................... 62
Why Tail Call Elimination is Beneficial .............................................................................................................. 62
Function Stack Frame Management in Tail Call Elimination .......................................................................... 62
Key Benefits of Tail Call Elimination.................................................................................................................. 62
Conclusion ............................................................................................................................................................. 63
Method 1: Simple Sorting..................................................................................................................................... 63
Method 2: Using a Min Heap (HeapSelect) ........................................................................................................ 64
Comparing the Methods:...................................................................................................................................... 65
Problem: Minimum Difference in an Array ....................................................................................................... 66
Naive Approach ..................................................................................................................................................... 66
Efficient Approach ................................................................................................................................................ 67
Explanation of the Efficient Approach: .............................................................................................................. 68
Summary: .............................................................................................................................................................. 68
Sorting an Array with Two Types of Elements (0s and 1s) ............................................................................... 68
Approach ............................................................................................................................................................... 68
Time Complexity: .................................................................................................................................................. 68
Auxiliary Space: .................................................................................................................................................... 69
Implementation (C++): ......................................................................................................................................... 69
Explanation: .......................................................................................................................................................... 69
Example Run: ........................................................................................................................................................ 69
Output: ................................................................................................................................................................... 70
Summary: .............................................................................................................................................................. 70
Problem: Sort an Array with 0s, 1s, and 2s ........................................................................................................ 70
Approach 1: Dutch National Flag Algorithm (Single Pass) .............................................................................. 70
Approach 2: Counting Sort Method.................................................................................................................... 71
Summary: .............................................................................................................................................................. 73
Problem: Meeting the Maximum Guests in a Party .......................................................................................... 73
Approach: .............................................................................................................................................................. 73
C++ Code: .............................................................................................................................................................. 73
Explanation: .......................................................................................................................................................... 74
Example Run: ........................................................................................................................................................ 74
Output: ................................................................................................................................................................... 75
Time Complexity: .................................................................................................................................................. 75
Method 2: Using an Auxiliary Array (O(max time)) ......................................................................................... 75
C++ Code for Auxiliary Array Approach: ......................................................................................................... 75
Time Complexity: .................................................................................................................................................. 76
Conclusion: ............................................................................................................................................................ 76
Cycle Sort ............................................................................................................................................................... 76
Counting Sort ........................................................................................................................................................ 78
Heap Sort ............................................................................................................................................................... 80
What is a Binary Heap?........................................................................................................................................ 80
Array-based Representation of a Binary Heap .................................................................................................. 81
Heap Sort Algorithm ............................................................................................................................................ 81
Heapify Procedure ................................................................................................................................................ 81
Heap Sort Algorithm for Sorting in Ascending Order ...................................................................................... 81
Step-by-Step Example: ......................................................................................................................................... 81
C++ Code Implementation for Heap Sort........................................................................................................... 82
Explanation of the Code: ...................................................................................................................................... 83
Output Example: ................................................................................................................................................... 83
Time Complexity: .................................................................................................................................................. 83
Space Complexity:................................................................................................................................................. 83
Conclusion: ............................................................................................................................................................ 83
Radix Sort .............................................................................................................................................................. 84
Radix Sort Algorithm ........................................................................................................................................... 84
Time Complexity of Radix Sort: .......................................................................................................................... 85
Applications of Radix Sort: .................................................................................................................................. 85
How Radix Sort Works: ....................................................................................................................................... 85
C++ Implementation of Radix Sort: .................................................................................................................... 86
Complexity Analysis of Radix Sort: .................................................................................................................... 87
Bucket Sort ............................................................................................................................................................ 87
Bucket Sort Algorithm.......................................................................................................................................... 87
Algorithm Steps ..................................................................................................................................................... 88
Time Complexity ................................................................................................................................................... 88
Space Complexity .................................................................................................................................................. 88
Example ................................................................................................................................................................. 88
C++ Implementation of Bucket Sort ................................................................................................................... 89
Output: ................................................................................................................................................................... 89
Key Points to Remember:..................................................................................................................................... 89
Applications: .......................................................................................................................................................... 90
Sorting in C++ STL

The C++ Standard Template Library (STL) provides a built-in function sort() that allows sorting of arrays
or vectors (containers with random access).

Syntax for Sorting an Array:

sort(arr, arr + n);

Where:

• arr is the name or base address of the array.

• n is the size of the array.

Syntax for Sorting a Vector:

sort([Link](), [Link]());

Where:

• vec is the name of the vector.

Example: Sorting with sort()

Below is a C++ program demonstrating the default behavior of the sort() function:

// C++ program to demonstrate default behavior of sort() in STL.

#include <bits/stdc++.h>
using namespace std;

int main() {
// Sorting Array
int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
int n = sizeof(arr) / sizeof(arr[0]);

sort(arr, arr + n); // Sorting the array in ascending order

cout << "Array after sorting is: \n";

for (int i = 0; i < n; ++i)
cout << arr[i] << " ";

// Sorting Vector
vector<int> vec = {1, 2, 4, 5, 3};

sort([Link](), [Link]()); // Sorting the vector in ascending order

cout << "\nVector after sorting is: \n";

for (int i = 0; i < [Link](); ++i)
cout << vec[i] << " ";

return 0;
}

Output:

Array after sorting is:

0 1 2 3 4 5 6 7 8 9
Vector after sorting is:
1 2 3 4 5

By default, the sort() function arranges the elements in ascending order.

Sorting in Descending Order

To sort in descending order, you can pass a third parameter to the sort() function. This parameter allows
you to specify the order in which elements should be sorted. You can use the greater<type>() function to
achieve this, which compares elements in such a way that larger elements are placed first.

Example: Sorting in Descending Order

// C++ program to demonstrate sorting in descending order

#include <bits/stdc++.h>
using namespace std;

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

sort(arr, arr + n, greater<int>()); // Sorting in descending order

cout << "Array after sorting: \n";

for (int i = 0; i < n; ++i)
cout << arr[i] << " ";

return 0;
}

Output:

Array after sorting:

9 8 7 6 5 4 3 2 1 0

Sorting with a Custom Order (Using Comparator Function)

Sometimes, you might need to sort elements according to a custom order. In such cases, you can write your
own comparator function and pass it as a third parameter to the sort() function.

Example: Sorting with a Custom Comparator

// C++ program to demonstrate STL sort() with custom comparator

#include <bits/stdc++.h>
using namespace std;

// A structure to represent an interval

struct Interval {
int start, end;
};

// Comparator function to compare intervals by start time

bool compareInterval(Interval i1, Interval i2) {
return ([Link] < [Link]);
}

int main() {
 // Array of intervals
Interval arr[] = {{6, 8}, {1, 9}, {2, 4}, {4, 7}};
int n = sizeof(arr) / sizeof(arr[0]);

// Sort intervals based on start time

sort(arr, arr + n, compareInterval);

cout << "Intervals sorted by start time: \n";

for (int i = 0; i < n; ++i)
cout << "[" << arr[i].start << "," << arr[i].end << "] ";

return 0;
}

Output:

Intervals sorted by start time:

[1,9] [2,4] [4,7] [6,8]

Conclusion

• The sort() function in C++ STL is a versatile tool to sort arrays and vectors in both ascending and
descending order.
• It can also be customized to sort elements based on custom conditions, using comparator functions.

This makes the sort() function a powerful and flexible utility for handling sorted data in C++.

Sorting using Built-in Methods in Java

[Link]() Method

The [Link]() method is part of Java's Arrays class and is used to sort an array in ascending or
descending order, or any other order specified by the user.

Syntax:

public static void sort(int[] arr, int from_Index, int to_Index)

• arr: The array to be sorted.

• from_Index: The starting index (inclusive) of the subarray to be sorted.
• to_Index: The ending index (exclusive) of the subarray to be sorted.

Examples of Sorting Arrays

1. Sorting an Array of Integers in Ascending Order

// A sample Java program to sort an array of integers

// using [Link](). It by default sorts in ascending order
import [Link];

public class SortExample {

public static void main(String[] args) {
// Array contains 8 elements
int[] arr = {13, 7, 6, 45, 21, 9, 101, 102};

// Sorting array in ascending order

 [Link](arr);

// Output the sorted array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [6, 7, 9, 13, 21, 45, 101, 102]

2. Sorting a Subarray

// A sample Java program to sort a subarray

// using [Link]().
import [Link];

public class SortExample {

public static void main(String[] args) {
// Array contains 8 elements
int[] arr = {13, 7, 6, 45, 21, 9, 2, 100};

// Sorting subarray from index 1 to 4

[Link](arr, 1, 5); // Only sorts the subarray {7, 6, 45, 21}

// Output the sorted array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [13, 6, 7, 21, 45, 9, 2, 100]

3. Sorting in Descending Order

// A sample Java program to sort an array in descending order

// using [Link]().
import [Link];
import [Link];

public class SortExample {

public static void main(String[] args) {
// Using Integer[] instead of int[] because [Link]() doesn't
work with primitive types.
Integer[] arr = {13, 7, 6, 45, 21, 9, 2, 100};

// Sorting array in descending order

[Link](arr, [Link]());

// Output the sorted array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [100, 45, 21, 13, 9, 7, 6, 2]

4. Sorting an Array of Strings

// A sample Java program to sort an array of strings

// in ascending and descending orders using [Link]().
import [Link];
import [Link];

public class SortExample {

public static void main(String[] args) {
String arr[] = {
"[Link]",
"[Link]",
"[Link]"
};

// Sorting array in ascending order

[Link](arr);
[Link]("Modified arr[] : \n%s\n\n", [Link](arr));

// Sorting array in descending order

[Link](arr, [Link]());
[Link]("Modified arr[] : \n%s\n\n", [Link](arr));
}
}

Output:

Modified arr[] :
[[Link], [Link], [Link]]

Modified arr[] :
[[Link], [Link], [Link]]

5. Sorting According to User-Defined Criteria Using Comparator

// Java program to demonstrate the working of Comparator interface

import [Link].*;

class Point {
int x, y;

Point(int i, int j) {
x = i;
y = j;
}
}

class MySort implements Comparator<Point> {

// Sorting points in ascending order based on x-coordinate
public int compare(Point a, Point b) {
return a.x - b.x;
}
}

public class Main {

public static void main(String[] args) {
Point[] arr = {
new Point(10, 20),
new Point(3, 12),
new Point(5, 7)
};

// Sorting based on custom comparator

[Link](arr, new MySort());

// Output sorted array

for (Point p : arr) {
[Link](p.x + " " + p.y);
}
}
}

Output:

3 12
5 7
10 20

[Link]() Method

The [Link]() method is used to sort elements in a list of collections in ascending order. It
works similarly to [Link]() but is more versatile because it can also sort other collection types like
ArrayList, LinkedList, Queue, etc.

Syntax:

public static void sort(List myList)

• myList: A List type object that you want to sort.

This method does not return anything; it sorts the list in place.

Examples of Sorting Collections

1. Sorting an ArrayList in Ascending Order

// Java program to demonstrate working of [Link]()

import [Link].*;

public class CollectionSorting {

public static void main(String[] args) {
ArrayList<String> al = new ArrayList<>();
[Link]("Geeks For Geeks");
[Link]("Friends");
[Link]("Dear");
[Link]("Is");
[Link]("Superb");

// Sorting ArrayList in ascending order

[Link](al);

// Output the sorted list

[Link]("List after sorting: " + al);
}
}

Output:

List after sorting: [Dear, Friends, Geeks For Geeks, Is, Superb]

2. Sorting an ArrayList in Descending Order

// Java program to demonstrate working of [Link]()

// to sort in descending order.
import [Link].*;

public class CollectionSorting {

public static void main(String[] args) {
ArrayList<String> al = new ArrayList<>();
[Link]("Geeks For Geeks");
 [Link]("Friends");
[Link]("Dear");
[Link]("Is");
[Link]("Superb");

// Sorting ArrayList in descending order

[Link](al, [Link]());

// Output the sorted list

[Link]("List after sorting: " + al);
}
}

Output:

List after sorting: [Superb, Is, Geeks For Geeks, Friends, Dear]

3. Sorting an ArrayList According to User-Defined Criteria Using Comparator

// Java program to demonstrate the use of Comparator interface

// and [Link]() for sorting according to custom criteria.
import [Link].*;

class Student {
int rollno;
String name, address;

// Constructor
public Student(int rollno, String name, String address) {
[Link] = rollno;
[Link] = name;
[Link] = address;
}

// Used to print student details

public String toString() {
return [Link] + " " + [Link] + " " + [Link];
}
}

public class Main {

public static void main(String[] args) {
ArrayList<Student> students = new ArrayList<>();
[Link](new Student(111, "bbbb", "London"));
[Link](new Student(131, "aaaa", "NYC"));
[Link](new Student(121, "cccc", "Jaipur"));

// Sorting students based on roll number

[Link](students, new Comparator<Student>() {
public int compare(Student s1, Student s2) {
return [Link] - [Link];
}
});

// Output the sorted list

[Link]("Sorted by rollno:");
for (Student student : students) {
[Link](student);
}
}
}

Output:

Sorted by rollno:
111 bbbb London
121 cccc Jaipur
131 aaaa NYC

Sorting using Built-in Methods in Java

Java provides powerful built-in methods for sorting arrays and collections. The two primary methods for
sorting are [Link]() and [Link](). Both can be used to sort arrays and collections in
various ways based on your requirements.

1. [Link]()

The [Link]() method is a built-in method in the Arrays class used to sort arrays in ascending,
descending, or any other order as specified by the user.

Syntax:

public static void sort(int[] arr, int from_Index, int to_Index)

Where:

• arr is the array to be sorted.

• from_Index is the index of the first element, inclusive, to be sorted.
• to_Index is the index of the last element, exclusive, to be sorted.

Example 1: Sorting an Array in Ascending Order

import [Link];

public class SortExample {

public static void main(String[] args) {
// Array of integers
int[] arr = {13, 7, 6, 45, 21, 9, 101, 102};

// Sorting the array in ascending order

[Link](arr);

// Printing the sorted array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [6, 7, 9, 13, 21, 45, 101, 102]

Example 2: Sorting a Subarray

import [Link];

public class SortExample {

public static void main(String[] args) {
 int[] arr = {13, 7, 6, 45, 21, 9, 2, 100};

// Sorting the subarray from index 1 to 4 (inclusive)

[Link](arr, 1, 5);

// Printing the modified array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [13, 6, 7, 21, 45, 9, 2, 100]

Example 3: Sorting in Descending Order

import [Link];
import [Link];

public class SortExample {

public static void main(String[] args) {
Integer[] arr = {13, 7, 6, 45, 21, 9, 2, 100};

// Sorting the array in descending order

[Link](arr, [Link]());

// Printing the sorted array

[Link]("Modified arr[] : %s", [Link](arr));
}
}

Output:

Modified arr[] : [100, 45, 21, 13, 9, 7, 6, 2]

Example 4: Sorting Strings in Alphabetical Order

import [Link];
import [Link];

public class SortExample {

public static void main(String[] args) {
String[] arr = {
"[Link]",
"[Link]",
"[Link]"
};

// Sorting in ascending order

[Link](arr);
[Link]("Modified arr[] : \n%s\n\n", [Link](arr));

// Sorting in descending order

[Link](arr, [Link]());
[Link]("Modified arr[] : \n%s\n\n", [Link](arr));
}
}

Output:

Modified arr[] :
[[Link], [Link], [Link]]
Modified arr[] :
[[Link], [Link], [Link]]

Example 5: Sorting Using a Custom Comparator

You can use the Comparator interface to define custom sorting logic. Here's an example:

import [Link].*;

class Point {
int x, y;
Point(int i, int j) { x = i; y = j; }
}

class MySort implements Comparator<Point> {

public int compare(Point a, Point b) {
return a.x - b.x; // Sorting in ascending order of x
}
}

public class Main {

public static void main(String[] args) {
Point[] arr = {
new Point(10, 20),
new Point(3, 12),
new Point(5, 7)
};

// Sorting the array using the custom comparator

[Link](arr, new MySort());

// Printing the sorted array

for (Point p : arr) {
[Link](p.x + " " + p.y);
}
}
}

Output:

3 12
5 7
10 20

2. [Link]()

The [Link]() method is used to sort elements in a List in ascending order. It works similarly
to [Link](), but is more flexible because it works with all collection types, such as ArrayList,
LinkedList, and Queue.

Syntax:

public static void sort(List<T> myList)

Where:

• myList is the List to be sorted.

This method doesn’t return anything; it modifies the list in-place.

Example 1: Sorting an ArrayList in Ascending Order

import [Link].*;

public class CollectionSorting {

public static void main(String[] args) {
// Creating a list of strings
ArrayList<String> al = new ArrayList<>();
[Link]("Geeks For Geeks");
[Link]("Friends");
[Link]("Dear");
[Link]("Is");
[Link]("Superb");

// Sorting the list in ascending order

[Link](al);

// Printing the sorted list

[Link]("List after [Link]() :\n" + al);
}
}

Output:

List after [Link]() :

[Dear, Friends, Geeks For Geeks, Is, Superb]

Example 2: Sorting in Descending Order

import [Link].*;

public class CollectionSorting {

public static void main(String[] args) {
ArrayList<String> al = new ArrayList<>();
[Link]("Geeks For Geeks");
[Link]("Friends");
[Link]("Dear");
[Link]("Is");
[Link]("Superb");

// Sorting the list in descending order

[Link](al, [Link]());

// Printing the sorted list

[Link]("List after [Link]() :\n" + al);
}
}

Output:

List after [Link]() :

[Superb, Is, Geeks For Geeks, Friends, Dear]

Example 3: Sorting an ArrayList According to User-Defined Criteria

You can also use the Comparator interface to sort elements based on custom criteria:
import [Link].*;

class Student {
int rollno;
String name, address;

public Student(int rollno, String name, String address) {

[Link] = rollno;
[Link] = name;
[Link] = address;
}

public String toString() {

return [Link] + " " + [Link] + " " + [Link];
}
}

public class Main {

public static void main(String[] args) {
ArrayList<Student> students = new ArrayList<>();
[Link](new Student(111, "bbbb", "London"));
[Link](new Student(131, "aaaa", "NYC"));
[Link](new Student(121, "cccc", "Jaipur"));

// Sorting by roll number

[Link](students, new Comparator<Student>() {
public int compare(Student s1, Student s2) {
return [Link] - [Link];
}
});

// Printing the sorted list

[Link]("Sorted by rollno:");
for (Student s : students) {
[Link](s);
}
}
}

Output:

Sorted by rollno:
111 bbbb London
121 cccc Jaipur
131 aaaa NYC

Conclusion

• [Link]() is used for sorting arrays in Java and provides several overloads to sort arrays,
subarrays, and arrays in descending order or according to custom comparators.
• [Link]() is ideal for sorting List types and offers flexible sorting options, including
sorting in descending order or using a custom comparator.

Both methods are essential tools for sorting in Java, with the choice of method depending on the type of data
structure you are working with.

This is a comprehensive overview of sorting in Java using the [Link]() method, covering both
primitive and non-primitive types. Let me summarize the key points:
1. Sorting Arrays of Primitive Types

You can use [Link]() to sort arrays containing primitive types such as int, char, double, etc.

Example (sorting integers and characters):

import [Link];

public class GfG {

public static void main(String[] args) {
int[] arr1 = { 5, 20, 12, 30 };
char[] arr2 = { 'B', 'B', 'A', 'C', 'A' };

[Link](arr1);
[Link]([Link](arr1));

[Link](arr2);
[Link]([Link](arr2));
}
}

Output:

[5, 12, 20, 30]

[A, A, B, B, C]

2. Sorting a Subarray

You can sort a specific portion of an array by specifying the range with the from_Index and to_Index
parameters.

Example (sorting a subarray):

import [Link];

public class GfG {

public static void main(String[] args) {
int[] arr = { 5, 30, 20, 10, 8 };
[Link](arr, 1, 4);
[Link]([Link](arr));
}
}

Output:

[5, 10, 20, 30, 8]

3. Sorting Non-Primitive Types Using Comparable Interface

When sorting non-primitive types (e.g., objects), the class needs to implement the Comparable interface.

Example (sorting by x coordinate of Point objects):

import [Link];

class Point implements Comparable<Point> {

int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
 }

public int compareTo(Point P) {

return this.x - P.x;
}
}

public class Test {

public static void main(String[] args) {
Point arr[] = { new Point(10, 20), new Point(3, 12), new Point(5, 7) };
[Link](arr);
for (Point p : arr) {
[Link](p.x + " " + p.y);
}
}
}

Output:

3 12
5 7
10 20

4. Sorting Using Comparator Interface

You can use a Comparator for custom sorting logic, allowing flexibility without modifying the original
class.

Example (sorting Point objects using a custom comparator):

import [Link].*;

class Point {
int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
}
}

class MyCmp implements Comparator<Point> {

public int compare(Point p1, Point p2) {
return p1.x - p2.x;
}
}

public class GfG {

public static void main(String[] args) {
Point arr[] = { new Point(10, 20), new Point(3, 12), new Point(5, 7) };
[Link](arr, new MyCmp());
for (Point p : arr) {
[Link](p.x + " " + p.y);
}
}
}

Output:

3 12
5 7
10 20
5. Reversing Order (Descending) with Wrapper Classes

You can reverse the sorting order using [Link](). This is applicable only to wrapper
classes (e.g., Integer, Double).

Example (sorting integers in descending order):

import [Link].*;

public class GfG {

public static void main(String[] args) {
Integer[] arr = { 5, 20, 10, 12 };
[Link](arr, [Link]());
[Link]([Link](arr));
}
}

Output:

[20, 12, 10, 5]

6. Sorting Integers Based on Even and Odd Numbers

You can sort an array such that even numbers come before odd numbers, using a custom Comparator.

Example (sorting by even and odd numbers):

import [Link].*;

class MyCmp implements Comparator<Integer> {

public int compare(Integer a, Integer b) {
return a % 2 - b % 2; // Even numbers come before odd
}
}

public class GfG {

public static void main(String[] args) {
Integer[] arr = { 5, 20, 10, 3, 12 };
[Link](arr, new MyCmp());
[Link]([Link](arr));
}
}

Output:

[20, 10, 12, 5, 3]

Key Notes:

• Primitive types are sorted in their natural order (e.g., numerical order for integers, lexicographical
order for characters) and do not require a comparator.
• Non-primitive types (objects) require either the Comparable interface or a Comparator for custom
sorting.
• [Link]() works for sorting arrays, while [Link]() is used for collections like
ArrayList.

This covers the basics and some advanced usages of [Link]() in Java! Let me know if you need
further clarification on any part.
[Link]() in Java
The [Link]() method is a part of the [Link] class. It is used to
sort the elements in a specified collection that implements the List interface, in ascending order. This
method is quite similar to [Link](), but more versatile since it can sort collections such as
ArrayList, LinkedList, and other List implementations, unlike [Link](), which is specifically for
arrays.

Example 1: Basic Sorting and Reverse Sorting

Code:
import [Link].*;

public class GfG {

public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
[Link](10);
[Link](5);
[Link](20);

// List is sorted in the natural order

[Link](list);
[Link](list); // Output: [5, 10, 20]

// Sorting the list in reverse order

[Link](list, [Link]());
[Link](list); // Output: [20, 10, 5]
}
}

Output:
[5, 10, 20]
[20, 10, 5]

Explanation:

• First Call: The [Link]() method sorts the list in ascending order (natural order).
• Second Call: The [Link]() function reverses the order, sorting the list in
descending order.

Note:

• Wrapper classes like Integer, Character, etc., implement the Comparable interface.
• The [Link]() method internally uses the compareTo() function to create a
comparator that helps reverse the sorting order.

Example 2: Sorting Using the Comparable Interface

The Comparable interface allows you to define a natural order for objects that you want to sort. This is
particularly useful when working with custom objects, like the Point class.
Code:
import [Link].*;

class Point implements Comparable<Point> {

int x, y;

Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public int compareTo(Point p) {
return this.x - p.x;
}
}

public class GfG {

public static void main(String[] args) {
List<Point> list = new ArrayList<Point>();
[Link](new Point(5, 10));
[Link](new Point(2, 20));
[Link](new Point(10, 30));

// List is sorted in the natural order based on x-coordinate

[Link](list);
for (Point p : list) {
[Link](p.x + " " + p.y);
}
}
}

Output:
2 20
5 10
10 30

Explanation:

• The Point class implements the Comparable interface and overrides the compareTo() method to
sort points by their x-coordinate.
• The [Link]() method uses the natural order defined by the compareTo() method.

Example 3: Sorting Using the Comparator Interface

The Comparator interface allows you to define custom sorting logic without modifying the object's class.
This is useful when you need to sort objects based on different criteria or multiple fields.

Code:
import [Link].*;

class Point {
int x, y;

Point(int x, int y) {
this.x = x;
 this.y = y;
}
}

class MyCmp implements Comparator<Point> {

@Override
public int compare(Point p1, Point p2) {
return p1.x - p2.x;
}
}

public class GfG {

public static void main(String[] args) {
List<Point> list = new ArrayList<Point>();
[Link](new Point(5, 10));
[Link](new Point(2, 20));
[Link](new Point(10, 30));

// Sorting using custom comparator based on x-coordinate

[Link](list, new MyCmp());
for (Point p : list) {
[Link](p.x + " " + p.y);
}
}
}

Output:
2 20
5 10
10 30

Explanation:

• The Point class does not implement Comparable, but the MyCmp class implements Comparator,
defining how Point objects are compared (based on the x-coordinate).

[Link]() vs [Link]()
Both [Link]() and [Link]() are used for sorting, but they differ in several ways:

• [Link]():
o Works with arrays.
o Can handle both primitive types (like int, char) and object types.
• [Link]():
o Works only with collections that implement the List interface (e.g., ArrayList,
LinkedList).
o Cannot directly handle arrays or primitive types.

Conclusion:

• [Link]() is a versatile method for sorting collections that implement the List interface.
• You can use it with custom sorting logic through the Comparable or Comparator interfaces, giving
you flexibility in defining how your objects should be ordered.
Here is the beautified and formatted version of your article:

Stability in Sorting Algorithms

Stability is essential when dealing with key-value pairs that may have duplicate keys (e.g., people's names
as keys with their respective details as values) and when we wish to sort these objects by their keys.

What is a stable sorting algorithm?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in the sorted
output as they appear in the input data set.

Formally, stability may be defined as how the algorithm treats equal elements. Let A[]A[] be an array, and
let '<' be a strict weak ordering on the elements of A[]A[]. A sorting algorithm is stable if:

If A[i]≡A[j], then the relative order of A[i] and A[j] is preserved.\text{If } A[i] \equiv A[j], \text{ then the
relative order of } A[i] \text{ and } A[j] \text{ is preserved.}

Informally, stability means that equivalent elements retain their relative positions after sorting.

Example of stable sorting

Do we care for simple arrays like the array of integers?

When equal elements are indistinguishable (e.g., with integers or more generally, any data where the entire
element is the key), stability is not an issue. Similarly, stability is not a concern when all keys are different.

Where are stable sorting algorithms useful?

Consider the following dataset of Student Names and their respective class sections:

Name Section
Alice A
Bob B
Charlie A
David B
Eric A

If we sort this data according to name only, the resulting dataset is unlikely to be grouped according to
sections as well.

So, we might need to sort again to obtain the list of students by sections. However, if the sorting algorithm is
unstable, we might get a result like this:

Name Section
Alice A
Charlie A
Eric A
Bob B
Name Section
David B

In the above case, the dataset is sorted according to sections, but not according to names. In the name-
sorted dataset, the tuple (Alice, A) was before (Eric, A). Since the sorting algorithm is not stable, the
relative order is lost.

On the other hand, if we used a stable sorting algorithm, the result would be:

Name Section
Alice A
Charlie A
Eric A
Bob B
David B

Here, the relative order between different tuples is maintained. This is the benefit of using a stable sorting
algorithm.

Which sorting algorithms are stable?

Some sorting algorithms are stable by nature, such as:

• Bubble Sort
• Insertion Sort
• Merge Sort
• Counting Sort

How do stable sorting algorithms maintain stability?

• Merge Sort and Insertion Sort are comparison-based stable sorts. They maintain stability by
ensuring that element A[i]A[i] comes before A[j]A[j] if and only if A[i]≡A[j]A[i] \equiv A[j] (i.e.,
the relative order is preserved if A[i]A[i] comes before A[j]A[j]).
• Counting Sort, a non-comparison-based stable sort, maintains stability by filling the sorted array in
reverse order so that elements with equivalent keys maintain their relative positions.
• Radix Sort depends on another sorting algorithm, with the requirement that the other sort should be
stable.

Which sorting algorithms are unstable?

Sorting algorithms like Quick Sort and Heap Sort are generally considered unstable. However, these can
be made stable by taking the positions of the elements into account. This adjustment may slightly affect the
performance and require extra space, but it is possible.

Can we make any sorting algorithm stable?

Yes, any given sorting algorithm that is not stable can be modified to be stable. There are algorithm-specific
ways to achieve this. In general, any comparison-based sorting algorithm that is not stable by nature can be
modified to be stable by changing the key comparison operation. This modified comparison will consider
the position of the elements when comparing keys with equal values.
This version has been cleaned up for readability and structure. If you need any further adjustments, feel free
to ask!

Here’s a beautified version of your article on Bubble Sort with improved formatting and clear sections for
better readability:

Bubble Sort Algorithm

Bubble Sort is one of the simplest sorting algorithms. It repeatedly compares adjacent elements in a list and
swaps them if they are in the wrong order. The algorithm is called "Bubble Sort" because smaller elements
bubble to the top of the list with each pass through the data.

Despite its simplicity, Bubble Sort is not suitable for large data sets due to its relatively high time
complexity in both the average and worst-case scenarios.

How Bubble Sort Works

Consider the following example:

Array: arr[] = {5, 1, 4, 2, 8}

First Pass:

• Step 1: Compare the first two elements 5 and 1. Since 5 > 1, swap them.
• (5 1 4 2 8) --> (1 5 4 2 8)
• Step 2: Compare 5 and 4. Since 5 > 4, swap them.
• (1 5 4 2 8) --> (1 4 5 2 8)
• Step 3: Compare 5 and 2. Since 5 > 2, swap them.
• (1 4 5 2 8) --> (1 4 2 5 8)
• Step 4: Compare 5 and 8. Since 5 < 8, no swap is needed.
• (1 4 2 5 8)

At the end of the first pass, the largest element (8) has "bubbled" to the end of the array.

Second Pass:

• Step 1: Compare 1 and 4. Since 1 < 4, no swap is needed.

• (1 4 2 5 8)
• Step 2: Compare 4 and 2. Since 4 > 2, swap them.
• (1 4 2 5 8) --> (1 2 4 5 8)
• Step 3: Compare 4 and 5. Since 4 < 5, no swap is needed.
• (1 2 4 5 8)
• Step 4: Compare 5 and 8. Since 5 < 8, no swap is needed.
• (1 2 4 5 8)

At the end of the second pass, the second-largest element (5) is in its correct position.

Third Pass:
Now, the array is already sorted, but the algorithm needs to perform one more pass without any swaps to
confirm the array is fully sorted.

• Step 1: Compare 1 and 2. Since 1 < 2, no swap is needed.

• (1 2 4 5 8)
• Step 2: Compare 2 and 4. Since 2 < 4, no swap is needed.
• (1 2 4 5 8)
• Step 3: Compare 4 and 5. Since 4 < 5, no swap is needed.
• (1 2 4 5 8)
• Step 4: Compare 5 and 8. Since 5 < 8, no swap is needed.
• (1 2 4 5 8)

Since no swaps were made during this pass, the algorithm terminates, confirming the array is sorted.

Illustration of Bubble Sort Process

Here’s a visual representation of how Bubble Sort works:

Initial Array: [5, 1, 4, 2, 8]

Pass 1: [1, 4, 2, 5, 8]
Pass 2: [1, 2, 4, 5, 8]
Pass 3: [1, 2, 4, 5, 8] (no swaps)

C++ Code Implementation of Bubble Sort

Code:
#include <bits/stdc++.h>
using namespace std;

// Function to implement Bubble Sort

void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n - 1; i++) {
// Last i elements are already in place
for (j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}

// Function to print an array

void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

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

cout << "Unsorted Array: ";

printArray(arr, n);
 bubbleSort(arr, n);

cout << "Sorted Array: ";

printArray(arr, n);

return 0;
}

Output:
Unsorted Array: 5 1 4 2 8
Sorted Array: 1 2 4 5 8

Time and Space Complexity

• Time Complexity: O(n^2), where n is the number of elements in the array.
o This is because, in the worst case, the algorithm requires n-1 passes, and each pass requires
comparing and possibly swapping up to n-i-1 elements.
• Space Complexity: O(1).
o The algorithm sorts the array in-place, meaning it does not require any additional storage or
memory allocation beyond the input array.

Conclusion:

• Bubble Sort is a straightforward but inefficient sorting algorithm, particularly for large datasets due
to its quadratic time complexity.
• However, its simplicity makes it an excellent choice for teaching sorting algorithms or for small
datasets where efficiency is not a concern.

Here is the beautified and formatted version of your article on Selection Sort:

Selection Sort
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering
ascending order) from the unsorted part and placing it at the beginning. The algorithm maintains two
subarrays in a given array:

1. The sorted subarray.

2. The unsorted subarray.

In each iteration of the selection sort, the minimum element (considering ascending order) from the unsorted
subarray is picked and moved to the sorted subarray.

Flowchart of the Selection Sort

How Selection Sort Works

Let's consider the following array as an example:
arr[] = {64, 25, 12, 22, 11}

First Pass:

• Traverse the whole array from index 0 to 4.

• Initially, 64 is at the first position. After traversing the entire array, it's clear that 11 is the smallest
value.

Before swap:

64 25 12 22 11

• Replace 64 with 11. After one iteration, 11, which is the smallest value in the array, appears at the
first position of the sorted list.

After swap:

11 25 12 22 64

Second Pass:

• Now, for the second position (where 25 is), traverse the rest of the array.

Before swap:

11 25 12 22 64

• After traversal, we find that 12 is the second smallest value in the array. So, we swap 25 and 12.

After swap:

11 12 25 22 64

Third Pass:

• Now, for the third position (where 25 is), traverse the rest of the array.

Before swap:

11 12 25 22 64

• We find that 22 is the third smallest value and it should appear at the third position. Thus, we swap
25 with 22.

After swap:

11 12 22 25 64

Fourth Pass:

• Similarly, for the fourth position, traverse the rest of the array and find the fourth smallest element.

Before swap:

11 12 22 25 64
 • Since 25 is already in the correct position, no further swap is needed.

Fifth Pass:

• At last, the largest value (64) is already in the last position, completing the sorting process.

Final sorted array:

11 12 22 25 64

Approach:

1. Initialize the minimum value (min_idx) to location 0.

2. Traverse the array to find the minimum element in the unsorted part.
3. If any element smaller than min_idx is found, swap the two elements.
4. Increment min_idx to point to the next element.
5. Repeat until the array is sorted.

C++ Implementation:
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;

// Swap function
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)

{
int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
{
if (arr[j] < arr[min_idx])
min_idx = j;
}
// Swap the found minimum element with the first element
swap(&arr[min_idx], &arr[i]);
}
}

Output:
Sorted array:
11 12 22 25 64

Time and Space Complexity:

• Time Complexity: O(n2)O(n^2), where nn is the number of elements in the input array.
• Space Complexity: O(1)O(1) (as it is an in-place sorting algorithm).
This version has been formatted for better readability and structure. Let me know if you need any further
changes!

Here's the beautified and formatted version of your Insertion Sort article:

Insertion Sort Algorithm

Insertion Sort is a simple and efficient sorting algorithm that works similarly to the way you might sort
playing cards in your hand. The algorithm divides the array into two parts: a sorted part and an unsorted
part. It then takes each element from the unsorted part and places it at its correct position in the sorted part.

Characteristics of Insertion Sort:

• Simplicity: It is one of the simplest sorting algorithms with a straightforward implementation.
• Efficiency for Small Data Sets: It is particularly efficient when dealing with small arrays or when
the data is already partially sorted.
• Adaptive Nature: Insertion sort is adaptive, meaning it performs well when the data is already
partially sorted, reducing the number of comparisons and swaps.

How Insertion Sort Works

Let's go through an example to understand how the Insertion Sort algorithm works.

Array: arr[] = {12, 11, 13, 5, 6}

First Pass:

• Compare the first two elements 12 and 11. Since 12 > 11, they are not in the correct order.
o Swap them.
• (12, 11, 13, 5, 6) --> (11, 12, 13, 5, 6)

Now, 11 is placed in the sorted sub-array {11}.

Second Pass:

• Compare 12 and 13. Since 12 < 13, no swap is needed. The sorted sub-array is now {11, 12}.

Third Pass:

• Compare 13 and 5. Since 13 > 5, swap them.

• (11, 12, 13, 5, 6) --> (11, 12, 5, 13, 6)
• Now compare 12 and 5. Since 12 > 5, swap them.
• (11, 12, 5, 13, 6) --> (11, 5, 12, 13, 6)
• Now compare 11 and 5. Since 11 > 5, swap them.
• (11, 5, 12, 13, 6) --> (5, 11, 12, 13, 6)
Now, the sorted sub-array is {5, 11, 12, 13}.

Fourth Pass:

• Compare 13 and 6. Since 13 > 6, swap them.

• (5, 11, 12, 13, 6) --> (5, 11, 12, 6, 13)
• Now compare 12 and 6. Since 12 > 6, swap them.
• (5, 11, 12, 6, 13) --> (5, 11, 6, 12, 13)
• Now compare 11 and 6. Since 11 > 6, swap them.
• (5, 11, 6, 12, 13) --> (5, 6, 11, 12, 13)

Finally, the array is completely sorted: {5, 6, 11, 12, 13}.

Illustration of Insertion Sort

Here’s a step-by-step illustration of how the array evolves through each pass of Insertion Sort:

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

Pass 1: [11, 12, 13, 5, 6]

Pass 2: [11, 12, 13, 5, 6]
Pass 3: [5, 11, 12, 13, 6]
Pass 4: [5, 6, 11, 12, 13]

Insertion Sort Algorithm

Steps to sort an array of size N in ascending order:

1. Start with the second element arr[1], treating the first element arr[0] as already sorted.
2. Compare the current element (key) with its predecessor.
3. If the key element is smaller than its predecessor, shift the larger elements one position up to make
space for the key element.
4. Insert the key element into the correct position.

C++ Code Implementation of Insertion Sort

Code:
#include <bits/stdc++.h>
using namespace std;

// Function to sort an array using Insertion Sort

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

// Move elements of arr[0..i-1] that are greater than key

// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
 j = j - 1;
}
arr[j + 1] = key;
}
}

// Function to print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}

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

cout << "Unsorted Array: ";

printArray(arr, n);

insertionSort(arr, n);

cout << "Sorted Array: ";

printArray(arr, n);

return 0;
}

Output:
Unsorted Array: 12 11 13 5 6
Sorted Array: 5 6 11 12 13

Time and Space Complexity

• Time Complexity: O(N²)
o The algorithm requires N-1 iterations. In the worst case, each iteration involves comparing
and possibly shifting N-1, N-2, ..., 1 elements.
• Space Complexity: O(1)
o Insertion sort sorts the array in-place, meaning it doesn’t require additional space beyond the
input array.

Conclusion:

• Insertion Sort is an intuitive and simple sorting algorithm that works well for small datasets or
nearly sorted data.
• Its time complexity of O(N²) makes it inefficient for large datasets compared to more advanced
sorting algorithms like Merge Sort or Quick Sort.
• However, it remains a good choice when the data is partially sorted or when simplicity is more
important than performance.

Here is the beautified and formatted version of your article on Merging Two Sorted Arrays:

Merge Two Sorted Arrays

Given two sorted arrays, the task is to merge them into a single sorted array.

Examples:

• Input:
arr1[] = { 1, 3, 4, 5},
arr2[] = {2, 4, 6, 8}
Output:
arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
• Input:
arr1[] = { 5, 8, 9},
arr2[] = {4, 7, 8}
Output:
arr3[] = {4, 5, 7, 8, 8, 9}

Method 1: (Time Complexity: O(n1×n2)O(n1 \times n2), Space Complexity:

O(n1+n2)O(n1 + n2))

1. Create an array arr3[] of size n1+n2n1 + n2.

2. Copy all n1n1 elements of arr1[] to arr3[].
3. Traverse arr2[] and one by one insert its elements into arr3[] in sorted order (like insertion sort).
This step takes O(n1×n2)O(n1 \times n2) time.

Method 2: (Time Complexity: O(n1+n2)O(n1 + n2), Space Complexity: O(n1+n2)O(n1 +

n2))

This method uses the merge function of Merge Sort.

1. Create an array arr3[] of size n1+n2n1 + n2.

2. Simultaneously traverse arr1[] and arr2[].
3. Pick the smaller of the current elements in arr1[] and arr2[], copy it to the next position in
arr3[], and move ahead in the respective array.
4. If there are remaining elements in arr1[] or arr2[], copy them into arr3[].

Below is a dry run of the above approach:

Example:

arr1[] = {1, 3, 5, 7},

arr2[] = {2, 4, 6, 8}

Steps:

1. Compare 1 (from arr1[]) and 2 (from arr2[]), pick the smaller one (1), and move to the next
element in arr1[].
2. Compare 3 (from arr1[]) and 2 (from arr2[]), pick the smaller one (2), and move to the next
element in arr2[].
3. Continue the process until all elements are merged.

C++ Implementation:
#include <bits/stdc++.h>
using namespace std;

void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) {
int i = 0, j = 0, k = 0;
 // Traverse both arrays and merge them into arr3[]
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}

// Copy remaining elements of arr1[]

while (i < n1)
arr3[k++] = arr1[i++];

// Copy remaining elements of arr2[]

while (j < n2)
arr3[k++] = arr2[j++];
}

int main() {
int arr1[] = {1, 3, 5, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);

int arr2[] = {2, 4, 6, 8};

int n2 = sizeof(arr2) / sizeof(arr2[0]);

int arr3[n1 + n2];

mergeArrays(arr1, arr2, n1, n2, arr3);

// Output the merged array

cout << "Array after merging: ";
for (int i = 0; i < n1 + n2; i++)
cout << arr3[i] << " ";

return 0;
}

Java Implementation:
public class MergeArrays {
static void mergeArrays(int[] arr1, int[] arr2, int n1, int n2, int[] arr3) {
int i = 0, j = 0, k = 0;

// Traverse both arrays and merge them into arr3[]

while (i < n1 && j < n2) {
if (arr1[i] < arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}

// Copy remaining elements of arr1[]

while (i < n1)
arr3[k++] = arr1[i++];

// Copy remaining elements of arr2[]

while (j < n2)
arr3[k++] = arr2[j++];
}

public static void main(String[] args) {

int[] arr1 = {1, 3, 5, 7};
int n1 = [Link];

int[] arr2 = {2, 4, 6, 8};

int n2 = [Link];
 int[] arr3 = new int[n1 + n2];

mergeArrays(arr1, arr2, n1, n2, arr3);

// Output the merged array

[Link]("Array after merging: ");
for (int i = 0; i < n1 + n2; i++)
[Link](arr3[i] + " ");
}
}

Output:
Array after merging: 1 2 3 4 5 6 7 8

Time and Space Complexity:

• Time Complexity: O(n1+n2)O(n1 + n2), where n1n1 and n2n2 are the lengths of the two input
arrays.
• Space Complexity: O(n1+n2)O(n1 + n2), as we need an additional array to store the merged
elements.

This version has been structured for easy reading and understanding. Let me know if you'd like further
changes!

Here is the formatted version of your article on Merging Two Sorted Arrays with three different methods:

Merge Function of Merge Sort

Given two sorted arrays, the task is to merge them into a single sorted array.

Examples:

• Input:
arr1[] = { 1, 3, 4, 5},
arr2[] = {2, 4, 6, 8}
Output:
arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}
• Input:
arr1[] = { 5, 8, 9},
arr2[] = {4, 7, 8}
Output:
arr3[] = {4, 5, 7, 8, 8, 9}

Method 1: (Time Complexity: O(n1×n2)O(n1 \times n2), Space Complexity:

O(n1+n2)O(n1 + n2))

1. Create an array arr3[] of size n1+n2n1 + n2.

2. Copy all n1n1 elements from arr1[] to arr3[].
3. Traverse arr2[] and insert its elements one by one into arr3[] in a sorted manner (similar to
insertion sort). This takes O(n1×n2)O(n1 \times n2) time.
Note: This method has been discussed in the implementation of "Merge two sorted arrays with O(1) extra
space".

Method 2: (Time Complexity: O(n1+n2)O(n1 + n2), Space Complexity: O(n1+n2)O(n1 +

n2))

This method uses the Merge function of Merge Sort.

1. Create an array arr3[] of size n1+n2n1 + n2.

2. Simultaneously traverse arr1[] and arr2[].
3. Pick the smaller element from the current elements of arr1[] and arr2[], copy it to the next
position in arr3[], and move to the next element in the corresponding array.
4. If there are any remaining elements in arr1[] or arr2[], copy them into arr3[].

Below is a dry run of this approach:

Example:

arr1[] = {1, 3, 5, 7},

arr2[] = {2, 4, 6, 8}

Steps:

1. Compare 1 (from arr1[]) and 2 (from arr2[]). Pick the smaller one (1), move to the next element
in arr1[].
2. Compare 3 (from arr1[]) and 2 (from arr2[]). Pick the smaller one (2), move to the next element
in arr2[].
3. Continue this process until all elements from both arrays are merged.

C++ Implementation:
#include<iostream>
using namespace std;

// Merge arr1[0..n1-1] and arr2[0..n2-1] into arr3[0..n1+n2-1]

void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[]) {
int i = 0, j = 0, k = 0;

// Traverse both arrays

while (i < n1 && j < n2) {
// If current element of arr1[] is smaller
if (arr1[i] <= arr2[j])
arr3[k++] = arr1[i++];
else
arr3[k++] = arr2[j++];
}

// Copy remaining elements of arr1[] (if any)

while (i < n1)
arr3[k++] = arr1[i++];

// Copy remaining elements of arr2[] (if any)

while (j < n2)
arr3[k++] = arr2[j++];
}
int main() {
int arr1[] = {1, 3, 5, 7};
int n1 = sizeof(arr1) / sizeof(arr1[0]);

int arr2[] = {2, 4, 6, 8};

int n2 = sizeof(arr2) / sizeof(arr2[0]);

int arr3[n1 + n2];

mergeArrays(arr1, arr2, n1, n2, arr3);

// Output the merged array

cout << "Array after merging: ";
for (int i = 0; i < n1 + n2; i++)
cout << arr3[i] << " ";

return 0;
}

Output:
Array after merging: 1 2 3 4 5 6 7 8

Time Complexity:

• Time Complexity: O(n1+n2)O(n1 + n2), where n1n1 and n2n2 are the sizes of the two arrays.
• Auxiliary Space: O(n1+n2)O(n1 + n2), due to the extra space required for arr3[].

Method 3: Using Maps (Time Complexity: O(nlog⁡n+mlog⁡m)O(n \log n + m \log m),

Space Complexity: O(n+m)O(n + m))

In this method, we use a map to store the elements of both arrays. The map automatically sorts the elements
and removes duplicates.

1. Insert elements from both arrays into a map.

2. Print the keys of the map.

Note: The use of TreeMap ensures the sorting of elements, but it removes duplicates by default. If you wish
to retain duplicates, this method will not work.

C++ Implementation:
#include<bits/stdc++.h>
using namespace std;

// Function to merge arrays using map

void mergeArrays(int a[], int b[], int n, int m) {
map<int, bool> mp;

// Inserting values from arr1[] to map

for (int i = 0; i < n; i++)
mp[a[i]] = true;

// Inserting values from arr2[] to map

 for (int i = 0; i < m; i++)
mp[b[i]] = true;

// Printing the merged array (keys of the map)

for (auto i : mp)
cout << [Link] << " ";
}

int main() {
int arr1[] = {1, 3, 5, 7};
int n = sizeof(arr1) / sizeof(arr1[0]);

int arr2[] = {2, 4, 6, 8};

int m = sizeof(arr2) / sizeof(arr2[0]);

mergeArrays(arr1, arr2, n, m);

}

Output:
1 2 3 4 5 6 7 8

Time Complexity:

• Time Complexity: O(nlog⁡n+mlog⁡m)O(n \log n + m \log m), due to the sorting of elements in
the map.
• Auxiliary Space: O(n+m)O(n + m), for the storage of elements in the map.

Conclusion:

• Method 1 is slower due to the O(n1×n2)O(n1 \times n2) complexity, but it's simpler for small arrays.
• Method 2 is efficient with O(n1+n2)O(n1 + n2) complexity and is the recommended approach for
merging two sorted arrays.
• Method 3 leverages the built-in map structure and is useful when you need automatic sorting and
handling of duplicates.

Choose the method based on the problem requirements and array sizes!

Merge Sort

Merge Sort is a Divide and Conquer algorithm that works by recursively splitting an array into two halves,
sorting each half, and then merging the sorted halves back together. The merge() function is a key
component, responsible for merging two sorted sub-arrays into a single sorted array.

Steps of Merge Sort

1. Divide the Array:
o Find the middle index m = (l + r) / 2 of the array, where l is the starting index and r is
the ending index.
o Recursively split the array into two halves: one from l to m and the other from m + 1 to r.
2. Sort the Two Halves:
o Recursively call mergeSort(arr, l, m) for the first half of the array.
 o
Recursively call mergeSort(arr, m + 1, r) for the second half of the array.
3. Merge the Two Sorted Halves:
o Once the two halves are sorted, merge them using the merge() function to produce the final
sorted array.

Algorithm Diagram (Visual)

Consider the array: {38, 27, 43, 3, 9, 82, 10}

• First Step (Divide):

o The array is split into two halves: {38, 27, 43} and {3, 9, 82, 10}.
• Second Step (Recursion):
o Continue dividing until each subarray has only one element.
• Final Step (Merge):
o The subarrays are merged back together in sorted order.

This recursive division and merging process continues until the entire array is merged back into a fully
sorted array.

Merge Sort Implementation

Here is a C++ implementation of Merge Sort:

// C++ program for Merge Sort

#include <iostream>
using namespace std;

// Merges two subarrays of array[].

// First subarray is arr[begin..mid]
// Second subarray is arr[mid+1..end]
void merge(int array[], int const left, int const mid,
int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;

// Create temporary arrays

auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temporary arrays leftArray[] and rightArray[]

for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

auto indexOfSubArrayOne = 0, // Initial index of first sub-array

indexOfSubArrayTwo = 0, // Initial index of second sub-array
indexOfMergedArray = left; // Initial index of merged sub-array

// Merge the temporary arrays back into the original array

while (indexOfSubArrayOne < subArrayOne && indexOfSubArrayTwo < subArrayTwo) {
if (leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
} else {
 array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}

// Copy the remaining elements of leftArray[], if any

while (indexOfSubArrayOne < subArrayOne) {
array[indexOfMergedArray] = leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}

// Copy the remaining elements of rightArray[], if any

while (indexOfSubArrayTwo < subArrayTwo) {
array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
}

// Merge Sort function

void mergeSort(int array[], int const left, int const right)
{
if (left >= right) {
return; // base case
}
int mid = (left + right) / 2; // Find the middle index
mergeSort(array, left, mid); // Sort the first half
mergeSort(array, mid + 1, right); // Sort the second half
merge(array, left, mid, right); // Merge the sorted halves
}

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

cout << "Unsorted array: ";

for (int i = 0; i < arr_size; i++) {
cout << arr[i] << " ";
}
cout << endl;

mergeSort(arr, 0, arr_size - 1);

cout << "Sorted array: ";

for (int i = 0; i < arr_size; i++) {
cout << arr[i] << " ";
}
cout << endl;

return 0;
}

Time Complexity Analysis

Merge Sort has a time complexity of Θ(n log n) for all three cases: worst, average, and best. This is because:

1. Recurrence Relation:
o Each time, the array is split into two halves, so there are log n divisions.
o For each level of recursion, O(n) work is done (merging the halves).
2. Total Time Complexity:
 o The recurrence can be expressed as: T(n) = 2T(n/2) + Θ(n)
o Solving this recurrence using the Master Theorem or Recursion Tree Method results in
Θ(n log n).

Thus, Merge Sort is efficient and performs well even with large datasets.

Auxiliary Space Complexity

Merge Sort requires O(n) extra space due to the creation of temporary subarrays during the merging process.
This space is used to store the subarrays before they are merged.

Key Characteristics of Merge Sort

• Stable Sort: The relative order of equal elements is preserved during the sorting process.
• Efficient for Large Data: With a time complexity of O(n log n), Merge Sort is suitable for sorting
large datasets.
• Memory Usage: The space complexity is O(n) due to the need for temporary arrays during merging.

Conclusion

• Merge Sort is a stable, efficient sorting algorithm that performs well even on large datasets, with a
time complexity of O(n log n).
• It requires additional memory for merging subarrays, but this trade-off is often worth it for the
efficiency in sorting.
• While Merge Sort may not be the best choice for small datasets due to its overhead, it excels in
handling large arrays or lists, especially in scenarios like external sorting.

Here's the beautified and formatted version of your Merge Sort Analysis:

Merge Sort Analysis

Merge Sort is a highly efficient and widely used sorting algorithm based on the "divide and conquer"
technique. It divides the input array into two halves, recursively sorts each half, and then merges the two
sorted halves back together. Below is an in-depth analysis of Merge Sort.

How Merge Sort Works

Merge sort recursively divides the array into two halves and sorts each half before merging them back
together. The merging process ensures that the sorted halves are correctly combined into a fully sorted array.
 1. Divide: Split the array into two halves until each subarray contains only one element.
2. Conquer: Recursively sort the two halves.
3. Combine: Merge the sorted halves to produce the sorted array.

Time Complexity of Merge Sort

Merge Sort's time complexity is analyzed by considering the number of passes and the time it takes for each
pass:

• Number of Passes: The algorithm splits the array into two halves on each pass. Since the size of the
array is halved at each step, the number of passes required is O(log n).
• Time per Pass: For each pass, we merge the sorted segments, which takes O(n) time.
• Total Time Complexity: Since there are O(log n) passes, and each pass takes O(n) time, the total
time complexity is O(n log n).

Thus, the Merge Sort algorithm has a time complexity of O(n log n), which is very efficient, particularly
for large datasets.

Applications of Merge Sort

Merge Sort is useful in various scenarios due to its efficient time complexity and stable nature. Some key
applications include:

1. Sorting Linked Lists

Merge Sort is particularly useful for sorting linked lists in O(N log N) time. Unlike arrays, where elements
are stored in contiguous memory locations, linked list nodes are scattered across memory. However, Merge
Sort can still efficiently sort linked lists because it doesn’t require random access. The merging operation in
Merge Sort can be done without additional space when applied to linked lists.

2. External Sorting

Merge Sort is commonly used for external sorting, where the dataset is too large to fit into the computer's
memory. This is common in big data applications. The algorithm’s ability to merge segments efficiently
without requiring random access makes it ideal for sorting large datasets stored on disk.

3. Inversion Count Problem

Merge Sort is also used to solve the inversion count problem, where the goal is to count the number of
pairs of elements in an array where the earlier element is larger than the later one. By modifying the merge
step of the Merge Sort, we can efficiently count the number of inversions in O(n log n) time.

Advantages of Merge Sort

Merge Sort has several advantages, particularly in handling large datasets:

1. Time Complexity
 • O(n log n) time complexity, making it efficient for large datasets, especially when compared to
simpler algorithms like Bubble Sort or Insertion Sort (which have O(n²) time complexity).

2. Stability

• Stable Sorting: Merge Sort is a stable sort, meaning that when two elements have equal values, their
relative order is preserved after sorting.

3. Easy Implementation

• Merge Sort is easy to implement, especially when compared to algorithms like Quick Sort, which
can be more complex due to the use of partitioning.

4. Suitable for External Sorting

• Merge Sort is highly useful in external sorting, where datasets are too large to fit in memory. Since
it requires sequential access to the data, Merge Sort can be efficiently applied to data stored in
external storage like hard disks.

5. Parallelization

• Merge Sort can be parallelized effectively. Since the divide step can be done independently for each
half of the array, Merge Sort can take advantage of multi-core processors to perform sorting in
parallel, speeding up the process.

6. Memory Efficiency

• Merge Sort requires relatively few additional resources (e.g., memory) for its operations, making it
suitable for systems with limited resources, as long as the available memory can accommodate the
temporary subarrays.

Drawbacks of Merge Sort

Despite its advantages, Merge Sort has a few drawbacks:

1. Slower for Small Datasets

• Merge Sort tends to be slower compared to simpler algorithms like Insertion Sort for smaller datasets
due to the overhead involved in the recursive calls and merging process.

2. Extra Memory

• Merge Sort requires O(n) extra space to store the temporary subarrays during the merging process.
This can be a disadvantage in situations where memory usage is a concern.

3. Unnecessary Sorting

• Even if the array is already sorted, Merge Sort will go through the entire process, making it less
efficient for already sorted data.

4. More Complex Implementation

 • The implementation of Merge Sort is more complex compared to simpler algorithms like Bubble
Sort or Insertion Sort, as it involves splitting the array and recursively merging the subarrays.

Recent Articles on Merge Sort

• Coding Practice: Enhance your sorting skills by practicing with Merge Sort and other algorithms.
• Quiz on Merge Sort: Test your understanding of Merge Sort through quizzes.
• Solution to Drawback of Extra Storage: To mitigate the memory overhead, you can use a linked
list instead of an array to avoid the additional space requirement.

Solution for Extra Storage: Use Linked Lists

To solve the issue of extra memory required for Merge Sort, you can use linked lists instead of arrays. This
eliminates the need for extra storage to hold subarrays, as the linked list nodes can be directly merged
without additional space.

Conclusion

• Merge Sort is an efficient and stable sorting algorithm with a time complexity of O(n log n),
making it ideal for large datasets.
• Its ability to be parallelized and used in external sorting applications makes it a popular choice in
real-world scenarios, especially when dealing with large amounts of data stored on disk.
• While Merge Sort may not be the best choice for small datasets due to its overhead and extra
memory requirements, its strengths in handling large and external datasets outweigh these
drawbacks.

Naive Partition in Quicksort

Quicksort is a well-known Divide and Conquer sorting algorithm. The key concept of Quicksort is
partitioning the array into two parts around a pivot element. The algorithm then recursively sorts the two
partitions.

The Naive Partition is one way of partitioning the array in Quicksort. It involves creating a temporary array
to hold elements in three parts:

• Elements smaller than the pivot.

• The pivot element itself.
• Elements greater than the pivot.

Naive Partition Algorithm Steps

1. Create Temporary Array:

o Create a temporary array temp[] of size r - l + 1, where l and r are the left and right
indices of the current array or subarray being partitioned.
2. Choose Pivot:
o Select the last element of the array as the pivot element.
 3. Partitioning the Array:
o Use two loops to rearrange the elements:
▪ First, store all elements smaller than the pivot into the temporary array.
▪ Then, place the pivot in the correct position.
▪ Finally, store all elements greater than the pivot into the temporary array.
4. Update the Original Array:
o After partitioning, copy the contents of the temporary array back into the original array.

Quicksort Using Naive Partition

After partitioning the array using the Naive Partition, the Quicksort algorithm recursively calls itself on the
two partitions (the part smaller than the pivot and the part greater than the pivot).

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

// Function to perform partitioning

int partition(vector<int>& arr, int start, int high) {
// Create a temporary array to store elements during partitioning
vector<int> temp(high - start + 1);

// Choose the pivot element (last element)

int pivot = arr[high];
int index = 0;

// Place elements smaller than the pivot to the left of the pivot
for (int i = start; i <= high; ++i) {
if (arr[i] < pivot) {
temp[index++] = arr[i];
}
}

// Remember the position where pivot should be placed

int position = index;

// Place the pivot in its correct position

temp[index++] = pivot;

// Store elements greater than the pivot to the right of the pivot
for (int i = start; i <= high; ++i) {
if (arr[i] > pivot) {
temp[index++] = arr[i];
}
}

// Copy the temporary array back into the original array

for (int i = 0; i < index; ++i) {
arr[start + i] = temp[i];
}

return position; // Return the partition point

}

// Quicksort function
void quickSort(vector<int>& arr, int start, int high) {
if (start < high) {
// Partition the array and get the partition point
int partitionIndex = partition(arr, start, high);

// Call Quicksort for the left part (less than pivot)

quickSort(arr, start, partitionIndex - 1);
 // Call Quicksort for the right part (greater than pivot)
quickSort(arr, partitionIndex + 1, high);
}
}

int main() {
vector<int> arr = {78, 3, 1, 97, 9798, 2};
int n = [Link]();

cout << "Unsorted array: ";

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

// Call the quickSort function

quickSort(arr, 0, n - 1);

cout << "Sorted array: ";

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

return 0;
}

Output:
Unsorted array: 78 3 1 97 9798 2
Sorted array: 1 2 3 78 97 9798

Time and Space Complexity of Naive Partition

1. Time Complexity:
o Best and Average Case: The partitioning process involves going through all the elements
once to place them in the correct temporary array. This takes O(N) time for each call of the
partition.
o Worst Case: If the array is already sorted, the partitioning takes O(N^2) time as the pivot
does not split the array evenly. This happens when the pivot is always the smallest or largest
element.

Overall Time Complexity:

o
Best/Average Case: O(N log N)
o
Worst Case: O(N^2) (when the pivot does not divide the array well)
2. Space Complexity:
o The Naive Partition uses an additional temporary array of size O(N) to hold the partitioned
elements.

Overall Space Complexity: O(N)

Advantages and Disadvantages of Naive Partition

• Advantages:
o Easy to implement and understand.
 o Maintains the relative order of equal elements.
• Disadvantages:
o Requires O(N) extra space for the temporary array.
o The overall efficiency is dependent on how well the pivot divides the array.

In summary, Naive Partition is simple but not optimal in terms of space. It is a straightforward
implementation but less efficient than other partitioning strategies like Lomuto or Hoare's partition in terms
of space usage.

Lomuto Partition in Quicksort

Quicksort is a Divide and Conquer algorithm that is widely used for sorting elements. The key idea in
quicksort is to choose a pivot element and partition the array into two sub-arrays: one containing elements
smaller than the pivot, and the other containing elements greater than the pivot. The pivot is then placed in
its correct sorted position.

The Lomuto Partition is one of the methods for partitioning the array around the pivot. In Lomuto
partition, the last element of the array is chosen as the pivot. This method has certain trade-offs when
compared to other partitioning schemes like Hoare’s partition.

Three Partition Types in Quicksort:

1. Naive Partition:
o This partition maintains the relative order of elements but requires extra space O(n)O(n).
2. Lomuto Partition:
o The last element is chosen as the pivot.
o After partitioning, the pivot is placed in its correct position, but more comparisons are done,
making it slightly less efficient than Hoare’s partition.
3. Hoare Partition:
o The first element is chosen as the pivot.
o It tends to perform fewer comparisons than Lomuto's partition and is considered more
efficient in practice.

Lomuto Partition Algorithm:

In the Lomuto Partition algorithm, the process works as follows:

1. Select the last element as the pivot.

2. Initialize an index variable i at the starting position of the array.
3. Traverse the array with a pointer j:
o If the element at arr[j] is smaller than or equal to the pivot, increment the index i and swap
arr[i] with arr[j].
4. After traversing the array, swap arr[i + 1] with the pivot (the element at arr[hi]), ensuring that
the pivot is placed in its correct position.
5. Return the index i + 1, which is the new position of the pivot.

Quicksort using Lomuto Partition:

After partitioning the array, Quicksort recursively sorts the two sub-arrays:

• One sub-array contains elements less than the pivot.

 • The other sub-array contains elements greater than the pivot.

Algorithm:

#include <iostream>
using namespace std;

// Lomuto's Partition function

int LomutoPartition(int arr[], int start, int last) {
int pivot = arr[last]; // Choose the last element as pivot
int index = start - 1; // Index for the smaller element
int temp;

for (int i = start; i < last; ++i) {

// If current element is smaller or equal to pivot, swap it
if (arr[i] <= pivot) {
++index;
// Swap the elements
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
}

// Swap the pivot element to the correct position

temp = arr[index + 1];
arr[index + 1] = arr[last];
arr[last] = temp;

return index + 1; // Return the pivot's final position

}

// Quicksort function that uses Lomuto's partition

void QuickSort(int arr[], int start, int last) {
if (start < last) {
int partitionIndex = LomutoPartition(arr, start, last); // Get pivot position
QuickSort(arr, start, partitionIndex - 1); // Recursively sort left subarray
QuickSort(arr, partitionIndex + 1, last); // Recursively sort right subarray
}
}

int main() {
int numbers[] = {4, 5, 6, 4, 2, 1, 5};
int size = sizeof(numbers) / sizeof(numbers[0]);

QuickSort(numbers, 0, size - 1); // Call QuickSort on the entire array

// Output the sorted array

cout << "Sorted Array: ";
for (int i = 0; i < size; i++) {
cout << numbers[i] << " ";
}

return 0;
}

Output:
Sorted Array: 1 2 4 4 5 5 6

Time and Space Complexity:

• Time Complexity:
 o Best Case / Average Case: O(Nlog⁡N)O(N \log N), where NN is the number of elements in
the array.
o Worst Case: O(N2)O(N^2), when the array is already sorted or nearly sorted, because each
partition results in sub-arrays of size 1.
• Space Complexity:
o Space Complexity: O(1)O(1), since the sorting is done in-place and only a constant amount
of extra space is used (for the pivot and index).

Key Observations:

• Unstable Sorting: Lomuto's partitioning scheme is unstable, meaning it does not guarantee the
preservation of the relative order of equal elements.
• Less Efficient on Sorted Arrays: In the worst case, when the array is already sorted, Lomuto’s
partition results in unbalanced partitions, leading to a performance degradation to O(N2)O(N^2).
This is a key limitation of Lomuto’s partition.

Conclusion:

Lomuto's partition algorithm is easy to implement and works well in most cases, but its efficiency can
degrade when the array is already sorted or nearly sorted. To optimize it, we can use techniques like
randomizing the pivot to avoid the worst-case scenario.

Hoare Partition in Quicksort

Quicksort is an efficient Divide and Conquer algorithm that divides the array into smaller subarrays and
sorts them recursively. The Hoare Partition is one of the partitioning methods used in Quicksort, known for
fewer comparisons and better performance than the Lomuto Partition.

In Hoare Partition, the pivot is chosen as the first element of the array. Two indices are used: one starts
from the left and the other from the right. These indices move towards each other until they find elements
that are out of order relative to the pivot, and then swap them. This process continues until the indices meet,
and the array is partitioned around the pivot.

Hoare Partition Algorithm

1. Choose Pivot: Select the first element as the pivot.

2. Initialize Indices:
o i starts at lo - 1 (left index).
o j starts at hi + 1 (right index).
3. Find Left and Right Elements to Swap:
o Move i from left to right until an element greater than or equal to the pivot is found.
o Move j from right to left until an element smaller than or equal to the pivot is found.
4. Swap: If i < j, swap arr[i] and arr[j] to bring the elements into the correct partition.
5. Stop: When i >= j, return j as the partition point.

This partitioning method ensures fewer swaps and comparisons, making it faster than Lomuto Partition for
larger arrays.
Hoare Partition Algorithm Implementation in C++
#include <iostream>
using namespace std;

// Function for Hoare Partitioning

int partition(int arr[], int low, int high)
{
int pivot = arr[low]; // Choose the first element as pivot
int i = low - 1; // Left index
int j = high + 1; // Right index

while (true)
{
// Move the left index until we find an element greater than or equal to pivot
do {
i++;
} while (arr[i] < pivot);

// Move the right index until we find an element smaller than or equal to pivot
do {
j--;
} while (arr[j] > pivot);

// If the indices have crossed, return the partition point

if (i >= j)
return j;

// Swap arr[i] and arr[j]

swap(arr[i], arr[j]);
}
}

// Function to perform quicksort using Hoare Partition

void quickSort(int arr[], int low, int high)
{
if (low < high)
{
// Get the partition point
int partitionIndex = partition(arr, low, high);

// Recursively apply quicksort on left and right subarrays

quickSort(arr, low, partitionIndex);
quickSort(arr, partitionIndex + 1, high);
}
}

int main()
{
int arr[] = {9, 18, 17, 15, 10, 11};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Unsorted array: ";

for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;

// Perform quicksort
quickSort(arr, 0, n - 1);

cout << "Sorted array: ";

for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;

return 0;
}
Output:
Unsorted array: 9 18 17 15 10 11
Sorted array: 9 10 11 15 17 18

Time and Space Complexity of Hoare Partition

1. Time Complexity:
o Best and Average Case: The Hoare partitioning technique splits the array into two roughly
equal halves, leading to a time complexity of O(N log N) in the best and average cases.
o Worst Case: In the worst case (e.g., when the array is already sorted), it still runs in O(N^2)
time, similar to other Quicksort versions.

Overall Time Complexity:

oBest/Average Case: O(N log N)

oWorst Case: O(N^2) (when the pivot does not divide the array well)
2. Space Complexity:
o Since Hoare's partitioning performs in-place sorting without requiring additional storage for a
temporary array, the space complexity is O(1).

Overall Space Complexity: O(1) (in-place sorting)

Advantages and Disadvantages of Hoare Partition

• Advantages:
o Fewer Comparisons: Hoare's partitioning tends to perform fewer comparisons and is more
efficient than the Lomuto partition.
o In-Place Sorting: Does not require extra space for temporary arrays, as it sorts the array in-
place.
o Efficient for Larger Arrays: Since it often performs fewer swaps and comparisons, Hoare's
partition is more cache-friendly and generally performs better for larger datasets.
• Disadvantages:
o Not Stable: Like other versions of Quicksort, Hoare's partition does not maintain the relative
order of equal elements.
o Potential for Unbalanced Partitions: In some cases (e.g., sorted or reverse-sorted arrays),
Hoare's partition can still lead to unbalanced partitions, resulting in suboptimal performance.

Summary

• Hoare Partition is an efficient partitioning method used in Quicksort.

• It involves fewer comparisons and performs in-place sorting with O(1) space complexity.
• Although Quicksort can still encounter worst-case performance of O(N^2), Hoare's partition is more
efficient for large datasets compared to Lomuto partitioning.

QuickSort: A Divide and Conquer Algorithm

QuickSort is a highly efficient sorting algorithm that uses the Divide and Conquer technique to sort
elements. The key idea is to partition the array around a pivot, such that all elements smaller than the pivot
are on one side, and all elements greater than the pivot are on the other side. QuickSort then recursively
applies the same process to the sub-arrays.

Steps in QuickSort:

1. Choose a pivot element from the array (there are different strategies for picking the pivot).
2. Partition the array: Arrange the array such that all elements less than the pivot are on its left and all
elements greater than the pivot are on its right. The pivot is then placed in its correct sorted position.
3. Recursively sort the sub-arrays on either side of the pivot.

Partitioning Process:

The partitioning process is key to QuickSort. It places the pivot in its correct sorted position and ensures
that:

• All elements smaller than the pivot are on its left.

• All elements greater than the pivot are on its right.

This process takes linear time O(n)O(n).

Partitioning Algorithm (Lomuto Partition):

1. Choose a pivot (e.g., the last element of the array).

2. Traverse the array and compare each element to the pivot:
o If an element is smaller than or equal to the pivot, increment the index i and swap the
element at i with the current element.
3. After the loop, place the pivot at the correct position by swapping it with the element at i + 1.

The pivot is now in its correct sorted position, and the array is partitioned into two sub-arrays: elements
smaller than the pivot on the left and elements greater than the pivot on the right.

QuickSort Algorithm (Recursive):

The QuickSort algorithm applies the partitioning process and recursively sorts the two sub-arrays.

#include <iostream>
using namespace std;

// Function for partitioning the array

int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choosing the last element as the pivot
int i = (low - 1); // Index of smaller element

for (int j = low; j <= high - 1; j++) {

// If current element is smaller or equal to pivot
if (arr[j] <= pivot) {
i++; // Increment index of smaller element
swap(arr[i], arr[j]); // Swap elements
}
}

swap(arr[i + 1], arr[high]); // Swap pivot to the correct position

return (i + 1); // Return the partition index
}

// QuickSort function
void quickSort(int arr[], int low, int high) {
 if (low < high) {
int pi = partition(arr, low, high); // Partition the array
quickSort(arr, low, pi - 1); // Sort the left sub-array
quickSort(arr, pi + 1, high); // Sort the right sub-array
}
}

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

quickSort(arr, 0, n - 1); // Apply quickSort to the entire array

// Output the sorted array

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

Example Walkthrough:

Given the array:

arr[] = {10, 80, 30, 90, 40, 50, 70}
The process starts by choosing the last element 70 as the pivot.

1. First Partition:
o Pivot = 70
o Traverse through the array:
▪ 10 <= 70 → Swap 10 with itself.
▪ 80 > 70 → No change.
▪ 30 <= 70 → Swap 80 and 30.
▪ 90 > 70 → No change.
▪ 40 <= 70 → Swap 80 and 40.
▪ 50 <= 70 → Swap 90 and 50.
o After traversal, swap the pivot (70) with the element at index i + 1 → {10, 30, 40, 50,
70, 90, 80}.
o The pivot 70 is placed in its correct position at index 4.
2. Recursively Sort the Sub-arrays:
o Left sub-array: {10, 30, 40, 50}
o Right sub-array: {90, 80}

The process continues with the same partitioning logic until the array is fully sorted.

Time Complexity Analysis:

1. Worst Case:
o The worst case occurs when the pivot is the smallest or largest element, causing unbalanced
partitions (e.g., when the array is already sorted or nearly sorted).
o Recurrence relation:
T(n)=T(0)+T(n−1)+O(n)T(n) = T(0) + T(n-1) + O(n)
The solution to this recurrence is O(n2)O(n^2).
2. Best Case:
o The best case occurs when the pivot is always the median, leading to balanced partitions.
o Recurrence relation:
T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)
The solution to this recurrence is O(nlog⁡n)O(n \log n).
3. Average Case:
 o The average case assumes that the pivot divides the array into two roughly equal sub-arrays.
o Recurrence relation:
T(n)=T(n/9)+T(9n/10)+O(n)T(n) = T(n/9) + T(9n/10) + O(n)
The solution to this recurrence is also O(nlog⁡n)O(n \log n).

Space Complexity:

• QuickSort is an in-place algorithm, so it does not require additional space except for recursion stack.
• Space Complexity: O(log⁡n)O(\log n) for balanced partitions due to the recursion stack. In the
worst case (unbalanced partition), it could be O(n)O(n).

Advantages of QuickSort:

• Efficient in Practice: Even though the worst-case time complexity is O(n2)O(n^2), QuickSort is
often faster than other sorting algorithms like Merge Sort and Heap Sort because of better cache
performance and low overhead in practice.
• In-place Sorting: QuickSort sorts the array in place, meaning it doesn’t require additional space for
a temporary array.

Disadvantages of QuickSort:

• Worst-case Time Complexity: In some cases (like a nearly sorted array), QuickSort may degrade to
O(n2)O(n^2) if the pivot selection is poor.
• Unstable Sorting: QuickSort is not a stable sorting algorithm. It does not preserve the relative order
of equal elements.

Conclusion:

QuickSort is one of the fastest sorting algorithms in practice, with average time complexity O(nlog⁡n)O(n
\log n). However, it is essential to consider the pivot selection strategy to avoid the worst-case scenario and
ensure that QuickSort performs optimally.

QuickSort Analysis Overview

QuickSort is a widely used sorting algorithm due to its efficiency and simplicity, but it also has a few trade-
offs that need to be considered in certain contexts. Here’s a detailed analysis of QuickSort from multiple
angles:

Is QuickSort Stable?

• QuickSort is generally unstable. This means that it does not guarantee to preserve the relative order
of equal elements in the array. For example, if two elements have the same value, QuickSort might
swap them, changing their relative positions.
• Stability can be achieved by modifying the algorithm to compare the elements using their indices,
ensuring that the relative order is preserved. However, this might slightly impact performance.

Is QuickSort In-place?

• Yes, QuickSort is in-place. It sorts the array without needing extra storage for a new array.
However, it uses recursion, which consumes extra space for function calls on the call stack.
 • In-place sorting means it does not require O(N) extra space for an auxiliary array like MergeSort
does. The space used by QuickSort is only for the recursion stack.

What is 3-Way QuickSort?

• 3-Way QuickSort is an improvement over the standard QuickSort when dealing with arrays that
have many duplicate elements. The standard QuickSort partitions the array into two subarrays:
elements less than the pivot and elements greater than the pivot. However, when many duplicates are
present, it can result in inefficient recursion.
• In 3-Way QuickSort, the array is divided into three parts:
1. Elements less than the pivot.
2. Elements equal to the pivot.
3. Elements greater than the pivot.

This reduces unnecessary recursive calls and ensures that the algorithm works efficiently even with
many duplicate elements.

How to Implement QuickSort for Linked Lists?

• QuickSort on Singly Linked List:

o One challenge with sorting linked lists using QuickSort is the lack of random access. Unlike
arrays, where you can access any element in constant time, linked lists require traversal to
access specific elements.
o For Singly Linked List, the partitioning process can be trickier, and an iterative approach is
often used for efficiency.
• QuickSort on Doubly Linked List:
o Doubly linked lists allow both forward and backward traversals, which makes partitioning
easier. The QuickSort algorithm can be adapted by using pointers to traverse the list and
partition it without needing extra space for sublists.

Can We Implement QuickSort Iteratively?

• Yes, QuickSort can be implemented iteratively. The recursive nature of QuickSort can be replaced
by using a stack to mimic the recursive calls. This avoids the overhead of recursive function calls and
can be more space-efficient.

Why QuickSort is Preferred Over MergeSort for Sorting Arrays?

1. In-place Sorting: QuickSort does not require extra space for sorting, whereas MergeSort requires
O(N) additional space.
2. Faster in Practice: QuickSort tends to be faster in practice, especially for small to moderately sized
arrays. It works well with the cache hierarchy due to its locality of reference, making it more
efficient than MergeSort in most cases.
3. Randomized Version: The randomized QuickSort (where the pivot is chosen randomly) ensures
that the worst-case time complexity is highly unlikely and generally remains O(N log N).
4. Tail Recursion Optimization: QuickSort is tail recursive, which makes it eligible for tail call
optimization by modern compilers, further improving efficiency.
Why MergeSort is Preferred Over QuickSort for Linked Lists?

1. No Random Access: Linked lists don’t allow direct access to elements like arrays. QuickSort relies
on random access to partition the array efficiently, which is not feasible with linked lists.
2. MergeSort Works Better: MergeSort, on the other hand, can work efficiently with linked lists
because it does not require random access. Instead, it can merge lists by traversing them sequentially,
which is ideal for linked lists.
3. Merge Sort’s Simplicity: MergeSort can be implemented without extra space for linked lists,
whereas QuickSort's partitioning would require extra steps and additional space overhead.

How to Optimize QuickSort for O(log n) Extra Space?

To optimize QuickSort and reduce its recursion stack to O(log n) space:

• Tail Call Optimization: The recursion depth can be reduced by always recursively calling the
smaller partition first. This way, the larger partition is processed using an iterative approach (using a
stack).
• This ensures that the recursion depth remains logarithmic, which helps keep the space complexity to
O(log n).

Advantages of QuickSort

1. Efficient: QuickSort is efficient on large datasets, with an average time complexity of O(N log N).
2. In-place Sorting: It doesn’t require extra space, which is a significant advantage over algorithms
like MergeSort.
3. Divide and Conquer: QuickSort’s divide-and-conquer approach allows it to break down problems
into manageable subproblems.
4. Randomized Versions: Randomizing the pivot helps avoid worst-case scenarios in practice.

Disadvantages of QuickSort

1. Worst-case Time Complexity: QuickSort’s worst-case time complexity is O(N^2), which occurs
when the pivot consistently divides the array poorly (e.g., already sorted or reverse-sorted arrays).
2. Not Stable: QuickSort does not preserve the relative order of equal elements.
3. Sensitive to Pivot Selection: A bad choice of pivot can lead to inefficient partitioning.
4. Not Cache-efficient: QuickSort does not perform well with large datasets stored in external
memory.

Time Complexity Analysis of QuickSort

• Worst Case: O(N^2) occurs when the pivot is the smallest or largest element, leading to unbalanced
partitions (e.g., when the array is already sorted).
• Best Case: O(N log N) occurs when the pivot divides the array into two equal halves.
• Average Case: O(N log N), assuming the pivot divides the array well.
Recurrence Relations:

• Worst Case: T(n) = T(n-1) + Θ(n) → O(N^2)

• Best Case: T(n) = 2T(n/2) + Θ(n) → O(N log N)
• Average Case: T(n) = T(n/9) + T(9n/10) + Θ(n) → O(N log N)

Summary of QuickSort

• QuickSort is a divide-and-conquer algorithm that works by partitioning the array around a pivot
and recursively sorting the subarrays.
• Efficient in practice due to in-place sorting and cache friendliness.
• Its average time complexity is O(N log N), but it suffers from O(N^2) in the worst case.
• It is generally not stable and sensitive to the choice of pivot, but its performance can be improved
with randomization.
• QuickSort is often preferred for sorting arrays due to its low memory overhead compared to
MergeSort.
• However, MergeSort is preferred for linked lists because it doesn’t require random access and
works better in that context.

Tail Call Elimination in QuickSort

Tail Call Elimination (also known as Tail Call Optimization, TCO) is an optimization technique used by
modern compilers to optimize recursive functions. It is particularly useful for tail-recursive functions,
where the recursive call is the last operation performed in the function. In this case, the compiler can
optimize the recursion to avoid creating a new stack frame for each recursive call, leading to reduced
memory usage.

What is Tail Recursion?

A recursive function is considered tail recursive if the recursive call is the last thing executed by the
function. This means that once the recursive call is made, the current function’s state doesn’t need to be
preserved, and the stack frame of that function can be reused for the next function call. This helps in
reducing memory consumption by keeping the function call stack constant rather than growing with each
recursive call.

Example of Tail Recursion

Consider the following example where the print function is tail-recursive:

#include <bits/stdc++.h>
using namespace std;

void print(int n)
{
if (n < 0)
return;
cout << n;
// The last executed statement is the recursive call
print(n - 1);
}

In this example:
 • The recursive call is the last operation executed in the function, which means the function can be
optimized for memory by the compiler.
• The function can be rewritten to use goto for tail-call elimination, as shown below:

#include <bits/stdc++.h>
using namespace std;

void print(int n)
{
start:
if (n < 0)
return;
cout << n;

// Update parameters for the recursive call and replace with `goto`
n = n - 1;
goto start;
}

By using a goto statement, we effectively eliminate the need to create a new stack frame for each recursive
call, resulting in constant memory usage.

Tail Recursion in QuickSort

QuickSort, by nature, is a divide and conquer algorithm where the input array is partitioned around a pivot,
and recursive calls are made to sort the subarrays on the left and right of the pivot.

QuickSort’s recursive nature makes it an ideal candidate for tail call optimization. Let’s take a look at the
standard QuickSort implementation:

void quickSort(int arr[], int low, int high)

{
if (low < high)
{
int pi = partition(arr, low, high); // partition index
quickSort(arr, low, pi - 1); // sort left subarray
quickSort(arr, pi + 1, high); // sort right subarray
}
}

In the above recursive quickSort function, two recursive calls are made:

1. One for the left subarray (low to pi-1).

2. One for the right subarray (pi+1 to high).

In this case, the recursive call to quickSort(arr, low, pi - 1) is not tail recursive because after it
returns, we still need to perform another recursive call on the right subarray.

To optimize this using tail recursion, we can remove the second recursive call and ensure that the function
tail-recurses on the smaller subarray, leaving the larger subarray for the iterative part. Here’s the optimized
code with tail call elimination:

void quickSort(int arr[], int low, int high)

{
start:
if (low < high)
{
int pi = partition(arr, low, high); // partition index
 // Tail-recursive call on the smaller part (left part)
quickSort(arr, low, pi - 1);

// Update the parameters for the right part and jump to the start of the
function
low = pi + 1;
goto start; // Use `goto` to eliminate the second recursive call.
}
}

Explanation of Tail Call Elimination in QuickSort

1. First recursive call: The left subarray (low to pi-1) is processed as usual through the recursive call.
2. Eliminate second recursive call: The right subarray (pi+1 to high) is handled by updating the low
and high parameters and using a goto statement to go back to the beginning of the function. This
avoids an additional recursive call, making the function tail-recursive.

Why Tail Call Elimination is Beneficial

Without tail call elimination, each recursive call adds a new frame to the call stack. The stack stores local
variables, function parameters, and return addresses, and it grows with each recursive call. This can lead to
stack overflow in case of deep recursion.

With tail call elimination:

• The compiler recognizes that no work is left to do after the recursive call, and it reuses the current
function's stack frame.
• The space complexity of the recursion is reduced from O(N) (for regular recursion) to O(1) (constant
space).

This means that instead of growing the call stack, the recursive function executes in constant memory space,
which makes it more memory-efficient and faster.

Function Stack Frame Management in Tail Call Elimination

In a typical recursive function, each call creates a new stack frame with its own local variables. However, in
tail recursion:

• No stack frame is needed for the recursive call because there are no operations left to perform
after the call.
• Constant memory space is used because no additional stack frames are created for each recursive
call, leading to a reduced space complexity of O(1).

Key Benefits of Tail Call Elimination

• Space Efficiency: No extra space is required for function calls, so the algorithm uses constant
memory regardless of the recursion depth.
• Improved Performance: Reduces memory overhead and avoids stack overflow, allowing the
algorithm to handle larger inputs efficiently.
• Faster Execution: As the call stack doesn’t grow unnecessarily, the overall time and space
complexities improve.
Conclusion

• QuickSort is inherently a recursive algorithm, and by applying tail call elimination, we can
significantly reduce the space complexity of the algorithm from O(N) to O(1).
• This optimization is particularly useful in deep recursive calls, allowing the algorithm to process
large arrays without running into memory issues.
• Modern compilers optimize tail recursion through tail call elimination, improving both memory
efficiency and performance.

By understanding and implementing tail recursion and optimization techniques like tail call elimination, we
can improve the efficiency of recursive algorithms like QuickSort.

To find the k-th smallest element in an array, we can use several methods. Below are two common
approaches:

Method 1: Simple Sorting

One way to find the k-th smallest element is by sorting the array and then returning the element at the k-1
index in the sorted array. This is the simplest approach.

Steps:

1. Sort the array using an efficient sorting algorithm like Merge Sort, Heap Sort, or QuickSort.
2. The k-th smallest element will be at index k-1 in the sorted array.

Time Complexity:

• Sorting the array takes O(Nlog⁡N)O(N \log N) time.

• Therefore, the overall time complexity is O(Nlog⁡N)O(N \log N).

Space Complexity:

• Since we are using an in-place sorting algorithm, the space complexity is O(1)O(1).

Implementation (C++):

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

// Function to return k'th smallest element in a given array

int kthSmallest(int arr[], int n, int k) {
// Sort the given array
sort(arr, arr + n);

// Return k'th element in the sorted array

return arr[k - 1];
}

// Driver program to test above methods

int main() {
int arr[] = {12, 3, 5, 7, 19};
int n = sizeof(arr) / sizeof(arr[0]), k = 2;

cout << "K'th smallest element is " << kthSmallest(arr, n, k);

return 0;
}

Output:
K'th smallest element is 5

Method 2: Using a Min Heap (HeapSelect)

We can optimize the solution further by using a Min Heap. A Min Heap is a binary tree where the value of
the parent node is smaller than or equal to the values of its children.

Steps:

1. Create a Min Heap from the array.

2. Extract the minimum element from the heap k times. The k-th extraction will give us the k-th
smallest element.

Time Complexity:

• Building the heap takes O(N)O(N) time.

• Extracting the minimum element k times takes O(klog⁡N)O(k \log N).
• Therefore, the overall time complexity is O(N+klog⁡N)O(N + k \log N).

Space Complexity:

• We need O(N)O(N) space to store the heap elements.

Implementation (C++):

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

// A class for Min Heap

class MinHeap {
int* harr; // Pointer to array of elements in heap
int capacity; // Maximum possible size of min heap
int heap_size; // Current number of elements in min heap

public:
MinHeap(int a[], int size); // Constructor
void MinHeapify(int i); // To minheapify subtree rooted with index i
int parent(int i) { return (i - 1) / 2; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }

int extractMin(); // Extracts root (minimum) element

int getMin() { return harr[0]; } // Returns minimum
};

// Constructor to build the min heap

MinHeap::MinHeap(int a[], int size) {
heap_size = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}

// MinHeapify to maintain the heap property

void MinHeap::MinHeapify(int i) {
int l = left(i);
int r = right(i);
 int smallest = i;

if (l < heap_size && harr[l] < harr[i])

smallest = l;

if (r < heap_size && harr[r] < harr[smallest])

smallest = r;

if (smallest != i) {
swap(harr[i], harr[smallest]);
MinHeapify(smallest);
}
}

// Extract the minimum element (root of the heap)

int MinHeap::extractMin() {
if (heap_size <= 0)
return INT_MAX;

if (heap_size == 1) {
heap_size--;
return harr[0];
}

int root = harr[0];

harr[0] = harr[heap_size - 1];
heap_size--;
MinHeapify(0);

return root;
}

// Function to return k'th smallest element

int kthSmallest(int arr[], int n, int k) {
MinHeap minHeap(arr, n);
int minElement;
for (int i = 0; i < k; i++) {
minElement = [Link]();
}
return minElement;
}

// Driver program to test above methods

int main() {
int arr[] = {12, 3, 5, 7, 19};
int n = sizeof(arr) / sizeof(arr[0]), k = 2;

cout << "K'th smallest element is " << kthSmallest(arr, n, k);

return 0;
}

Output:

K'th smallest element is 5

Comparing the Methods:

Method Time Complexity Space Complexity

Simple Sorting O(Nlog⁡N)O(N \log N) O(1)O(1) (in-place)
Min Heap O(N+klog⁡N)O(N + k \log N) O(N)O(N)
 • Method 1 (Sorting) is simpler and requires no extra space for the heap. However, it has a higher
time complexity of O(Nlog⁡N)O(N \log N).
• Method 2 (Min Heap) is more efficient when k is small because it has a better time complexity of
O(N+klog⁡N)O(N + k \log N), especially if k is much smaller than N.

Both methods are effective depending on the problem's constraints. If you expect k to be much smaller than
the array size, the heap method could be more efficient. However, if simplicity and readability are important,
sorting might be sufficient.

Problem: Minimum Difference in an Array

The problem asks for finding the minimum absolute difference between any two elements in an unsorted
array.

Naive Approach

The naive approach involves generating every possible pair of elements in the array and calculating the
absolute difference between them to find the minimum difference.

Steps:

1. Use two nested loops to iterate through all pairs of elements.

2. Calculate the absolute difference between each pair.
3. Keep track of the minimum difference found.

Time Complexity:

• The time complexity for this approach is O(N²), where N is the number of elements in the array, as
we are checking all pairs.

Auxiliary Space:

• The auxiliary space complexity is O(1) since we are using only a constant amount of extra space for
variables.

Code:

#include <bits/stdc++.h>
using namespace std;

// Returns minimum difference between any pair

int findMinDiff(int arr[], int n)
{
// Initialize difference as infinite
int diff = INT_MAX;

// Find the min diff by comparing difference of all possible pairs

for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (abs(arr[i] - arr[j]) < diff)
diff = abs(arr[i] - arr[j]);

// Return min diff

return diff;
}

int main()
{
int arr[] = {1, 5, 3, 19, 18, 25};
 int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum difference is " << findMinDiff(arr, n) << endl;
return 0;
}

Output:

Minimum difference is 1

Efficient Approach

The naive approach has a time complexity of O(N²), which can be improved. The efficient approach
involves sorting the array first. After sorting, the minimum difference will be between adjacent elements
because any larger differences would naturally be formed by elements that are further apart in the sorted
array.

Steps:

1. Sort the array in non-decreasing order.

2. Compare only adjacent elements to find the minimum difference.
3. Return the minimum difference found.

Time Complexity:

• The time complexity is O(N log N) because sorting the array takes O(N log N) time, and the linear
scan to find the minimum difference takes O(N) time.

Auxiliary Space:

• The auxiliary space is O(1) since we are using only a few extra variables for tracking the minimum
difference.

Code:

#include <bits/stdc++.h>
using namespace std;

// Returns minimum difference between any pair

int findMinDiff(int arr[], int n)
{
// Sort the array in non-decreasing order
sort(arr, arr + n);

// Initialize difference as infinite

int diff = INT_MAX;

// Find the min diff by comparing adjacent pairs

for (int i = 0; i < n - 1; i++)
if (arr[i + 1] - arr[i] < diff)
diff = arr[i + 1] - arr[i];

// Return min diff

return diff;
}

int main()
{
int arr[] = {1, 5, 3, 19, 18, 25};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum difference is " << findMinDiff(arr, n) << endl;
return 0;
}

Output:

Minimum difference is 1

Explanation of the Efficient Approach:

1. Sorting:
Sorting the array ensures that the smallest difference will always occur between two adjacent
elements. For example, if you have the sorted array [1, 3, 5, 19, 18, 25], the minimum
difference must be between two adjacent numbers (i.e., between 18 and 19).
2. Scanning for Minimum Difference:
After sorting, we only need to compare adjacent elements, which reduces the problem to a linear
scan of the array. This makes it much faster than checking every pair in the array.

Summary:

• Naive Approach:
o Time Complexity: O(N²)
o Auxiliary Space: O(1)
o Suitable for small arrays, but inefficient for larger datasets.
• Efficient Approach:
o Time Complexity: O(N log N)
o Auxiliary Space: O(1)
o More efficient for larger datasets, as sorting reduces the problem size.

By sorting the array first, we reduce the problem of finding the minimum difference between any two
elements to just comparing adjacent pairs, which significantly improves performance.

Sorting an Array with Two Types of Elements (0s and 1s)

Given an array with only two types of elements (0s and 1s), we want to segregate the 0s on the left side and
the 1s on the right side, all in a single traversal. This is a common problem that can be efficiently solved
using the two-pointer technique.

Approach

1. Two Pointers:
o We use two pointers: type0 (starting from the left) and type1 (starting from the right).
o type0 will move towards the right to find 1s, and type1 will move towards the left to find 0s.
2. Swapping Logic:
o If the element at type0 is 1, we swap it with the element at type1, and then move type1 left
(because we now know the element at type1 is 1).
o If the element at type0 is 0, we simply move type0 right.
3. This way, the array is partitioned with 0s on the left and 1s on the right by the time the two pointers
meet.

Time Complexity:

• O(n) where n is the size of the array. We only traverse the array once.
Auxiliary Space:

• O(1) since the sorting is done in place, and no extra space is used.

Implementation (C++):
#include <iostream>
#include <algorithm>
using namespace std;

// Method for segregation 0 and 1 given input array

void segregate0and1(int arr[], int n)
{
int type0 = 0; // Pointer to place 0
int type1 = n - 1; // Pointer to place 1

while (type0 < type1) {

if (arr[type0] == 1) {
// If current element is 1, swap it with the element at type1
swap(arr[type0], arr[type1]);
type1--; // Move type1 to the left
}
else {
// If current element is 0, move type0 to the right
type0++;
}
}
}

// Driver program
int main()
{
int arr[] = {0, 1, 0, 1, 0, 0, 1, 1, 1, 0};
int n = sizeof(arr) / sizeof(arr[0]);

segregate0and1(arr, n);

// Print the sorted array

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

return 0;
}

Explanation:

• Initial Pointers:
o type0 = 0 (leftmost index of the array).
o type1 = n - 1 (rightmost index of the array).
• Logic:
o If the element at arr[type0] is 1, we swap it with arr[type1] and move type1 one step to
the left.
o If the element at arr[type0] is 0, we move type0 one step to the right.
• The loop continues until the two pointers cross, i.e., type0 >= type1, ensuring all 0s are on the left
and all 1s are on the right.

Example Run:

For the input:

arr[] = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
 1. Initially:
2. type0 = 0, type1 = 9, arr[] = [0, 1, 0, 1, 0, 0, 1, 1, 1, 0]
3. Swap elements where necessary, and the array after traversal becomes:
4. arr[] = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
5. Final Output:
6. 0 0 0 0 0 1 1 1 1 1

Output:
0 0 0 0 0 1 1 1 1 1

Summary:

• This method is an efficient way to sort an array of 0s and 1s using the two-pointer technique in one
pass.
• The time complexity is O(n) and the space complexity is O(1).

Problem: Sort an Array with 0s, 1s, and 2s

We are given an array consisting of three types of elements: 0s, 1s, and 2s. The goal is to sort the array in
such a way that all 0s appear first, followed by all 1s, and finally, all 2s. We need to do this in an efficient
manner.

Approach 1: Dutch National Flag Algorithm (Single Pass)

The Dutch National Flag problem, proposed by Edsger Dijkstra, is a well-known problem used to sort an
array of three different elements. In this case, we have three distinct elements: 0, 1, and 2.

Explanation:

• We maintain three pointers:

o lo: This pointer represents the boundary between 0s and 1s.
o mid: This pointer represents the current element being evaluated.
o hi: This pointer represents the boundary between 1s and 2s.
• The array is divided into four sections:
o 0s are at the start ([0..lo-1]).
o 1s are between lo and mid-1.
o mid to hi is the unknown region.
o 2s are at the end ([hi+1..n-1]).

Steps:

1. If the current element (a[mid]) is 0, it is swapped with a[lo], and we increment both lo and mid.
2. If the current element is 1, we simply move mid forward.
3. If the current element is 2, it is swapped with a[hi], and we decrement hi, but mid remains
unchanged because we need to evaluate the swapped element.

The process continues until mid crosses hi.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to sort the input array of 0s, 1s, and 2s

void sort012(int a[], int arr_size)
{
int lo = 0;
int hi = arr_size - 1;
int mid = 0;

// Iterate until mid is less than or equal to hi

while (mid <= hi) {
switch (a[mid]) {
case 0:
// Swap 0 to the low range
swap(a[lo++], a[mid++]);
break;
case 1:
// If it's 1, just move mid forward
mid++;
break;
case 2:
// Swap 2 to the high range
swap(a[mid], a[hi--]);
break;
}
}
}

// Driver code
int main()
{
int arr[] = {0, 1, 2, 0, 1, 2};
int n = sizeof(arr) / sizeof(arr[0]);

sort012(arr, n);

cout << "Sorted array: ";

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

return 0;
}

Output:

Sorted array: 0 0 1 1 2 2

Complexity Analysis:

• Time Complexity: O(n), where n is the number of elements in the array. Only one pass through the
array is needed.
• Space Complexity: O(1) because the sorting is done in-place with only a few additional variables.

Approach 2: Counting Sort Method

Another approach is to count the occurrences of 0s, 1s, and 2s in the array. Once we have the counts, we
can reconstruct the array by placing all 0s first, followed by 1s and 2s.

Steps:

1. Count the number of 0s, 1s, and 2s in the array.

2. Modify the array such that:
o First, fill the array with the counted 0s.
 o Then, fill the array with the counted 1s.
o Finally, fill the array with the counted 2s.

Code Implementation:

#include <bits/stdc++.h>
using namespace std;

// Function to print the array

void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}

// Function to sort the array of 0s, 1s, and 2s using counting sort
void sortArr(int arr[], int n)
{
int cnt0 = 0, cnt1 = 0, cnt2 = 0;

// Count the number of 0s, 1s, and 2s in the array

for (int i = 0; i < n; i++) {
switch (arr[i]) {
case 0:
cnt0++;
break;
case 1:
cnt1++;
break;
case 2:
cnt2++;
break;
}
}

// Replace the array with sorted elements based on the counts

for (int i = 0; i < n; i++) {
if (i < cnt0)
arr[i] = 0;
else if (i < cnt0 + cnt1)
arr[i] = 1;
else
arr[i] = 2;
}
}

// Driver code
int main()
{
int arr[] = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
int n = sizeof(arr) / sizeof(arr[0]);

sortArr(arr, n);

cout << "Sorted array: ";

printArr(arr, n);

return 0;
}

Output:

Sorted array: 0 0 0 0 0 1 1 1 1 1 2 2

Complexity Analysis:
 • Time Complexity: O(n) because we are doing two passes: one for counting and one for assigning
values to the array.
• Space Complexity: O(1) because we are not using any extra space (except a few counters).

Summary:

• Dutch National Flag Algorithm (Single Pass): This approach uses a three-way partitioning strategy
to sort the array in one pass with O(n) time complexity and O(1) space complexity.
• Counting Sort Method: This approach counts the occurrences of each element (0, 1, 2) and
reconstructs the sorted array. It also has O(n) time complexity and O(1) space complexity.

Both approaches are efficient, with the Dutch National Flag Algorithm being a more elegant solution for this
particular problem.

Problem: Meeting the Maximum Guests in a Party

Given the arrival and exit times of guests in a party, we need to determine the time at which there are the
maximum number of guests present at the party.

Approach:

There are two efficient approaches for solving this problem.

Method 1: Sorting and Merging Events (O(n log n) Time)

The idea is to treat each guest's entry and exit as an "event." We can sort these events and then track the
number of guests at any given time.

1. Step 1: Sort the arrival and exit times separately.

2. Step 2: Process the two sorted arrays using a merge-like approach.
o If the current event is an arrival, increment the count of guests.
o If the current event is an exit, decrement the count of guests.
3. Step 3: Keep track of the maximum number of guests and the corresponding time.

Here is the implementation:

C++ Code:
#include<iostream>
#include<algorithm>
using namespace std;

void findMaxGuests(int arr[], int exit[], int n) {

// Sort the arrival and exit arrays
sort(arr, arr + n);
sort(exit, exit + n);

int guests_in = 1, max_guests = 1, time = arr[0];

int i = 1, j = 0;

// Merge-like process to handle events

while (i < n && j < n) {
// If next event is arrival, increment guest count
if (arr[i] <= exit[j]) {
guests_in++;
i++;
 }
// If next event is exit, decrement guest count
else {
guests_in--;
j++;
}

// Update max_guests and time if we have more guests

if (guests_in > max_guests) {
max_guests = guests_in;
time = arr[i-1];
}
}

// Output the result

cout << "Maximum Number of Guests = " << max_guests << " at time " << time << endl;
}

int main() {
int arr[] = {1, 2, 10, 5, 5}; // Arrival times
int exit[] = {4, 5, 12, 9, 12}; // Exit times
int n = sizeof(arr) / sizeof(arr[0]);

findMaxGuests(arr, exit, n);

return 0;
}

Explanation:

• Step 1: Both the arr (arrival) and exit arrays are sorted.
• Step 2: We maintain two indices, i (for arrivals) and j (for exits), and traverse the two sorted arrays.
o If the next event is an arrival (i.e., arr[i] <= exit[j]), we increment the guest count.
o If it's an exit, we decrement the guest count.
• Step 3: As we process events, we keep track of the maximum number of guests and the
corresponding time.

Example Run:

For the input:

arr[] = {1, 2, 10, 5, 5}

exit[] = {4, 5, 12, 9, 12}

1. Sort the arr and exit arrays:

2. arr[] = {1, 2, 5, 5, 10}
3. exit[] = {4, 5, 9, 12, 12}
4. Using the merge-like process:
o At time 1: 1 guest arrives (1 guest in the party).
o At time 2: 1 more guest arrives (2 guests in the party).
o At time 4: 1 guest leaves (1 guest in the party).
o At time 5: 1 more guest arrives (2 guests in the party).
o At time 5: Another guest arrives (3 guests in the party) → maximum guests at time 5.
o At time 5: 1 guest leaves (2 guests in the party).
o At time 9: 1 more guest leaves (1 guest in the party).
o At time 10: 1 guest arrives (2 guests in the party).
o At time 12: 1 guest leaves (1 guest in the party).
o At time 12: Another guest leaves (0 guests in the party).

The maximum number of guests is 3 at time 5.

Output:
Maximum Number of Guests = 3 at time 5

Time Complexity:

• Sorting the two arrays takes O(n log n) time.

• The traversal of the arrays to calculate the maximum number of guests takes O(n) time. Thus, the
total time complexity is O(n log n).

Method 2: Using an Auxiliary Array (O(max time))

This method uses an auxiliary array to track the number of guests at each point in time. It works by
incrementing the count at the arrival time and decrementing it after the exit time.

1. Step 1: Create an auxiliary array that tracks guest arrivals and exits at specific times.
2. Step 2: For each arrival time arr[i], increment the count at arr[i].
3. Step 3: For each exit time exit[i], decrement the count at exit[i] + 1 (because the guest leaves
after this time).
4. Step 4: Calculate the cumulative sum across the auxiliary array to find the maximum number of
guests at any time.

C++ Code for Auxiliary Array Approach:

#include<bits/stdc++.h>
using namespace std;

void maxOverlap(vector<int>& start, vector<int>& end) {

int n = [Link]();

// Find the maximum time in the start and end arrays

int max_start = *max_element([Link](), [Link]());
int max_end = *max_element([Link](), [Link]());
int max_time = max(max_start, max_end);

vector<int> x(max_time + 2, 0); // Auxiliary array

// Add 1 at the start time and subtract 1 after the end time
for(int i = 0; i < n; i++) {
x[start[i]]++;
x[end[i] + 1]--;
}

int max_guests = 0, current_guests = 0, time_at_max = 0;

// Traverse through the array to find the maximum number of guests
for(int i = 0; i <= max_time; i++) {
current_guests += x[i];
if(current_guests > max_guests) {
max_guests = current_guests;
time_at_max = i;
}
}

cout << "Maximum value is " << max_guests << " at position " << time_at_max <<
endl;
}

int main() {
vector<int> start = {1, 2, 10, 5, 5}; // Arrival times
vector<int> end = {4, 5, 12, 9, 12}; // Exit times

maxOverlap(start, end);
 return 0;
}

Time Complexity:

• The time complexity is O(max(time)), where max(time) is the maximum value in the start or end
array.
• The auxiliary space complexity is also O(max(time)) for the auxiliary array.

Conclusion:

• Method 1 (Sorting and Merging Events) is efficient with O(n log n) time complexity, which is
suitable when dealing with large input sizes.
• Method 2 (Using an Auxiliary Array) is effective when the time range (max(time)) is reasonably
small, as it takes O(max(time)) time.

Here’s a more polished version of your article on Cycle Sort:

Cycle Sort

Cycle Sort is an in-place, unstable sorting algorithm and a comparison-based sorting technique. It is
considered theoretically optimal in terms of the total number of writes to the original array.

Key Features of Cycle Sort:

• In-place Sorting: Cycle Sort does not require additional memory to store the sorted array; the
sorting happens within the given array.
• Optimal Write Efficiency: This algorithm minimizes memory writes. Each value is either written
zero times if it's already in its correct position or one time to its correct position.
• Unstable Sorting: It does not guarantee the order of equal elements in the sorted array.
• Comparison Sort: The sorting process relies on comparing elements with each other.

How Cycle Sort Works:

Cycle Sort works by dividing the array into distinct cycles. Each cycle is a group of elements that need to be
placed in their correct positions. You can visualize a cycle as a graph where each node represents an element
in the array, and the directed edge from node i to node j indicates that the element at index i should be at
index j in the sorted array.

Here’s an example of the cycle in the array arr[] = {2, 4, 5, 1, 3}:

Cycle in arr[] = {4, 3, 2, 1}

In this case, the array elements are part of a cycle, where each element should be moved to the correct
position in a sorted array.

Implementation of Cycle Sort (C++):

// C++ program to implement cycle sort

#include <iostream>
using namespace std;

// Function to sort the array using Cycle Sort

void cycleSort(int arr[], int n)
{
// Count the number of memory writes
int writes = 0;

// Traverse array elements and place them at their correct position

for (int cycle_start = 0; cycle_start <= n - 2; cycle_start++)
{
// Initialize item as the starting point of the cycle
int item = arr[cycle_start];

// Find the correct position to place the item

int pos = cycle_start;
for (int i = cycle_start + 1; i < n; i++)
{
if (arr[i] < item)
pos++;
}

// If the item is already in the correct position, skip the cycle

if (pos == cycle_start)
continue;

// Otherwise, put the item to the correct position

while (item == arr[pos])
pos++;

// Place the item at its correct position

if (item != arr[pos])
{
swap(item, arr[pos]);
writes++;
}

// Continue to move the items in the cycle

while (pos != cycle_start)
{
pos = cycle_start;
for (int i = cycle_start + 1; i < n; i++)
{
if (arr[i] < item)
pos++;
}

// Move the item to the correct position

while (item == arr[pos])
pos++;

// Place the item at its correct position

if (item != arr[pos])
{
swap(item, arr[pos]);
writes++;
}
}
}
}

Time Complexity:

• Worst Case: O(n^2)

 • Average Case: O(n^2)
• Best Case: O(n^2)

Cycle Sort has quadratic time complexity in all cases because it needs to traverse each cycle and shift
elements within the cycle.

Space Complexity:

• Auxiliary Space: O(1)

Since Cycle Sort is an in-place sorting algorithm, it does not require any additional memory other than the
input array itself.

Summary:

• Optimal for Write Operations: Cycle Sort minimizes the number of memory writes compared to
other sorting algorithms.
• In-place Sorting Algorithm: No extra space is needed beyond the input array.
• Unstable: It may not maintain the relative order of equal elements.
• Time Complexity: Worst-case and average-case complexity is quadratic (O(n^2)), making it less
efficient for large datasets compared to other sorting algorithms like Quick Sort or Merge Sort.

Let me know if you'd like to make any further changes!

Here’s a refined version of your article on Counting Sort:

Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that works by counting the frequency of
elements within a specific range. This technique calculates the position of each element in the output
sequence by counting the occurrences of distinct keys.

How Counting Sort Works:

To illustrate how Counting Sort operates, let’s consider an example with input data in the range of 0 to 9.

Input Data:
1, 4, 1, 2, 7, 5, 2

Step-by-Step Process:

1. Count Occurrences:
First, we create a count array to store the frequency of each unique element.
 Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 2 0 1 1 0 1 0 0

This count array shows that:

o The element 1 appears 2 times.

o The element 2 appears 2 times.
o The element 4 appears 1 time, and so on.
2. Modify Count Array:
Next, modify the count array so that each element stores the cumulative count of all previous
elements. This will help us determine the correct position of each element in the sorted output.

Index: 0 1 2 3 4 5 6 7 8 9
Count: 0 2 4 4 5 6 6 7 7 7

The modified count array indicates the final positions of each element in the sorted sequence.

3. Construct Output Array:

Now, we place each element from the input array into its correct position in the output array, based
on the modified count array:
o For the first occurrence of 1, its position is 2 in the output array.
o For the second occurrence of 1, its position is 1 (we decrement the count of 1).
o This continues for all elements in the input sequence.

Example:

Let’s process the input sequence 1, 4, 1, 2, 7, 5, 2. For each element, we find its position in the
output sequence using the modified count array and place it accordingly, adjusting the count for each
element after placement.

Implementation (C++):

void countSort(vector<int>& arr)

{
// Find the maximum and minimum elements in the array
int max = *max_element([Link](), [Link]());
int min = *min_element([Link](), [Link]());

// Range of input data

int range = max - min + 1;

// Create count and output arrays

vector<int> count(range), output([Link]());

// Count occurrences of each element

for (int i = 0; i < [Link](); i++)
count[arr[i] - min]++;

// Modify the count array to store cumulative counts

for (int i = 1; i < [Link](); i++)
count[i] += count[i - 1];

// Place the elements into the output array in sorted order

for (int i = [Link]() - 1; i >= 0; i--)
{
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
 // Copy the sorted elements into the original array
for (int i = 0; i < [Link](); i++)
arr[i] = output[i];
}

Time and Space Complexity:

• Time Complexity: O(N + K)

Where N is the number of elements in the input array, and K is the range of input data. This makes
Counting Sort efficient when the range of input values is not significantly larger than the number of
elements.
• Auxiliary Space: O(N + K)
Counting Sort requires extra space for the count array and the output array. The space complexity is
proportional to both the size of the input and the range of input data.

Key Points:

• Efficient for Small Ranges: Counting Sort is particularly efficient when the range of input data is
not much larger than the number of elements to be sorted. For example, sorting numbers in a small
range (like 1 to 10) works well, but if the range is much larger, the space complexity becomes
impractical.
• Not Comparison-Based: Unlike algorithms such as QuickSort or MergeSort, Counting Sort does
not rely on comparisons between elements, which can make it faster for certain types of data.
• Non-Comparison Sorting: Running time complexity is linear, O(N + K), where N is the number of
elements, and K is the range of the input data.
• Negative Numbers Handling: The original version of Counting Sort does not work well with
negative numbers because array indices must be non-negative. However, by shifting all the input
data by the minimum value, we can handle negative inputs effectively.
• Subroutine for Other Algorithms: Counting Sort is often used as a subroutine for other sorting
algorithms, such as Radix Sort.
• Partial Hashing: It uses partial hashing to count the occurrences of each data object in constant time
O(1).

Extensions and Considerations:

Counting Sort can be extended to work with negative input values by adjusting the index positions. For
example, by shifting all the values in the input array to be non-negative (by adding the absolute value of the
minimum element), the algorithm can handle negative integers as well.

Let me know if you'd like any further refinements or additions!

Heap Sort

Heap sort is a comparison-based sorting algorithm that works by utilizing the binary heap data structure. It
is somewhat similar to selection sort, where we find the maximum (or minimum) element and place it at the
end of the array, repeating the process for the remaining elements.

What is a Binary Heap?

A Binary Heap is a complete binary tree that satisfies the heap property:

• Max-Heap: In a max-heap, the value of each parent node is greater than or equal to the values of its
children.
• Min-Heap: In a min-heap, the value of each parent node is less than or equal to the values of its
children.

Binary heaps are often represented as arrays because they allow efficient access to the parent and child
nodes.

Array-based Representation of a Binary Heap

A binary heap is a complete binary tree, and it can be represented using an array where:

• For a node at index i:

o The left child is at index 2 * i + 1
o The right child is at index 2 * i + 2
o The parent node is at index (i - 1) / 2 (for zero-based indexing)

Heap Sort Algorithm

Heap sort works by repeatedly building a max-heap and removing the largest element to place it at the end
of the array, reducing the heap size each time. The process consists of two main parts:

1. Building a Max-Heap: Convert the input array into a max-heap using the heapify process.
2. Sorting the Array: Extract the root (maximum element), swap it with the last element, reduce the
heap size, and heapify the root again to maintain the heap property. Repeat until the heap size is 1.

Heapify Procedure

Heapify is the process of ensuring that the binary tree rooted at a given node satisfies the heap property (in
this case, a max-heap). The algorithm works by comparing the node with its children and swapping it with
the larger of the two children, then recursively applying the heapify procedure.

Heap Sort Algorithm for Sorting in Ascending Order

1. Build the max-heap from the input data.

2. The root of the max-heap (index 0) will be the largest element. Swap the root with the last element
in the heap, then reduce the heap size by 1.
3. Heapify the root element to maintain the max-heap property.
4. Repeat this process until the heap size is greater than 1.

Step-by-Step Example:

Input: [4, 10, 3, 5, 1]

1. Build Max-Heap:
o Initially, the array is: [4, 10, 3, 5, 1]
o Heapify starting from the last non-leaf node. After heapifying, the array becomes: [10, 5,
3, 4, 1] (This is the max-heap).
2. Sort the Array:
o Swap the root (10) with the last element (1). Array becomes [1, 5, 3, 4, 10].
o Reduce the heap size by 1 and heapify the root (1). After heapifying, the array becomes [5,
4, 3, 1, 10].
 o Swap the root (5) with the last element (1). Array becomes [1, 4, 3, 5, 10].
o Reduce the heap size by 1 and heapify the root (1). After heapifying, the array becomes [4,
1, 3, 5, 10].
o Swap the root (4) with the last element (1). Array becomes [1, 4, 3, 5, 10].
o Continue heapifying until the heap size becomes 1.

The final sorted array will be [1, 3, 4, 5, 10].

C++ Code Implementation for Heap Sort

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

// Heapify a subtree rooted at index i (n is the size of the heap)

void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int left = 2 * i + 1; // left = 2 * i + 1
int right = 2 * i + 2; // right = 2 * i + 2

// If left child is larger than root

if (left < n && arr[left] > arr[largest]) {
largest = left;
}

// If right child is larger than largest so far

if (right < n && arr[right] > arr[largest]) {
largest = right;
}

// If largest is not root, swap with largest and heapify the affected subtree
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}

// Heap sort function

void heapSort(int arr[], int n) {
// Build a max-heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}

// One by one extract elements from the heap

for (int i = n - 1; i >= 1; i--) {
// Swap current root with the last element
swap(arr[0], arr[i]);

// Call heapify on the reduced heap

heapify(arr, i, 0);
}
}

// Function to print the array

void printArray(int arr[], int size) {
for (int i = 0; i < size; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
 cout << "Original Array: ";
printArray(arr, n);

heapSort(arr, n);

cout << "Sorted Array: ";

printArray(arr, n);

return 0;
}

Explanation of the Code:

1. heapify():
o This function ensures that the subtree rooted at index i follows the heap property. It
compares the node with its children, swaps if necessary, and recursively heapifies the
affected subtree.
2. heapSort():
o The function first builds a max-heap from the input array by calling heapify starting from
the last non-leaf node (i.e., index n/2 - 1).
o Then, it repeatedly swaps the root of the heap with the last element, reduces the heap size,
and calls heapify to maintain the heap property.
3. printArray():
o A helper function to print the contents of the array.

Output Example:

For the input array [4, 10, 3, 5, 1], the output will be:

Original Array: 4 10 3 5 1
Sorted Array: 1 3 4 5 10

Time Complexity:

• Heapify: Each heapify operation takes O(log N) time, and there are N elements, so heapifying the
entire array takes O(N log N).
• Building the Heap: The initial heap construction involves N/2 calls to heapify, each costing O(log
N), which results in O(N) time for heap construction.
• Overall Time Complexity: The total time complexity for heap sort is O(N log N), where N is the
number of elements.

Space Complexity:

• Heap sort is an in-place algorithm, meaning it doesn't require additional storage for sorting the array.
• The space complexity is O(log N) due to the recursion stack used by the heapify function.
However, if implemented iteratively, the auxiliary space could be reduced to O(1).

Conclusion:

Heap sort is an efficient sorting algorithm with a time complexity of O(N log N) and is particularly useful
for situations where memory usage is a concern, as it is an in-place algorithm. However, in practice, it is
often outperformed by quicksort and merge sort, which can be faster for practical cases. Nonetheless, the
binary heap data structure itself is widely used in applications such as priority queues and scheduling
algorithms.
Here’s a more polished version of your article on Radix Sort:

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that is often used when the range of elements is
large. It is especially effective when sorting integers or strings by processing digits or characters one at a
time. Unlike comparison-based algorithms like Merge Sort or QuickSort, which have a lower bound of Ω(n
log n), Radix Sort can offer better performance under certain conditions.

Why Radix Sort?

For example, if the elements are in the range from 1 to n^2, we cannot use Counting Sort, as it would take
O(n^2) time, which is worse than comparison-based sorting algorithms. Instead, Radix Sort can handle such
scenarios efficiently.

The key idea of Radix Sort is to perform a digit-by-digit sort, starting from the least significant digit (LSD)
to the most significant digit (MSD). It uses Counting Sort or any stable sorting algorithm as a subroutine to
sort based on individual digits.

Radix Sort Algorithm

The algorithm proceeds in the following manner:

1. Start with the least significant digit (LSD):

Sort the numbers based on the least significant digit.
2. Move to the next digit:
Sort the numbers based on the next significant digit (tens place, hundreds place, etc.).
3. Repeat until the most significant digit (MSD):
Continue sorting the numbers by each digit from LSD to MSD.

Example:

Consider the following list of numbers:

170, 45, 75, 90, 802, 24, 2, 66

Sorting Process:

1. Sorting by the unit place (1s place):

The sorted array after considering the unit place is:
2. [170, 90, 802, 2, 24, 45, 75, 66]
3. Sorting by the tens place (10s place):
The sorted array after considering the tens place is:
4. [802, 2, 24, 45, 66, 170, 75, 90]
5. Sorting by the hundreds place (100s place):
The sorted array after considering the hundreds place is:
6. [2, 24, 45, 66, 75, 90, 170, 802]

After processing all digits, the final sorted array is:

[2, 24, 45, 66, 75, 90, 170, 802]

Time Complexity of Radix Sort:

The time complexity of Radix Sort depends on two factors:

• n: the number of elements in the input array.

• d: the number of digits in the largest number.

The algorithm runs in O(d * (n + b)) time, where:

• d is the number of digits (logarithmic in terms of the size of the numbers),

• n is the number of elements,
• b is the base for representing numbers (for decimal numbers, b = 10).

Simplifying for Large Inputs:

• If k is the maximum possible number, then d = O(log_b(k)), so the time complexity becomes O((n
+ b) * log_b(k)). This is still better than comparison-based algorithms when k is large and the
base b is chosen wisely.
• To achieve linear time complexity (O(n)), we can increase the base b. If b = n, the time complexity
becomes O(n), making Radix Sort an optimal choice for large datasets, especially when the range of
numbers is large.

Applications of Radix Sort:

• Sorting on Multiple Keys:

Radix Sort is used in scenarios where data records are keyed by multiple fields. For example, to sort
records by date, we could first sort by day, then month, and finally year, using Radix Sort for each
key.
• Historical Use:
Radix Sort was used in early card sorting machines, where the machine could punch holes in specific
columns (each representing a digit). The cards were sorted based on the punched positions, making it
highly efficient for such tasks.

How Radix Sort Works:

To sort the array [170, 45, 75, 90, 802, 24, 2, 66] using Radix Sort, follow these steps:

Step 1: Find the largest element.

The largest number is 802, which has three digits. We will iterate three times (once for each significant
place).

Step 2: Sort based on the unit place.

Perform Counting Sort based on the unit place digits:

[170, 90, 802, 2, 24, 45, 75, 66]

Step 3: Sort based on the tens place.

Perform Counting Sort based on the tens place digits:

[802, 2, 24, 45, 66, 170, 75, 90]

Step 4: Sort based on the hundreds place.

Perform Counting Sort based on the hundreds place digits:

[2, 24, 45, 66, 75, 90, 170, 802]

Now the array is fully sorted in ascending order:

[2, 24, 45, 66, 75, 90, 170, 802]

C++ Implementation of Radix Sort:

#include <iostream>
using namespace std;

// Function to get the maximum value in the array

int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// Counting sort based on the digit represented by exp

void countSort(int arr[], int n, int exp)
{
int output[n]; // Output array
int i, count[10] = { 0 };

// Count occurrences of each digit

for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Store cumulative count

for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array

for (i = n - 1; i >= 0; i--)
{
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Copy the sorted elements into the original array

for (i = 0; i < n; i++)
arr[i] = output[i];
}

// Main function to implement Radix Sort

void radixSort(int arr[], int n)
{
// Get the maximum number to determine the number of digits
int m = getMax(arr, n);

// Do counting sort for every digit

for (int exp = 1; m / exp > 0; exp *= 10)
 countSort(arr, n, exp);
}

int main()
{
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]);

radixSort(arr, n);

cout << "Sorted array: ";

for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;

return 0;
}

Complexity Analysis of Radix Sort:

• Time Complexity:
Radix Sort has a time complexity of O(d * (n + b)), where:
o d is the number of digits (logarithmic in terms of the largest number),
o n is the number of elements,
o b is the base of the number system (for decimal numbers, b = 10).

In practice, Radix Sort often outperforms comparison-based algorithms (such as QuickSort and
MergeSort) when the range of digits is small and the dataset is large.

• Auxiliary Space Complexity:

Radix Sort has an auxiliary space complexity of O(n + b), where n is the number of elements and b
is the base of the number system. This space is required for the output array and the counting array.

Radix Sort is an efficient sorting technique for large datasets, especially when the elements have a smaller
range or fewer digits. It is a non-comparison-based sorting algorithm, making it a valuable tool in specific
applications, like sorting integers or strings with known ranges.

Bucket Sort

Bucket Sort is a non-comparison-based sorting algorithm that is particularly effective when the input data is
uniformly distributed across a range. It is most useful when sorting floating-point numbers that lie in a
known range, for example, numbers in the range from 0.0 to 1.0.

In typical comparison-based sorting algorithms like Merge Sort, Quick Sort, or Heap Sort, the best-case time
complexity is Ω(n log n), which means they can't perform better than n log n comparisons in the average or
best case. However, bucket sort can achieve linear time complexity O(n), provided certain conditions are
met, such as a uniform distribution of the elements in the input.

Bucket Sort Algorithm

The Bucket Sort algorithm works as follows:

1. Create Empty Buckets: Create an array of empty buckets (or lists) to group the input numbers
based on their values.
 2. Distribute Elements into Buckets: For each element in the array, assign it to a bucket based on its
value.
3. Sort Individual Buckets: Sort the elements within each bucket. Since the number of elements in a
bucket is small, a simple sorting algorithm like Insertion Sort can be used efficiently for this
purpose.
4. Concatenate the Buckets: After all buckets are sorted, concatenate the elements from all the
buckets to get the final sorted array.

Algorithm Steps

1. Create n empty buckets. Each bucket will hold the numbers that fall into a specific range.
2. Place each element arr[i] in a bucket. The index of the bucket is determined by n * arr[i],
where n is the total number of buckets. The bucket index will depend on the element's value.
3. Sort each individual bucket. The sorting within each bucket can be done using any efficient sorting
algorithm (Insertion Sort is commonly used here due to the small size of the buckets).
4. Concatenate the sorted buckets to obtain the final sorted array.

Time Complexity

• Step 1: Creating n empty buckets takes O(n) time.

• Step 2: Placing each element in a bucket takes O(1) time for each element, so overall it takes O(n)
time.
• Step 3: Sorting the elements inside the buckets is the most crucial step. If the elements are uniformly
distributed, the average number of elements in each bucket will be O(1), and sorting each bucket
using Insertion Sort will take O(1) time on average for each element. So this step will take O(n) time
in total.
• Step 4: Concatenating the sorted buckets also takes O(n) time.

Thus, the overall average time complexity of Bucket Sort is O(n), provided that the elements are uniformly
distributed across the range.

However, in the worst-case scenario, if all elements fall into a single bucket, the time complexity can
degrade to O(n^2) due to the sorting of the elements in a single bucket (this happens when the elements are
not uniformly distributed).

Space Complexity

The space complexity of bucket sort is O(n + k), where:

• O(n) is the space needed to store the n elements in the buckets.

• O(k) is the space for the buckets themselves, where k is the number of buckets.

Example

Suppose we want to sort the following array of floating-point numbers in the range from 0.0 to 1.0:

Input: [0.1234, 0.3434, 0.656, 0.897, 0.665, 0.565]

• Step 1: Create empty buckets. Let's assume we create 6 buckets, one for each decimal range (e.g.,
0.0 to 0.1, 0.1 to 0.2, etc.).
• Step 2: Place each element in the appropriate bucket. The bucket index for each number is calculated
as n * arr[i].
o For 0.1234, the bucket index is 6 * 0.1234 = 0.7404 (put it in the 1st bucket).
o Repeat this process for all elements.
• Step 3: Sort the individual buckets (we can use Insertion Sort).
 • Step 4: Concatenate the sorted buckets to get the final sorted array.

C++ Implementation of Bucket Sort

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

// Function to perform bucket sort

void bucketSort(float arr[], int n)
{
// 1) Create n empty buckets
vector<float> b[n];

// 2) Put array elements in different buckets

for (int i = 0; i < n; i++) {
int bi = n * arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}

// 3) Sort individual buckets using Insertion Sort

for (int i = 0; i < n; i++) {
sort(b[i].begin(), b[i].end());
}

// 4) Concatenate all sorted buckets

int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < b[i].size(); j++) {
arr[index++] = b[i][j];
}
}
}

// Function to print the array

void printArray(float arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

int main() {
float arr[] = {0.1234, 0.3434, 0.656, 0.897, 0.665, 0.565};
int n = sizeof(arr) / sizeof(arr[0]);

cout << "Original array: ";

printArray(arr, n);

bucketSort(arr, n);

cout << "Sorted array: ";

printArray(arr, n);

return 0;
}

Output:
Original array: 0.1234 0.3434 0.656 0.897 0.665 0.565
Sorted array: 0.1234 0.3434 0.565 0.656 0.665 0.897

Key Points to Remember:

 1. Bucket Sort is efficient when the input is uniformly distributed over a range.
2. It can achieve linear time complexity O(n), which is faster than comparison-based algorithms in
specific cases.
3. It is often used when sorting floating-point numbers, especially when the numbers are uniformly
distributed across a known range.
4. If the input data is not uniformly distributed, the worst-case time complexity can degrade to O(n²).

Applications:

• Bucket sort is particularly useful in situations where the data is uniformly distributed, such as:
o Sorting floating-point numbers in a known range.
o Sorting large datasets like grading systems (e.g., assigning ranks based on percentiles).
o Sorting hash functions in distributed systems.