Insertion Sort
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in
your hands. The array is virtually split into a sorted and an unsorted part. Values from the
unsorted part are picked and placed at the correct position in the sorted part.
Implementation of Insertion Sort Algorithm
How many inputs do you want? 5
Index 1: 5
Index 2: 4
Index 3: 3
Index 4: 2
Index 5: 1
Sorted Value of Index: 1,2,3,4,5
Sorted Index based on the value: 5,4,3,2,1
// C++ program for insertion sort
#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;
}
}
// A utility function to print an array
// of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, N);
printArray(arr, N);
return 0;
}
// This is code is contributed by rathbhupendra
Activity 1
3 1 7 4 5 2 6
Activity 2
2 9 8 1 7 3 6 5
Selection Sort
Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting
the smallest (or largest) element from the unsorted portion of the list and moving it to the
sorted portion of the list.
The algorithm repeatedly selects the smallest (or largest) element from the unsorted portion of
the list and swaps it with the first element of the unsorted part. This process is repeated for the
remaining unsorted portion until the entire list is sorted.
Implementation:
// C++ program for implementation of
// selection sort
#include <bits/stdc++.h>
using namespace std;
// Function for Selection sort
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
if (min_idx != i)
swap(arr[min_idx], arr[i]);
}
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++) {
cout << arr[i] << " ";
cout << endl;
}
}
// Driver program
int main()
{
int arr[] = { 64, 25, 12, 22, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function Call
selectionSort(arr, n);
cout << "Sorted array: \n";
printArray(arr, n);
return 0;
}
// This is code is contributed by rathbhupendra
Output
Sorted array:
11 12 22 25 64
1st Given
-7 3 8 -4 1 2 6
2nd Given
3 6 -8 9 1 2
