Insertion Sort Research and Algorithm.pdf

Insertion Sort Research and Algorithm.pdf

1. INSERTION
SORT
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
Castañares. Eva Mae C.
Group 4
WHAT IS
INSERTION SORT?
Insertion Sort is a
simple sorting
algorithm that builds
the final sorted array
one item at a time. It’s
similar to how you
would sort playing
cards in your hand. In
each step, it takes one
element from the input
data, finds the correct
position within the
sorted elements, and
inserts it there.
Here’s how it works
step-by-step:
1.Start from the
second element
(the first element
is trivially sorted
by itself).
2.Take the current
element and
compare it with
elements in the
sorted portion to
its left.
3.Shift each larger
element one
position to the
right to make
space for the
current element.
4.Insert the current
element in its
correct position.
5.Repeat until the
entire array is
sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so
swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so
swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so
no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so
swap them.
•Compare 1 with 5: 1 is smaller than 5, so
swap them.
•Compare 1 with 4: 1 is smaller than 4, so
swap them.
•Compare 1 with 2: 1 is smaller than 2, so
swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so
swap them.
•Compare 3 with 5: 3 is smaller than 5, so
swap them.
•Compare 3 with 4: 3 is smaller than 4, so
swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion
Sort:
∙Time Complexity:
Best case:
O(n) when
the array is
already
sorted.
Average and
worst case:
O(n^2), when
elements are
in reverse
order.
∙Space
Complexity: O(1)
making it an
in-place sorting
algorithm.
∙Stability: Yes, it
maintains the
relative order of
equal elements.

Advantages:
•Simple and easy to
implement.
•Efficient for small or
nearly sorted
datasets.

Disadvantages:
•Inefficient for large
datasets compared
to more advanced
algorithms like
quicksort or
mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

2. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works
step-by-step:
1.Start from the
second element
(the first element
is trivially sorted
by itself).
2.Take the current
element and
compare it with
elements in the
sorted portion to
its left.
3.Shift each larger
element one
position to the
right to make
space for the
current element.
4.Insert the current
element in its
correct position.
5.Repeat until the
entire array is
sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so
swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so
swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so
no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so
swap them.
•Compare 1 with 5: 1 is smaller than 5, so
swap them.
•Compare 1 with 4: 1 is smaller than 4, so
swap them.
•Compare 1 with 2: 1 is smaller than 2, so
swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so
swap them.
•Compare 3 with 5: 3 is smaller than 5, so
swap them.
•Compare 3 with 4: 3 is smaller than 4, so
swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion
Sort:
∙Time Complexity:
Best case:
O(n) when
the array is
already
sorted.
Average and
worst case:
O(n^2), when
elements are
in reverse
order.
∙Space
Complexity: O(1)
making it an
in-place sorting
algorithm.
∙Stability: Yes, it
maintains the
relative order of
equal elements.

Advantages:
•Simple and easy to
implement.
•Efficient for small or
nearly sorted
datasets.

Disadvantages:
•Inefficient for large
datasets compared
to more advanced
algorithms like
quicksort or
mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

3. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works step-by-step:
1.Start from the second element (the first element is trivially
sorted by itself).
2.Take the current element and compare it with elements in the
sorted portion to its left.
3.Shift each larger element one position to the right to make
space for the current element.
4.Insert the current element in its correct position.
5.Repeat until the entire array is sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so
swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so
swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so
no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so
swap them.
•Compare 1 with 5: 1 is smaller than 5, so
swap them.
•Compare 1 with 4: 1 is smaller than 4, so
swap them.
•Compare 1 with 2: 1 is smaller than 2, so
swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so
swap them.
•Compare 3 with 5: 3 is smaller than 5, so
swap them.
•Compare 3 with 4: 3 is smaller than 4, so
swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion
Sort:
∙Time Complexity:
Best case:
O(n) when
the array is
already
sorted.
Average and
worst case:
O(n^2), when
elements are
in reverse
order.
∙Space
Complexity: O(1)
making it an
in-place sorting
algorithm.
∙Stability: Yes, it
maintains the
relative order of
equal elements.

Advantages:
•Simple and easy to
implement.
•Efficient for small or
nearly sorted
datasets.

Disadvantages:
•Inefficient for large
datasets compared
to more advanced
algorithms like
quicksort or
mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

4. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works step-by-step:
1.Start from the second element (the first element is trivially
sorted by itself).
2.Take the current element and compare it with elements in the
sorted portion to its left.
3.Shift each larger element one position to the right to make
space for the current element.
4.Insert the current element in its correct position.
5.Repeat until the entire array is sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so swap them.
•Compare 1 with 5: 1 is smaller than 5, so swap them.
•Compare 1 with 4: 1 is smaller than 4, so swap them.
•Compare 1 with 2: 1 is smaller than 2, so swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so swap them.
•Compare 3 with 5: 3 is smaller than 5, so swap them.
•Compare 3 with 4: 3 is smaller than 4, so swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion
Sort:
∙Time Complexity:
Best case:
O(n) when
the array is
already
sorted.
Average and
worst case:
O(n^2), when
elements are
in reverse
order.
∙Space
Complexity: O(1)
making it an
in-place sorting
algorithm.
∙Stability: Yes, it
maintains the
relative order of
equal elements.

Advantages:
•Simple and easy to
implement.
•Efficient for small or
nearly sorted
datasets.

