#include <stdio.
h>
int main() {
int rows = 3, cols = 3;
int arr[3][3];
// Input values into the 2D array
printf("Enter 9 numbers for a 3x3 array:\n");
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
scanf("%d", &arr[i][j]);
}
}
// Display the 2D array
printf("\nThe 3x3 array is:\n");
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
Output
Program Input:
Enter 9 numbers for a 3x3 array:
123
456
789
Program output:
The 3x3 array is:
123
456
789
Selection Sort
Selection Sort is a comparison-based sorting algorithm. It sorts by repeatedly
selecting the smallest (or largest) element from the unsorted portion and
swapping it with the first unsorted element.
1. Find the smallest element and swap it with the first element. This
way we get the smallest element at its correct position.
2. Then find the smallest among remaining elements (or second
smallest) and swap it with the second element.
3. We keep doing this until we get all elements moved to correct
position.
#include <stdio.h>
int main() {
int arr[5] = {64, 25, 12, 22, 11};
int n = 5;
// Selection Sort
for(int i = 0; i < n-1; i++) {
int min_index = i;
for(int j = i+1; j < n; j++) {
if(arr[j] < arr[min_index])
min_index = j;
}
// Swap
int temp = arr[min_index];
arr[min_index] = arr[i];
arr[i] = temp;
}
// Display sorted array
printf("Sorted array (Selection Sort):\n");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Processing (Step by Step):
Original array: 64 25 12 22 11
Pass 1: min = 11 → Swap with 64 → 11 25 12 22 64
Pass 2: min = 12 → Swap with 25 → 11 12 25 22 64
Pass 3: min = 22 → Swap with 25 → 11 12 22 25 64
Pass 4: min = 25 → Swap with 25 → 11 12 22 25 64
Sorted array: 11 12 22 25 64
Complexity Analysis of Selection Sort
Time Complexity: O(n2) ,as there are two nested loops:
One loop to select an element of Array one by one = O(n)
Another loop to compare that element with every other Array
element = O(n)
Therefore overall complexity = O(n) * O(n) = O(n*n) = O(n2)
Auxiliary Space: O(1) as the only extra memory used is for temporary
variables.
Advantages of Selection Sort
Easy to understand and implement, making it ideal for teaching basic
sorting concepts.
Requires only a constant O(1) extra memory space.
It requires less number of swaps (or memory writes) compared to
many other standard algorithms. Only cycle sort beats it in terms of
memory writes. Therefore it can be simple algorithm choice when
memory writes are costly.
Disadvantages of the Selection Sort
Selection sort has a time complexity of O(n^2) makes it slower
compared to algorithms like Quick Sort or Merge Sort.
Does not maintain the relative order of equal elements which means
it is not stable.
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that works by iteratively inserting
each element of an unsorted list into its correct position in a sorted portion of
the list. It is like sorting playing cards in your hands. You split the cards into
two groups: the sorted cards and the unsorted cards. Then, you pick a card
from the unsorted group and put it in the right place in the sorted group.
Start with the second element as the first element is assumed to be
sorted.
Compare the second element with the first if the second is smaller
then swap them.
Move to the third element, compare it with the first two, and put it in
its correct position
Repeat until the entire array is sorted.
#include <stdio.h>
int main() {
int arr[5] = {64, 25, 12, 22, 11};
int n = 5;
// Insertion Sort
for(int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements greater than key one position ahead
while(j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
// Display sorted array
printf("Sorted array (Insertion Sort):\n");
for(int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Original array: 64 25 12 22 11
Pass 1: key=25 → Move 64 → 25 64 12 22 11
Pass 2: key=12 → Move 64,25 → 12 25 64 22 11
Pass 3: key=22 → Move 64,25 → 12 22 25 64 11
Pass 4: key=11 → Move 64,25,22,12 → 11 12 22 25 64
Sorted array: 11 12 22 25 64
Time Complexity
Best case: O(n), If the list is already sorted, where n is the number of
elements in the list.
Average case: O(n2), If the list is randomly ordered
Worst case: O(n2), If the list is in reverse order
Space Complexity
Auxiliary Space: O(1), Insertion sort requires O(1) additional space,
making it a space-efficient sorting algorithm.
Please refer Complexity Analysis of Insertion Sort for details.
Advantages and Disadvantages of Insertion Sort
Advantages
Simple and easy to implement.
Stable sorting algorithm.
Efficient for small lists and nearly sorted lists.
Space-efficient as it is an in-place algorithm.
Adoptive. the number of inversions is directly proportional to
number of swaps. For example, no swapping happens for a sorted
array and it takes O(n) time only.
Disadvantages
Inefficient for large lists.
Not as efficient as other sorting algorithms (e.g., merge sort, quick
sort) for most cases.