/Sort-Testing

Test work to measure the execution time of sorting methods.

Primary LanguageC++

Runtime testing on sorting algorithms

Members:

  • João Vitor dos Santos Couto
  • Norton Pereira Ricardo
  • Gabriel de Castro Gonçalves
  • Wellington Soares de Morais

This work aims to analyze the execution time of each sorting method, considering the best and worst case and a random case.

Algoritmos

  • InsertSort
  • SelectSort
  • BubbleSort
  • MergeSort
  • QuickSort
  • HeapSort
  • CountingSort

Execution

Initially, vectors of capacities 10, 100, 1000, 10000, 100000, 1000000 with random values are generated. Each ordering method contemplates the best case, the worst case and the random case, measuring the execution time in milliseconds.

Ps.: Execution time is very long!

Result

At the end of the execution, a .csv file is generated with the relation of the time of each sorting method, the case and the number of values.

The table below shows the results obtained in our tests:

Method Case 10 elements 100 elements 1K elements 10K elements 100K elements 1Mi elements
Insert Sort desc 0.000004 0.000019 0.001620 0.182767 17.251184 1611.838577
asc 0.000002 0.000004 0.000006 0.000047 0.000449 0.004473
random 0.000003 0.000012 0.00823 0.079005 7.943851 799.206770
Select Sort desc 0.000003 0.000019 0.001410 0.133461 13.359896 1343.629463
asc 0.000003 0.0000015 0.001354 0.129305 12.944675 1306.872859
random 0.000004 0.000019 0.001361 0.134216 12.956807 1306.966180
Bubble Sort desc 0.000003 0.000024 0.002332 0.241012 23.713167 2401.834658
asc 0.000003 0.0000018 0.001894 0.154836 15.277765 1551.682540
random 0.000004 0.000032 0.002354 0.306766 36.531915 3758.580319
Merge Sort desc 0.000005 0.000014 0.000167 0.001795 0.019427 --
asc 0.000010 0.000009 0.000098 0.001441 0.015994 --
random 0.000005 0.000021 0.000211 0.002391 0.027624 --
Quick Sort desc 0.000003 0.000029 0.002901 0.276623 32.086353 --
asc 0.000003 0.000042 0.004697 0.394430 46.614081 --
random 0.000003 0.000014 0.000163 0.002214 0.025998 --
Heap Sort desc 0.000004 0.000020 0.000251 0.003109 0.038352 0.482071
asc 0.000004 0.000042 0.000278 0.003290 0.041006 0.498634
random 0.000005 0.000023 0.000325 0.003789 0.048847 0.672122 
Ps.: The times of operations were measured in seconds.

Test machine specification

In this project, a virtual machine hosted on the Google Cloud service was used with the following settings:

Processor: 4 vCPUs Intel(R) Xeon(R) CPU @ 2.20GHz
Memory: 32GB
OS: Ubuntu #56~18.04.1 x86_64, GNU/Linux
Hard disk: 50GB