Algorithms and Problem Solving with Java
Simple Sorting Algorithms
You are viewing a free preview lesson.
Lesson Overview
Sorting means values-কে একটি নির্দিষ্ট order-এ arrange করা।
Example:
40 10 30 20
ascending order:
10 20 30 40
descending order:
40 30 20 10
Sorting গুরুত্বপূর্ণ কারণ sorted data অনেক operation সহজ করে।
Examples:
Binary Search
Finding minimum/maximum positions
Displaying ranked results
Grouping similar values
Detecting boundaries
Merging ordered datasets
Java already provides:
Arrays.sort(...)
তবুও manual sorting algorithms শেখা গুরুত্বপূর্ণ।
কারণ এগুলো আমাদের শেখায়:
- How comparisons drive algorithms
- How values are swapped
- How loops cooperate
- How sorted and unsorted regions change
- Why some algorithms are
O(n²) - Why better algorithms are needed for large input
এই lesson-এ আমরা শিখব:
- What sorting means
- Comparison-based sorting
- Swapping
- Bubble Sort
- Selection Sort
- Insertion Sort
- Step-by-step tracing
- Time complexity
- Space complexity
- In-place sorting
- Stability intuition
- When simple sorts are useful
- Why production code usually uses library sorting
What Is Sorting?
Suppose:
int[] numbers = {
40,
10,
30,
20
};
Ascending sorting transforms it into:
10
20
30
40
The original values remain the same।
Only their order changes।
Sorting Order
Common sorting orders include:
Ascending
Descending
Alphabetical
Date order
Price order
Priority order
For objects, the sorting rule may depend on a field।
Example:
Course by price
Learner by name
Enrollment by creation time
Later we will use:
Comparable
Comparator
to define custom ordering।
Comparison-Based Sorting
The algorithms in this lesson use comparisons such as:
first > second
or:
first < second
They decide ordering by comparing values।
These are called:
Comparison-based sorting algorithms
Swapping Values
Sorting algorithms frequently swap two array elements।
Suppose:
int[] numbers = {
40,
10
};
We want:
10
40
A swap requires a temporary variable।
Swap Example
int temporary =
numbers[0];
numbers[0] =
numbers[1];
numbers[1] =
temporary;
Result:
10 40
Why Do We Need a Temporary Variable?
Incorrect:
numbers[0] =
numbers[1];
numbers[1] =
numbers[0];
Suppose:
numbers[0] = 40
numbers[1] = 10
After first assignment:
numbers[0] = 10
numbers[1] = 10
The original 40 has been lost।
So we temporarily preserve one value।
Reusable Swap Method
We can create:
static void swap(
int[] numbers,
int firstIndex,
int secondIndex
) {
int temporary =
numbers[firstIndex];
numbers[firstIndex] =
numbers[secondIndex];
numbers[secondIndex] =
temporary;
}
Then sorting algorithms can call:
swap(
numbers,
i,
j
);
Bubble Sort
Bubble Sort repeatedly compares neighboring values।
If they are in the wrong order, it swaps them।
Example:
40 10 30 20
Compare:
40 and 10
Wrong order:
40 > 10
Swap:
10 40 30 20
Continue the Pass
Now compare:
40 and 30
Swap:
10 30 40 20
Then:
40 and 20
Swap:
10 30 20 40
After one full pass:
40
has moved to its final position।
Why "Bubble" Sort?
Large values gradually move toward the end through repeated neighboring swaps।
Conceptually they "bubble" toward their correct side।
Bubble Sort Implementation
static void bubbleSort(
int[] numbers
) {
for (
int pass = 0;
pass < numbers.length - 1;
pass++
) {
for (
int i = 0;
i < numbers.length - 1 - pass;
i++
) {
if (
numbers[i]
> numbers[i + 1]
) {
swap(
numbers,
i,
i + 1
);
}
}
}
}
Why numbers.length - 1 Passes?
For n values, at most:
n - 1
passes are required।
After each pass, one more largest remaining value reaches its final position।
Why Does the Inner Loop Shrink?
Notice:
numbers.length - 1 - pass
After the first pass, the final position is already sorted।
We do not need to compare it again।
Example:
Pass 0
[ ... ... ... 40 ]
sorted
Pass 1
[ ... ... 30 40 ]
sorted
The sorted region grows from the right।
Bubble Sort Trace
Input:
5 3 4 1
Pass 1
Compare:
5 and 3
Swap:
3 5 4 1
Compare:
5 and 4
Swap:
3 4 5 1
Compare:
5 and 1
Swap:
3 4 1 5
Now 5 is final।
Pass 2
Current:
3 4 1 5
Compare:
3 and 4
No swap।
Compare:
4 and 1
Swap:
3 1 4 5
Now:
4 5
are final।
Pass 3
Compare:
3 and 1
Swap:
1 3 4 5
Sorted।
Bubble Sort Complexity
Nested loops make the worst-case time approximately:
O(n²)
Because many neighboring pairs may be compared repeatedly।
Bubble Sort Space
It sorts the same array and uses only a few variables।
Additional space:
O(1)
This is an:
in-place sort
What Is In-Place Sorting?
An in-place sorting algorithm rearranges the original data structure without creating another full n-sized array।
Example:
bubbleSort(
numbers
);
Afterward:
numbers itself is sorted
Optimized Bubble Sort
Suppose input is already sorted:
1 2 3 4 5
The basic implementation still performs all passes।
We can track whether any swap occurred।
Optimized Version
static void bubbleSort(
int[] numbers
) {
for (
int pass = 0;
pass < numbers.length - 1;
pass++
) {
boolean swapped =
false;
for (
int i = 0;
i < numbers.length - 1 - pass;
i++
) {
if (
numbers[i]
> numbers[i + 1]
) {
swap(
numbers,
i,
i + 1
);
swapped =
true;
}
}
if (!swapped) {
return;
}
}
}
Optimized Best Case
For already sorted data, first pass performs:
O(n)
comparisons।
No swaps occur।
Then the algorithm stops।
Best case:
O(n)
Worst case remains:
O(n²)
Bubble Sort Stability
A sorting algorithm is stable if equal elements preserve their original relative order।
Suppose objects are:
A(score=80)
B(score=80)
A stable sort by score keeps:
A before B
if they were originally in that order।
Bubble Sort can be stable when it swaps only when:
left > right
and does not swap equal values।
Why Stability Matters
Suppose learners are already ordered by registration time।
Then you sort by score।
If equal-score learners preserve their earlier registration ordering, the sort is stable।
Stability matters more with objects than primitive integers, but the concept is worth learning now।
Selection Sort
Selection Sort uses a different idea।
Instead of repeatedly swapping neighbors, it finds the smallest remaining value and places it in the next correct position।
Conceptually:
Find smallest
Put it first
Find next smallest
Put it second
Repeat
Selection Sort Example
Input:
40 10 30 20
Find smallest:
10
Swap it with first position:
10 40 30 20
Now first position is final।
Next Round
Unsorted region:
40 30 20
Smallest:
20
Swap with first element of unsorted region:
10 20 30 40
Continue until sorted।
Sorted and Unsorted Regions
Selection Sort conceptually divides the array:
[ sorted | unsorted ]
Initially:
[ | 40 10 30 20 ]
After selecting 10:
[ 10 | 40 30 20 ]
After selecting 20:
[ 10 20 | 30 40 ]
Selection Sort Implementation
static void selectionSort(
int[] numbers
) {
for (
int start = 0;
start < numbers.length - 1;
start++
) {
int minIndex =
start;
for (
int i = start + 1;
i < numbers.length;
i++
) {
if (
numbers[i]
< numbers[minIndex]
) {
minIndex =
i;
}
}
if (
minIndex != start
) {
swap(
numbers,
start,
minIndex
);
}
}
}
Understanding minIndex
At the start of each pass:
int minIndex =
start;
We assume the first unsorted value is the smallest।
Then scan remaining values।
Whenever we find something smaller:
minIndex =
i;
At the end, we know where the minimum value is।
Selection Sort Trace
Input:
5 3 4 1
Round 1
Start:
start = 0
Current minimum:
5
Check:
3 → smaller
min = 3
Check:
4 → no
Check:
1 → smaller
min = 1
Swap 1 into index 0:
1 3 4 5
Round 2
Unsorted:
3 4 5
Minimum is already:
3
No swap required।
Selection Sort Complexity
Selection Sort scans the remaining unsorted region every round।
Approximately:
n + (n - 1) + (n - 2) + ...
Worst case:
O(n²)
Best case:
O(n²)
Even if data is already sorted, it still searches for the minimum in each remaining region।
Selection Sort Space
Additional space:
O(1)
It is in-place।
Selection Sort Swaps
One interesting property:
Selection Sort performs relatively few swaps।
At most roughly:
n - 1
swaps।
Bubble Sort may perform many more swaps।
This can matter conceptually when swapping itself is expensive।
Selection Sort Stability
The common implementation is generally:
Not stable
because swapping a minimum value from far away can change the relative order of equal elements।
Example of Stability Problem
Imagine:
A(2), B(2), C(1)
Selection Sort may move C(1) to the front by swapping with A(2):
C(1), B(2), A(2)
Originally:
A before B
Now:
B before A
The equal elements changed relative order।
Insertion Sort
Insertion Sort uses another mental model।
Imagine sorting playing cards in your hand।
You take one new card and insert it into the correct position among cards already sorted।
Conceptually:
[ sorted region | remaining values ]
Insertion Sort Example
Input:
5 3 4 1
Start:
[5] | 3 4 1
Treat first value as already sorted।
Take:
3
Insert before 5:
[3 5] | 4 1
Next Value
Take:
4
Compare with sorted region:
3 5
Insert between:
3 and 5
Result:
[3 4 5] | 1
Then insert 1:
[1 3 4 5]
Insertion Sort Implementation
static void insertionSort(
int[] numbers
) {
for (
int i = 1;
i < numbers.length;
i++
) {
int current =
numbers[i];
int position =
i - 1;
while (
position >= 0
&& numbers[position]
> current
) {
numbers[position + 1] =
numbers[position];
position--;
}
numbers[position + 1] =
current;
}
}
Understanding the Algorithm
At:
int current =
numbers[i];
we temporarily preserve the value being inserted।
Then:
numbers[position]
> current
means existing sorted values are too large।
We shift them one position to the right।
Finally:
numbers[position + 1] =
current;
places the value into its correct position।
Shift vs Swap
Insertion Sort does not necessarily swap the current value repeatedly।
Instead it often shifts larger values right।
Example:
1 3 5 7 | 4
To insert 4:
Shift:
7 → right
5 → right
Then insert:
4
Result:
1 3 4 5 7
Insertion Sort Trace
Input:
5 3 4 1
i = 1
Current:
3
Compare with:
5
Shift 5:
5 5 4 1
Insert 3:
3 5 4 1
i = 2
Current:
4
Compare with 5।
Shift:
3 5 5 1
Compare with 3।
No need to move 3।
Insert:
3 4 5 1
i = 3
Current:
1
Shift:
5
4
3
to the right।
Result:
1 3 4 5
Insertion Sort Worst Case
Worst input for ascending sorting:
5 4 3 2 1
Every new value may need to move through the entire sorted region।
Worst-case time:
O(n²)
Insertion Sort Best Case
Already sorted:
1 2 3 4 5
For each new value, the while condition quickly fails।
Best-case time:
O(n)
This makes Insertion Sort useful for:
Small datasets
Nearly sorted datasets
Insertion Sort Space
Additional space:
O(1)
It is in-place।
Insertion Sort Stability
The normal implementation using:
numbers[position]
> current
rather than:
>=
does not move equal values past each other।
Therefore it can be:
Stable
Comparing the Three Algorithms
| Algorithm | Best Time | Worst Time | Extra Space | Stable? |
|---|---|---|---|---|
| Bubble Sort | O(n) optimized | O(n²) | O(1) | Yes, common implementation |
| Selection Sort | O(n²) | O(n²) | O(1) | Usually no |
| Insertion Sort | O(n) | O(n²) | O(1) | Yes, common implementation |
Why All Three Are Still O(n²)
Their mechanics differ।
Bubble Sort:
Repeated neighbor comparisons
Selection Sort:
Repeated minimum search
Insertion Sort:
Repeated insertion into sorted prefix
But worst-case work grows quadratically।
Which Simple Sort Is Usually Most Practical?
Among these three, Insertion Sort is often the most practically useful for:
Small input
Nearly sorted input
Small partitions inside larger algorithms
Bubble Sort is mainly educational।
Selection Sort is useful for understanding selection and minimizing swaps, but is not a common production default।
Why Bubble Sort Is Famous
Not because it is a great general-purpose production sorting algorithm।
It is famous because it is very easy to visualize:
Compare neighbors
Swap
Repeat
That makes it useful for teaching sorting mechanics।
Why Selection Sort Is Useful to Learn
It teaches:
Find best candidate
Place it
Grow sorted region
This selection pattern appears in many other algorithms।
Why Insertion Sort Matters
Insertion Sort is especially important because:
It handles small/naturally sorted regions well
and ideas similar to insertion sorting are useful in optimized sorting implementations।
Sorting Descending
The same algorithms can sort descending by reversing the comparison।
Bubble ascending:
if (
numbers[i]
> numbers[i + 1]
)
Descending:
if (
numbers[i]
< numbers[i + 1]
)
Selection Sort Descending
Instead of finding minimum:
Find maximum
and place it at the beginning of the unsorted region।
Insertion Sort Descending
Change:
numbers[position]
> current
to:
numbers[position]
< current
so larger values remain first।
Sorting Strings
Algorithms can also sort strings using comparison methods।
Example:
first.compareTo(
second
)
For ascending natural order:
if (
first.compareTo(
second
) > 0
) {
// first should move after second
}
We will discuss Comparable properly later।
Example Bubble Sort for Strings
static void bubbleSort(
String[] values
) {
for (
int pass = 0;
pass < values.length - 1;
pass++
) {
boolean swapped =
false;
for (
int i = 0;
i < values.length - 1 - pass;
i++
) {
if (
values[i]
.compareTo(
values[i + 1]
) > 0
) {
String temporary =
values[i];
values[i] =
values[i + 1];
values[i + 1] =
temporary;
swapped =
true;
}
}
if (!swapped) {
return;
}
}
}
Sorting Custom Objects
Suppose:
record Course(
String title,
long price
) {
}
We may sort by:
price
or:
title
The algorithm itself only needs a way to answer:
Which of these two should come first?
Later Comparator will let us provide that rule cleanly।
Sorting and Binary Search
Recall Binary Search requires sorted input।
Example:
Unsorted
[40, 10, 30, 20]
Sort
↓
[10, 20, 30, 40]
Binary Search
↓
O(log n) lookup
This is one major reason sorting matters।
But Sorting Has a Cost
If you use Bubble Sort:
O(n²)
just to perform one Binary Search:
O(log n)
the overall operation is still dominated by:
O(n²)
That would usually be worse than one simple:
O(n)
Linear Search।
Efficient Sorting Changes the Tradeoff
With a more efficient sort:
O(n log n)
sorting plus one search is:
O(n log n)
Still more expensive asymptotically than one linear lookup:
O(n)
But sorting can pay off when you perform many future searches।
Sorting Is Often Preprocessing
This is an important algorithmic concept।
Sometimes we perform expensive work once:
Sort data
Build index
Build map
to make future operations much faster।
This is called:
Preprocessing
Example
Without preprocessing:
1000 linear searches
could cost roughly:
1000 × O(n)
With sorted preprocessing:
O(n log n) sort
+
1000 × O(log n) searches
Depending on n and usage pattern, the second strategy can be significantly better।
Stability Example with Objects
Suppose:
Sakib score=90 joined=1
Subu score=80 joined=2
Sumu score=90 joined=3
If original order represents join order and we stable-sort by score descending:
Sakib 90
Sumu 90
Subu 80
Among equal score 90:
Sakib remains before Sumu
A non-stable sort might reverse them।
Stable Sorting Can Preserve Previous Ordering
A useful pattern:
- Sort by secondary criterion.
- Stable-sort by primary criterion.
The secondary ordering can remain for equal primary values।
Modern comparator chaining is often clearer, but stability is still an important property।
Is Stability Relevant for int[]?
Usually not visibly।
If two values are both:
5
you cannot distinguish one 5 from another।
Stability becomes meaningful when elements carry identity or additional fields।
In-Place vs Out-of-Place Sorting
Our three simple algorithms are:
In-place
They mutate the input array।
Example:
selectionSort(
numbers
);
After the call:
numbers is sorted
Preserve Original Data
If original order matters:
int[] sorted =
Arrays.copyOf(
numbers,
numbers.length
);
insertionSort(
sorted
);
Now original remains unchanged।
Sorting API Design
Instead of:
static void sort(
int[] numbers
)
you could design:
static int[] sortedCopy(
int[] numbers
)
which communicates that the original will not be changed।
Example:
static int[] sortedCopy(
int[] numbers
) {
int[] result =
Arrays.copyOf(
numbers,
numbers.length
);
insertionSort(
result
);
return result;
}
Mutation Should Be Intentional
Always ask:
Does the caller expect the original order to change?
Sorting is not just an algorithm decision।
It is also an API design decision।
Java Already Has Arrays.sort()
Production code usually should not write:
bubbleSort(...)
for ordinary sorting।
Prefer:
Arrays.sort(
numbers
);
Why?
Because standard-library implementations are:
Well-tested
Optimized
Familiar
Maintained
Then Why Implement Sorting Manually?
Because implementation teaches:
Nested loops
Comparisons
Swapping
Shifting
Invariant reasoning
Complexity
Sorted-region thinking
Without this foundation, efficient algorithms can feel like magic।
Algorithm Invariant Intuition
An invariant is something that remains true at a particular stage of an algorithm।
You do not need formal proofs yet।
Just learn to identify what the algorithm guarantees।
Bubble Sort Invariant
After each completed pass:
The largest remaining unsorted value
has reached its final position.
Selection Sort Invariant
Before each new round:
Everything before start
is already in final sorted order.
Insertion Sort Invariant
Before processing index i:
The prefix from index 0 to i - 1
is already sorted.
These mental guarantees make algorithms easier to reason about।
Common Mistake 1 — Wrong Swap
Bad:
numbers[i] =
numbers[j];
numbers[j] =
numbers[i];
This loses one value।
Use a temporary variable।
Common Mistake 2 — Bubble Sort Out-of-Bounds
Bad:
for (
int i = 0;
i < numbers.length;
i++
) {
if (
numbers[i]
> numbers[i + 1]
) {
}
}
When:
i = last index
i + 1 is invalid।
Use:
i < numbers.length - 1
or the shrinking pass boundary।
Common Mistake 3 — Forgetting Bubble Sort Passes
One pass does not generally fully sort the array।
Example:
5 4 3 2 1
One pass only guarantees the largest value reaches the end।
Multiple passes are required।
Common Mistake 4 — Swapping During Every Selection Comparison
Selection Sort should normally:
Find the minimum index first
then perform one swap after the scan।
Do not swap every time a smaller value is seen unless you intentionally implement another algorithm।
Common Mistake 5 — Losing the Insertion Value
During Insertion Sort:
int current =
numbers[i];
must be saved before values shift over its original position।
Otherwise the value can be overwritten।
Common Mistake 6 — Wrong Insertion Boundary
This condition:
position >= 0
must be checked before:
numbers[position]
is accessed।
Java's && short-circuit behavior makes this safe:
position >= 0
&& numbers[position] > current
Common Mistake 7 — Calling Every O(n²) Sort Equivalent
They share the same worst-case growth class, but they can behave differently in practice।
Examples:
Bubble Sort may perform many swaps.
Selection Sort performs fewer swaps.
Insertion Sort performs well on nearly sorted data.
Big-O does not capture every constant or input-sensitive behavior।
Common Mistake 8 — Using Manual Sort in Production Without Reason
Educational implementation is valuable।
Production reinvention usually is not।
Prefer Java's standard sorting APIs unless there is a specific algorithmic requirement।
Practical Example — Compare All Three
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] original = {
40,
10,
30,
20
};
int[] bubble =
Arrays.copyOf(
original,
original.length
);
int[] selection =
Arrays.copyOf(
original,
original.length
);
int[] insertion =
Arrays.copyOf(
original,
original.length
);
bubbleSort(
bubble
);
selectionSort(
selection
);
insertionSort(
insertion
);
System.out.println(
Arrays.toString(
bubble
)
);
System.out.println(
Arrays.toString(
selection
)
);
System.out.println(
Arrays.toString(
insertion
)
);
}
static void bubbleSort(
int[] numbers
) {
for (
int pass = 0;
pass < numbers.length - 1;
pass++
) {
boolean swapped =
false;
for (
int i = 0;
i < numbers.length - 1 - pass;
i++
) {
if (
numbers[i]
> numbers[i + 1]
) {
swap(
numbers,
i,
i + 1
);
swapped =
true;
}
}
if (!swapped) {
return;
}
}
}
static void selectionSort(
int[] numbers
) {
for (
int start = 0;
start < numbers.length - 1;
start++
) {
int minIndex =
start;
for (
int i = start + 1;
i < numbers.length;
i++
) {
if (
numbers[i]
< numbers[minIndex]
) {
minIndex =
i;
}
}
if (
minIndex != start
) {
swap(
numbers,
start,
minIndex
);
}
}
}
static void insertionSort(
int[] numbers
) {
for (
int i = 1;
i < numbers.length;
i++
) {
int current =
numbers[i];
int position =
i - 1;
while (
position >= 0
&& numbers[position]
> current
) {
numbers[position + 1] =
numbers[position];
position--;
}
numbers[position + 1] =
current;
}
}
static void swap(
int[] numbers,
int firstIndex,
int secondIndex
) {
int temporary =
numbers[firstIndex];
numbers[firstIndex] =
numbers[secondIndex];
numbers[secondIndex] =
temporary;
}
}
Output:
[10, 20, 30, 40]
[10, 20, 30, 40]
[10, 20, 30, 40]
All solve the same problem through different strategies।
Practice 1 — Swap
Given:
int[] values = {
10,
20
};
swap the values।
Solution
int temporary =
values[0];
values[0] =
values[1];
values[1] =
temporary;
Result:
20 10
Practice 2 — Bubble Sort Pass
Given:
4 2 3 1
What does the array look like after one full Bubble Sort pass?
Step 1
4 2
swap:
2 4 3 1
Step 2
4 3
swap:
2 3 4 1
Step 3
4 1
swap:
2 3 1 4
Answer
2 3 1 4
The largest value 4 reached the end।
Practice 3 — Selection Sort First Round
Input:
8 3 5 1
What is the first selected value?
Answer
1
After first swap:
1 3 5 8
Practice 4 — Insertion Sort Prefix
Input:
3 5 7 4 9
Suppose:
3 5 7
is already sorted and current value is:
4
What happens?
Answer
Shift:
7
5
as needed।
Final prefix:
3 4 5 7
Practice 5 — Complexity
What is Bubble Sort worst-case complexity?
Answer
O(n²)
Practice 6 — Complexity
What is Selection Sort best-case complexity in its standard implementation?
Answer
O(n²)
It still scans the remaining values to find each minimum।
Practice 7 — Complexity
What is Insertion Sort best-case complexity for already sorted input?
Answer
O(n)
Practice 8 — Space
What is additional space complexity for these in-place implementations?
Answer
O(1)
Practice 9 — Stability
Which of these common implementations are stable?
Answer
Bubble Sort → Yes
Selection Sort → Usually no
Insertion Sort → Yes
Practice 10 — Choose an Algorithm
You have 12 nearly sorted values and must implement sorting manually for an exercise।
Which simple sort is a reasonable choice?
Answer
Insertion Sort
because it performs especially well on small, nearly sorted input।
Practice 11 — Production Choice
You need to sort one million integers in normal application code।
Which should you choose?
Bubble Sort
Selection Sort
Insertion Sort
Arrays.sort()
Answer
Normally:
Arrays.sort()
Do not manually use these basic educational algorithms for a large general-purpose production sort।
Practice 12 — Mutation
Given:
int[] numbers = {
3,
2,
1
};
insertionSort(
numbers
);
Does the original array change?
Answer
Yes।
The implementation sorts in place।
True or False
- Sorting changes element order.
- Bubble Sort compares neighboring elements.
- Bubble Sort guarantees the whole array is sorted after one pass.
- Selection Sort repeatedly finds a minimum from the unsorted region.
- Selection Sort standard implementation is
O(n)on already sorted input. - Insertion Sort grows a sorted prefix.
- Insertion Sort can have
O(n)best-case behavior. - All three simple sorts have
O(n²)worst-case complexity. - All three implementations shown require
O(n)additional arrays. - Bubble Sort can be stable.
- Standard Selection Sort is normally stable.
- Insertion Sort can be stable.
Arrays.sort()is usually preferable for ordinary production sorting.- Sorting before one Binary Search is always beneficial.
Answers
1. True
2. True
3. False
4. True
5. False
6. True
7. True
8. True
9. False
10. True
11. False
12. True
13. True
14. False
Knowledge Check
Question 1
What is sorting?
Question 2
What is a swap?
Question 3
What does Bubble Sort guarantee after one complete pass?
Question 4
Why can optimized Bubble Sort reach O(n) best-case time?
Question 5
How does Selection Sort choose the next element?
Question 6
Why is Selection Sort still O(n²) for already sorted input?
Question 7
How does Insertion Sort differ conceptually from Selection Sort?
Question 8
Why can Insertion Sort be good for nearly sorted data?
Question 9
What does in-place sorting mean?
Question 10
What does stable sorting mean?
Question 11
Why is stability more meaningful for objects than primitive numbers?
Question 12
Why do we learn these algorithms if Arrays.sort() already exists?
Knowledge Check Answers
Answer 1
Sorting arranges values according to a defined ordering rule such as ascending or descending order।
Answer 2
A swap exchanges the values stored at two positions, usually using a temporary variable to avoid losing one value।
Answer 3
The largest value in the current unsorted region reaches its final position at the end of that pass।
Answer 4
If a full pass performs no swaps, the array is already sorted, so the optimized implementation can stop after one linear scan।
Answer 5
It scans the unsorted region to find the smallest remaining element and places that element at the beginning of the unsorted region।
Answer 6
It still scans the remaining unsorted region on every pass to verify which element is smallest।
Answer 7
Selection Sort selects the next smallest value from the remaining data, while Insertion Sort takes the next value and inserts it into the correct position inside an already-sorted prefix।
Answer 8
Very few elements need to shift when most values are already near their correct positions।
Answer 9
The algorithm rearranges the original array using only a small constant amount of extra memory instead of creating another full-size array।
Answer 10
A stable sort preserves the original relative ordering of elements that compare as equal।
Answer 11
Two primitive values such as 5 and 5 are indistinguishable, while equal-key objects may still have different identities or other fields whose previous ordering matters।
Answer 12
Manual implementation teaches comparison, swapping, shifting, invariants, nested-loop complexity, and the reasoning needed to understand more efficient sorting algorithms।
Sorting Comparison Summary
Bubble Sort
Core idea:
Compare neighbors
Swap if out of order
Largest value moves right each pass
Complexity:
Best: O(n) optimized
Worst: O(n²)
Space: O(1)
Good for:
Learning
Visualization
Very small educational examples
Selection Sort
Core idea:
Find smallest remaining value
Place it next
Complexity:
Best: O(n²)
Worst: O(n²)
Space: O(1)
Good for:
Learning selection logic
Cases where minimizing swaps matters conceptually
Insertion Sort
Core idea:
Maintain sorted prefix
Insert next value into correct position
Complexity:
Best: O(n)
Worst: O(n²)
Space: O(1)
Good for:
Small datasets
Nearly sorted data
Understanding incremental sorting
Lesson Summary
এই lesson-এ আমরা sorting-এর core mechanics শিখেছি।
We learned:
- Sorting arranges values according to an ordering rule
- Comparison-based algorithms decide order by comparing elements
- Swapping requires preserving one value temporarily
- Bubble Sort repeatedly compares neighboring values
- Bubble Sort gradually grows a sorted region from the right
- Optimized Bubble Sort can stop when no swaps occur
- Selection Sort repeatedly finds the minimum remaining value
- Selection Sort grows a sorted region from the left
- Insertion Sort inserts each new value into an already sorted prefix
- Insertion Sort often performs well on small or nearly sorted input
- All three algorithms have
O(n²)worst-case complexity - Bubble and Insertion Sort can have
O(n)best-case behavior under suitable conditions - Selection Sort remains
O(n²)in the standard version - The implementations shown use
O(1)extra space - Stable sorting preserves relative order among equal elements
- Sorting can mutate original data, so copies may be needed
- Sorting is often preprocessing for faster future operations
- Java's standard sorting APIs should normally be preferred in production
The core mental models are:
Bubble Sort
→ move large values through neighbors
Selection Sort
→ repeatedly select the smallest remaining value
Insertion Sort
→ insert each value into a sorted prefix
These algorithms are not the end goal।
They prepare us to understand why more scalable sorting algorithms are necessary।
Next Lesson
পরবর্তী lesson:
Merge Sort and Quick Sort
আমরা শিখব:
- Why
O(n²)sorting becomes expensive - Divide and conquer
- Merge Sort
- Splitting arrays
- Merging sorted ranges
- Recursive execution
O(n log n)complexity- Merge Sort space tradeoff
- Quick Sort
- Pivot selection
- Partitioning
- Recursive subranges
- Average
O(n log n) - Worst-case
O(n²) - Merge Sort vs Quick Sort
- Why production sorting implementations are more sophisticated than textbook versions