Sorting Comparison Objective: Write a program that implements the following sort

Question

Sorting Comparison

Objective:

Write a program that implements the following sorting algorithms:

Selection Sort

Bubble Sort

Merge Sort

Quick Sort

Next test the efficiency of each using the following steps:

Create an array of randomly selected whole numbers of 1,000 elements

Each value is selected from the range 0-999

Sort that array using each method

Make sure to copy the initial array into a new one so that the tests will be accurate and not be sorting sorted arrays

Show that each method successfully sorted the array

Count the number of checks each method had to perform before fully sorting the array

Keep track of the total number of checks for each algorithm

Perform this 20 times and keep track of the running average

Finally at the end give the average number of checks using each algorithm.

Explanation / Answer

Selection Sort In C :-

Bubble Sort :

Merge Sort :-

#include <stdio.h>

void mergeSort(int [], int, int, int);
void partition(int [],int, int);

int main()
{
int list[50];
int i, size;

printf("Enter total number of elements:");
scanf("%d", &size);
printf("Enter the elements: ");
for(i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
partition(list, 0, size - 1);
printf("After merge sort: ");
for(i = 0;i < size; i++)
{
printf("%d ",list[i]);
}

return 0;
}

void partition(int list[],int low,int high)
{
int mid;

if(low < high)
{
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}
}

void mergeSort(int list[],int low,int mid,int high)
{
int i, mi, k, lo, temp[50];

lo = low;
i = low;
mi = mid + 1;
while ((lo <= mid) && (mi <= high))
{
if (list[lo] <= list[mi])
{
temp[i] = list[lo];
lo++;
}
else
{
temp[i] = list[mi];
mi++;
}
i++;
}
if (lo > mid)
{
for (k = mi; k <= high; k++)
{
temp[i] = list[k];
i++;
}
}
else
{
for (k = lo; k <= mid; k++)
{
temp[i] = list[k];
i++;
}
}

for (k = low; k <= high; k++)
{
list[k] = temp[k];
}
}

Quick SOrt :-

#include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

printf("Enter size of the array: ");
scanf("%d",&size);

printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
    scanf("%d",&x[i]);

quicksort(x,0,size-1);

printf("Sorted elements: ");
  for(i=0;i<size;i++)
    printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[10],int first,int last){
    int pivot,j,temp,i;

     if(first<last){
         pivot=first;
         i=first;
         j=last;

         while(i<j){
             while(x[i]<=x[pivot]&&i<last)
                 i++;
             while(x[j]>x[pivot])
                 j--;
             if(i<j){
                 temp=x[i];
                  x[i]=x[j];
                  x[j]=temp;
             }
         }

         temp=x[pivot];
         x[pivot]=x[j];
         x[j]=temp;
         quicksort(x,first,j-1);
         quicksort(x,j+1,last);

    }
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.