Disadvantages:
•Inefficient for large
datasets compared
to more advanced
algorithms like
quicksort or
mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

5. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works step-by-step:
1.Start from the second element (the first element is trivially
sorted by itself).
2.Take the current element and compare it with elements in the
sorted portion to its left.
3.Shift each larger element one position to the right to make
space for the current element.
4.Insert the current element in its correct position.
5.Repeat until the entire array is sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so swap them.
•Compare 1 with 5: 1 is smaller than 5, so swap them.
•Compare 1 with 4: 1 is smaller than 4, so swap them.
•Compare 1 with 2: 1 is smaller than 2, so swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so swap them.
•Compare 3 with 5: 3 is smaller than 5, so swap them.
•Compare 3 with 4: 3 is smaller than 4, so swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion Sort:
∙Time Complexity:
Best case: O(n) when the array is already sorted.
Average and worst case: O(n^2), when elements are in reverse
order.
∙Space Complexity: O(1) making it an in-place sorting algorithm.
∙Stability: Yes, it maintains the relative order of equal elements.

Advantages:
•Simple and easy to
implement.
•Efficient for small or
nearly sorted
datasets.

Disadvantages:
•Inefficient for large
datasets compared
to more advanced
algorithms like
quicksort or
mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

6. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works step-by-step:
1.Start from the second element (the first element is trivially
sorted by itself).
2.Take the current element and compare it with elements in the
sorted portion to its left.
3.Shift each larger element one position to the right to make
space for the current element.
4.Insert the current element in its correct position.
5.Repeat until the entire array is sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so swap them.
•Compare 1 with 5: 1 is smaller than 5, so swap them.
•Compare 1 with 4: 1 is smaller than 4, so swap them.
•Compare 1 with 2: 1 is smaller than 2, so swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so swap them.
•Compare 3 with 5: 3 is smaller than 5, so swap them.
•Compare 3 with 4: 3 is smaller than 4, so swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion Sort:
∙Time Complexity:
Best case: O(n) when the array is already sorted.
Average and worst case: O(n^2), when elements are in reverse
order.
∙Space Complexity: O(1) making it an in-place sorting algorithm.
∙Stability: Yes, it maintains the relative order of equal elements.

Advantages:
•Simple and easy to implement.
•Efficient for small or nearly sorted datasets.

Disadvantages:
•Inefficient for large datasets compared to more
advanced algorithms like quicksort or mergesort.
When to Use Insertion Sort
Insertion Sort is most
efficient when:
∙Sorting small datasets
or partially sorted
arrays.
∙When memory usage
is a concern, as it
sorts in place without
requiring additional
memory.

7. INSERTIO
N
Almirante, Avegail Lorainne P.
Celicious, Angel Rosana C.
Ondac, Deverly Clair
Resit, Jonalyn Q.
(i-apil pa ba nato?)
So
rt
Group 4
WHAT IS INSERTION SORT?
Insertion Sort is a simple sorting algorithm that builds the final
sorted array one item at a time. It’s similar to how you would
sort playing cards in your hand. In each step, it takes one
element from the input data, finds the correct position within
the sorted elements, and inserts it there.
Here’s how it works step-by-step:
1.Start from the second element (the first element is trivially
sorted by itself).
2.Take the current element and compare it with elements in the
sorted portion to its left.
3.Shift each larger element one position to the right to make
space for the current element.
4.Insert the current element in its correct position.
5.Repeat until the entire array is sorted.
Example:
Let's say we have the following unsorted array:
[5, 2, 4, 6, 1, 3]

Here's how insertion sort would sort this array:
Iteration 1:
•Current element: 2
•Compare 2 with 5: 2 is smaller than 5, so swap them.
•Array: [2, 5, 4, 6, 1, 3]

Iteration 2:
•Current element: 4
•Compare 4 with 5: 4 is smaller than 5, so swap them.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 3:
•Current element: 6
•Compare 6 with 5: 6 is greater than 5, so no swap is needed.
•Array: [2, 4, 5, 6, 1, 3]

Iteration 4:
•Current element: 1
•Compare 1 with 6: 1 is smaller than 6, so swap them.
•Compare 1 with 5: 1 is smaller than 5, so swap them.
•Compare 1 with 4: 1 is smaller than 4, so swap them.
•Compare 1 with 2: 1 is smaller than 2, so swap them.
•Array: [1, 2, 4, 5, 6, 3]

Iteration 5:
•Current element: 3
•Compare 3 with 6: 3 is smaller than 6, so swap them.
•Compare 3 with 5: 3 is smaller than 5, so swap them.
•Compare 3 with 4: 3 is smaller than 4, so swap them.
•Array: [1, 2, 3, 4, 5, 6]

The array is now sorted.
Properties of Insertion Sort:
∙Time Complexity:
Best case: O(n) when the array is already sorted.
Average and worst case: O(n^2), when elements are in reverse
order.
∙Space Complexity: O(1) making it an in-place sorting algorithm.
∙Stability: Yes, it maintains the relative order of equal elements.

Advantages:
•Simple and easy to implement.
•Efficient for small or nearly sorted datasets.

Disadvantages:
•Inefficient for large datasets compared to more
advanced algorithms like quicksort or mergesort.
When to Use Insertion Sort
Insertion Sort is most efficient when:
∙Sorting small datasets or partially sorted
arrays.
∙When memory usage is a concern, as it sorts
in place without requiring additional
memory.