Comparative Study of Sorting Algorithms to sort a set of n number of records usi

Question

Comparative Study of Sorting Algorithms to sort a set of n number of records using multiple algorithms and analysis of the runtime.

Source code in C++

Algorithms considered should be: (i) Selection (ii) Insertion (iii) Merge (iv) Randomized Quick Sort and (v) Heap Sort

Each record consists of persons first name (string), last name (string), birthdate in date form (which itself will be a struct with month (string), day (int) and year (int)), email address (string) and phone no (area code (int), number (int)).

Explanation / Answer

selection sort: O(n2)

insertion sort: O(n2)

Merge: O(nlogn)

Quick Sort: O(n2)

Heap Sort: O(nlogn)

#include <iostream>
#include <string>
using namespace std;

struct Persons
{
string firstName;
string lastName;
string month;
int day;
int year;
string email;
int code;
int number;
};

void selectionSort(Persons s[], int n){
Persons temp;
for (int i = 0; i <n; i++)
for (int j = i+1; j < n; j++)
if (s[i].number > s[i].number)
{
tmp = s[i];
s[i] = s[j];
s[j] = tmp;
}
}
}
}

void insertionSort(Persons s[], int n){
Persons temp;
for (int i = 1; i < n; i++)
{
for (int j = i; j >= 1; j--)
{
if (s[i].number < s[i].number)
{
temp = s[j];
s[j] = s[j-1];
s[j-1] = temp;
}
else
break;
}
}
}

void mergesort(Persons *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
return;
}
void merge(Persons *a, int low, int high, int mid)
{
int i, j, k;
Persons * c = new Persons[10];
i = low;
k = low;
j = mid + 1;
while (i <= mid && j <= high)
{
if (a[i].number < a[j].number)
{
c[k].number = a[i].number;
k++;
i++;
}
else
{
c[k].number = a[j].number;
k++;
j++;
}
}
while (i <= mid)
{
c[k].number = a[i].number;
k++;
i++;
}
while (j <= high)
{
c[k].number = a[j].number;
k++;
j++;
}
for (i = low; i < k; i++)
{
a[i].number = c[i].number;
}
}

//quicksort
void quicksort(Persons *arr, const int left, const int right){

if (left >= right) {
return;
}

int part = partition(arr, left, right);

quicksort(arr, left, part - 1, sz);
quicksort(arr, part + 1, right, sz);
}

//heap sort
void max_heapify(Persons *a, int i, int n)
{
int j;
Persons temp;
temp = a[i].number;
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1].number > a[j].number)
j = j+1;
if (temp > a[j].number)
break;
else if (temp <= a[j].number)
{
a[j/2].number = a[j].number;
j = 2*j;
}
}
a[j/2].number = temp;
return;
}
void heapsort(Persons *a, int n)
{
int i;
Persons temp;
for (i = n; i >= 2; i--)
{
temp = a[i].number;
a[i].number = a[1];
a[1].number = temp;
max_heapify(a, 1, i - 1);
}
}

int main()
{
Persons * pointer = new Persons[3];
pointer[0].firstName = "John";
pointer[0].lastName = "carter";
pointer[0].month = "jan";
pointer[0].day = 21;
pointer[0].year = "John";
pointer[0].email = "abc@gmail.com";
pointer[0].code = 007;
pointer[0].number = 12345;

pointer[1].firstName = "John";
pointer[1].lastName = "carter";
pointer[1].month = "jan";
pointer[1].day = 21;
pointer[1].year = "John";
pointer[1].email = "abc@gmail.com";
pointer[1].code = 007;
pointer[1].number = 12345;

//call functions to make sort

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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