Question

Merge Sort:

Time Complexity: O(n log(n))

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <stdlib.h>

using namespace std;

void combine(int *a, int low, int high, int mid)

{

       int i, j, k, c[100000];

       i = low;

       k = low;

       j = mid + 1;

       while (i <= mid && j <= high)

       {

              if (a[i] < a[j])

              {

                     c[k] = a[i];

                     k++;

                     i++;

              }

              else

              {

                     c[k] = a[j];

                     k++;

                     j++;

              }

       }

       while (i <= mid)

       {

              c[k] = a[i];

              k++;

              i++;

       }

       while (j <= high)

       {

              c[k] = a[j];

              k++;

              j++;

       }

       for (i = low; i < k; i++)

       {

              a[i] = c[i];

       }

}

void mergeSort(int *a, int low, int high)

{

       int mid;

       if (low < high)

       {

              mid = (low + high) / 2;

              mergeSort(a, low, mid);

              mergeSort(a, mid + 1, high);

              combine(a, low, high, mid);

       }

       return;

}

int _tmain(int argc, _TCHAR* argv[])

{

       //random number seed

       srand(time(NULL));

       int l = 1;

       const clock_t startclock = clock();

       for (int i = 0; i < l; i++)

       {

              int a[100000];

              for (int j = 0; j < 100000; j++)

                     a[i] = rand() % 10000;

              int len = 100000;

              mergeSort(a, 0, len - 1);

       }

       cout << "\nStart time for Mergesort: " << float(startclock) / CLOCKS_PER_SEC;

       cout << "\nEnd time for Mergesort: " << float(clock()) / CLOCKS_PER_SEC;

       cout << "\nTime taken for Mergesort: " << float(clock() - startclock) / CLOCKS_PER_SEC;

       cout << "\n\n";

       return 0;

}

Quicksort:

O(n log(n))

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <stdlib.h>

using namespace std;

void quickSort(int arr[], int left, int right) {

       int i = left, j = right;

       int tmp;

       int pivot = arr[(left + right) / 2];

       /* partition */

       while (i <= j) {

              while (arr[i] < pivot)

                     i++;

              while (arr[j] > pivot)

                     j--;

              if (i <= j) {

                     tmp = arr[i];

                     arr[i] = arr[j];

                     arr[j] = tmp;

                     i++;

                     j--;

              }

       };

       /* recursion */

       if (left < j)

              quickSort(arr, left, j);

       if (i < right)

              quickSort(arr, i, right);

}

int _tmain(int argc, _TCHAR* argv[])

{

       //random number seed

       srand(time(NULL));

       int l = 1;

       const clock_t startclock = clock();

       for (int i = 0; i < l; i++)

       {

              int a[100000];

              for (int j = 0; j < 100000; j++)

                     a[i] = rand() % 10000;

              int len = 100000;

              quickSort(a, 0, len - 1); //must do len -1 due to \0 at the end of every array

       }

       cout << "\nStart time for Quicksort: " << float(startclock) / CLOCKS_PER_SEC;

       cout << "\nEnd time for Quicksort: " << float(clock()) / CLOCKS_PER_SEC;

       cout << "\nTime taken for Quicksort: " << float(clock() - startclock) / CLOCKS_PER_SEC;

       cout << "\n\n";

       return 0;

}

Insertion Sort

Time Complexity: O(n)

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <stdlib.h>

using namespace std;

void insertionSort(int arr[], int n)

{

       int temp;

       for (int i = 1; i < n; i++)

       {

              for (int j = i; j >= 1; j--)

              {

                     if (arr[j] < arr[j - 1])

                     {

                           temp = arr[j];

                           arr[j] = arr[j - 1];

                           arr[j - 1] = temp;

                     }

                     else

                           break;

              }

       }

}

int _tmain(int argc, _TCHAR* argv[])

{

       srand(time(NULL));

       int l = 1;

       const clock_t startclock = clock();

       for (int i = 0; i < l; i++)

       {

              int a[100000];

              for (int j = 0; j < 100000; j++)

                     a[i] = rand() % 10000;

              int len = 100000;

              insertionSort(a, len);

       }

       cout << "Start time for Insertion Sort: " << float(startclock) / CLOCKS_PER_SEC;

       cout << "\nEnd time for Insertion Sort: " << float(clock()) / CLOCKS_PER_SEC;

       cout << "\nTime taken for Insertion Sort: " << float(clock() - startclock) / CLOCKS_PER_SEC;

       return 0;

}

Selection Sort

Time Complexity: O(n^2)

#include "stdafx.h"

#include <iostream>

#include <time.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

void selectSort(int arr[], int n)

{

       //pos_min is short for position of min

       int pos_min, temp;

       for (int i = 0; i < n - 1; i++)

       {

              pos_min = i;//set pos_min to the current index of array

              for (int j = i + 1; j < n; j++)

              {

                     if (arr[j] < arr[pos_min])

                           pos_min = j;

                     //pos_min will keep track of the index that min is in, this is needed when a swap happens

              }

              //if pos_min no longer equals i than a smaller value must have been found, so a swap must occur

              if (pos_min != i)

              {

                     temp = arr[i];

                     arr[i] = arr[pos_min];

                     arr[pos_min] = temp;

              }

       }

}

int _tmain(int argc, _TCHAR* argv[])

{

       //How to make a random number in C++

       srand(time(NULL));

       int l = 1;

       const clock_t startclock = clock();

       for (int i = 0; i < l; i++)

       {

              int a[100000];

              for (int j = 0; j < 100000; j++)

                     a[i] = rand() % 10000;

              int len = 100000;

              selectSort(a, len);

       }

       cout << "Start time for Seleciton Sort: " << float(startclock) / CLOCKS_PER_SEC;

       cout << "\nEnd time for Selection Sort: " << float(clock()) / CLOCKS_PER_SEC;

       cout << "\nTime taken for Section Sort: " << float(clock() - startclock) / CLOCKS_PER_SEC;

       cout << "\n\n" << endl;

       return 0;

}

Give a description and a comparison/analysis of the running times of different algorithms.

Answer 1