Lab 5 – Investigating Sorting Algorithms In this assignment we will create a sor
ID: 3689400 • Letter: L
Question
Lab 5 – Investigating Sorting Algorithms In this assignment we will create a sorting program that provides the user with a large assortment of sorting methods and options. The user should be able to choose from a menu to select which Sort they would like to use. For each Sort, be sure to sort four arrays (*see note below), and list the time it took to sort each of the four arrays either in milliseconds or nanoseconds. For each sorting algorithm, write a brief description of how the sort works, and be sure to note the time complexity. You can include both in the code as comments. The user should be able to choose from the following sort algorithms (Be sure to implement all). If you use any other resource (including online) you need to cite the source in your code. Bogo Sort **
Selection Sort
Insertion Sort
Bubble Sort
Quick Sort
Shell Sort
Merge Sort
Gnome Sort
Cocktail Sort
Radix Sort
** One more Sort of your choice**
*Note: For the assignment, you will need to create several arrays of integers of the following sizes {20,100, 500, 1000}. Fill the values of these arrays with random values between the number 0 and 999. You may need to reinitialize these arrays if the user decides to run another sort. You may also need values of 1000 to 9999 if you want to use Radix from the in-class example. **For Bogo Sort, due to the speed you may want to give the user a choice of the array size so that it may finish the sort in a somewhat timely manner.
Explanation / Answer
Most of the algorithms in use have an algorithmic efficiency of either O(n^2) or O(n*log(n)). A few special case algorithms can sort certain data sets faster than O(n*log(n)). It has been shown that no key-comparison algorithm can perform better than O(n*log(n)).
Here all sorts are implemented in C program. If want implement in any other language please inform me. And then explain every sort as individually not possible because due to space.
Bogo Sort
Output
Enter the elements of array
56 34 96 26 08 87 36
The array after sording is
08 26 34 36 56 87 96
Selection sort
#include<stdio.h>
#include<stdlib.h>
void display(int *array, int size){
int i;
for(i = 0; i < size; ++i){
printf("%d ",array[i]);
}
}
int findMax(int *array,int size){
int max=0,j;
for(j = 1; j <= size; ++j){
if(array[j] > array[max]){
max = j;
}
}
return max;
}
void selectionSort(int *array,int size){
int i,steps,temp;
for(steps = 0; steps < size; ++steps){
for(i = steps+1; i < size; ++i){
if(array[steps] > array[i]){
temp = array[steps];
array[steps] = array[i];
array[i] = temp;
}
}
printf(" After Iteration %d ",steps+1);
display(array,size);
}
}
int main(){
int *array,size,i;
printf("Enter the number of elements in the array");
scanf("%d",&size);
array = (int *)malloc(sizeof(int)*size);
for(i = 0; i < size; ++i){
printf(" Enter element %d",i+1);
scanf("%d",&array[i]);
}
printf(" Selection sort.");
printf(" array before sorting: ");
display(array,size);
selectionSort(array,size);
printf(" array after sorting: ");
display(array,size);
return 0;
}
Output
Enter the number of elements in the array
6 2 7 3 8 5 1
Selection sort.
array before sorting:
2 7 3 8 5 1
array after sorting:
1 2 3 5 7 8
Selection Sort
#include <stdio.h>
int main()
{
int data[100],i,n,steps,temp;
printf("Enter the number of elements to be sorted: ");
scanf("%d",&n);
for(i=0;i<n;++i)
{
printf("%d. Enter element: ",i+1);
scanf("%d",&data[i]);
}
for(steps=0;steps<n;++steps)
for(i=steps+1;i<n;++i)
{
if(data[steps]>data[i])
/* To sort in descending order, change > to <. */
{
temp=data[steps];
data[steps]=data[i];
data[i]=temp;
}
}
printf("In ascending order: ");
for(i=0;i<n;++i)
printf("%d ",data[i]);
return 0;
}
Output
Insertion sort
Output
Enter the number of elements 5
Enter the 5 integers
4 3 -1 2 1
Sorted list in ascending order:
-1 1 2 3 4
Bubble Sort
Output
Enter number of elements 6
Enter 6 integers
2 -4 7 8 4 7
Sorted list in ascending order
-4 2 4 7 7 8
Quick Sort
#include<stdio.h>
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // pivot
int i = (low - 1); // Index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[p] is now
at right place */
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf(" ");
}
// Driver program to test above functions
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;
}
Output
Sorted array
1 5 7 8 9 10
Radix sort
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.