Consider the following sequence of integers: 22,1,3,4,9,13,29,25,5,8,6 Ilustrate

Question

Consider the following sequence of integers: 22,1,3,4,9,13,29,25,5,8,6 Ilustrate the execution of inplace sorting of the sequence of numbers using selection sort algorithm, insertion sort algorithm, bubble sort algorithm, merge sort algorithm, and quick sort algorithm Consider the following sequence of integers: 22,1,3,4,9,13,29,25,5,8,6 Ilustrate the execution of inplace sorting of the sequence of numbers using selection sort algorithm, insertion sort algorithm, bubble sort algorithm, merge sort algorithm, and quick sort algorithm 22,1,3,4,9,13,29,25,5,8,6 Ilustrate the execution of inplace sorting of the sequence of numbers using selection sort algorithm, insertion sort algorithm, bubble sort algorithm, merge sort algorithm, and quick sort algorithm

Explanation / Answer

Selection Sort --

#include <stdio.h>

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void selectionSort(int arr[], int n)
{
int i, j, min_idx;

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(&arr[min_idx], &arr[i]);
}
}

void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}

int main()
{
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}

Insertion sort --

#include <stdio.h>
#include <math.h>

void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;

while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}

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

int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

Bubble Sort --

#include <stdio.h>

void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)


for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}

void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}

int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}

Merge Sort --

#include<stdlib.h>
#include<stdio.h>

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
  
int m = l+(r-l)/2;

mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}

int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is ");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf(" Sorted array is ");
printArray(arr, arr_size);
return 0;
}

Quick Sort --

#include<stdio.h>

void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}

int partition (int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high- 1; j++)
{
  
if (arr[j] <= pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

void quickSort(int arr[], int low, int high)
{
if (low < high)
{

int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}

int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---