[go: up one dir, main page]
Scribd
Upload
9 views8 pages

Exprimrnt 1

The document describes two sorting algorithms: Selection Sort and Insertion Sort. Selection Sort repeatedly selects the smallest element from the unsorted portion and swaps it into the correct position, while Insertion Sort divides the list into sorted and unsorted parts, inserting each element from the unsorted part into its correct position in the sorted part. Both algorithms are implemented in C programming language with example code provided.

Uploaded by

231114
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
9 views8 pages

Exprimrnt 1

The document describes two sorting algorithms: Selection Sort and Insertion Sort. Selection Sort repeatedly selects the smallest element from the unsorted portion and swaps it into the correct position, while Insertion Sort divides the list into sorted and unsorted parts, inserting each element from the unsorted part into its correct position in the sorted part. Both algorithms are implemented in C programming language with example code provided.

Uploaded by

231114
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

Selection Sort

Selection Sort is a comparison-based sorting algorithm. It sorts an array by repeatedly


selecting the smallest (or largest) element from the unsorted portion and swapping it with
the first unsorted element. This process continues until the entire array is sorted.
1. First we find the smallest element and swap it with the first element. This way we get
the smallest element at its correct position.
2. Then we 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.
// C program for implementation of selection sort
#include <stdio.h>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
// Assume the current position holds
// the minimum element
int min_idx = i;
// Iterate through the unsorted portion
// to find the actual minimum
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
// Update min_idx if a smaller element is found
min_idx = j;
}
}
// Move minimum element to its
// correct position
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
Insertion Sort
How Insertion Sort Works in C?
Insertion sort divides the list into sorted and unsorted part. Initially, the first element is
already considered sorted, while the rest of the list is considered unsorted. The algorithm then
iterates through each element in the unsorted part, picking one element at a time, and inserts
it into its correct position in the sorted part.

Insertion Sort Algorithm in C


 Start with the second element (index 1) as the key.
 Compare the key with the elements before it.
 If the key is smaller than the compared element, shift the compared element one
position to the right.
 Insert the key where the shifting of elements stops.
 Repeat steps 2-4 for all elements in the unsorted part of the list.
Example of array arr = {12, 11, 13, 5, 6} that we need to sort in ascending order.
// C program to implement insertion sort
#include <math.h>
#include <stdio.h>
void insertionSort(int arr[], int N) {
// Starting from the second element
for (int i = 1; i < N; i++) {
int key = arr[i];
int j = i - 1;
// Move elements of arr[0..i-1], that are
// greater than key, to one position to
// the right of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Move the key to its correct position
arr[j + 1] = key;
}
}
int main() {
int arr[] = { 12, 11, 13, 5, 6 };
int N = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array: ");
for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// Calling insertion sort on array arr
insertionSort(arr, N);

printf("Sorted array: ");


for (int i = 0; i < N; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}

You might also like