What is Selection Sort, Insertion Sort and Merge Sort? Define their advantage. Write C Program and Algorithm also.
Selection Sort
Selection sort is a simple sorting algorithm that works by repeatedly finding the minimum element from an unsorted part of the array and placing it at the beginning of the array. This process is repeated until the entire array is sorted.
Advantages of Selection
Sort:
- Simple to implement
- In-place sorting algorithm, i.e., it doesn't require any extra memory space
- Good for small arrays or arrays with a small number of elements
//Algorithm for Selection
Sort:
Step 1. Start
Step 2. The first
element of the array.
Step 3. Find the smallest
element in the remaining unsorted part of the array.
Step 4. Swap the smallest
element with the first element.
Step 5. Move to the next
unsorted element and repeat steps 2 and 3 until the entire array is sorted.
Step 6. End
//C Program for Selection
Sort:
#include
<stdio.h>
void selection_sort(int
arr[], int n) {
int i, j, min_idx, temp;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Insertion Sort
Insertion sort is a
simple sorting algorithm that builds the final sorted array one item at a time,
much like how we sort a deck of playing cards. It is an in-place sorting
algorithm, which means it does not require extra space to perform the sort. The
algorithm is particularly efficient for small data sets or for data sets that
are almost sorted.
//Here is the algorithm
for insertion sort:
Step 1. Start
Step 2.The second element of the array.
Step 3. Compare the second
element with the first element. If the second element is smaller, swap them.
Step 4. Move to the third
element of the array.
Step 5. Compare the third element
with the second element. If the third element is smaller, swap them. If the
third element is still smaller than the first element, swap it with the first
element. Otherwise, do nothing.
Step 6. Repeat step 4 for the
remaining elements of the array.
Step 7. End
//Here is the C program for insertion sort:
#include <stdio.h>
void insertion_sort(int
arr[], int n) {
int i, j, key;
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;
}
}
int main() {
int arr[] = { 5, 2, 4, 6, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
The advantage of
insertion sort is that it has a best-case time complexity of O(n), where n is
the size of the array, if the input array is already sorted or nearly sorted.
Additionally, insertion sort is an adaptive sorting algorithm, meaning that it
is efficient for data sets that are partially sorted.
Merge Sort
Merge sort is a
divide-and-conquer sorting algorithm that divides an unsorted array into two
halves, sorts each half recursively, and then merges the two sorted halves into
a single sorted array. It is a stable sorting algorithm, meaning that it
maintains the relative order of equal elements in the sorted output.
//Here is the algorithm
for merge sort:
Step 1. Start
Step 2. merge_sort (arr, beg,
end)
Step 3. if beg < end
set mid = (beg +
end)/2
merge_sort(arr, beg,
mid)
merge_sort (arr, mid +
1, end)
merge (arr, beg, mid,
end)
Step 4. End
//Here is the C program for merge sort:
#include <stdio.h>
void merge(int arr[],
int left[], int left_size, int right[], int right_size) {
int i = 0, j = 0, k = 0;
while (i < left_size && j <
right_size) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left_size) {
arr[k++] = left[i++];
}
while (j < right_size) {
arr[k++] = right[j++];
}
}
void merge_sort(int
arr[], int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int left[mid], right[n - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}
merge_sort(left, mid);
merge_sort(right, n - mid);
merge(arr, left, mid, right, n - mid);
}
int main() {
int arr[] = { 5, 2, 4, 6, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
The advantage of merge
sort is that it has a time complexity of O(n log n), where n is the size of the
array, which makes it efficient for large datasets. Additionally, merge sort is
a stable sorting algorithm, meaning that it maintains the relative order of
equal elements in the sorted output.
Visit Also :-
What is Data Structure? Its Type and Operations.
https://codingtuition.blogspot.com/2023/05/what-is-data-structure-define-its-type.html
What is Searching? C Program of Linear Search and Binary Search with Algo.
https://codingtuition.blogspot.com/2023/05/searching-searching-is-process-of.html
What is Sorting? What is Bubble Sort?
https://codingtuition.blogspot.com/2023/05/what-is-sorting-define-its-type-and_4.html
Comments
Post a Comment