Advertisement
Guest User

Sorting algorithms

a guest
Oct 25th, 2016
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <time.h>
  4.  
  5. using namespace std;
  6.  
  7. int* BubbleSort(int arr[], int arraysize);
  8. int* QuickSort(int arr[], int left, int right);
  9. int* RadixSort(int arr[], int arraysize);
  10.  
  11. int main()
  12. {
  13.     int arraysize;
  14.     cout << "Enter the array size: ";
  15.     cin >> arraysize;
  16.  
  17.     int timer_start, timer_end, bubble_time, quick_time, radix_time;
  18.     int bubblearr[arraysize], quickarr[arraysize], radixarr[arraysize];
  19.  
  20.     ifstream file_bubble, file_quick, file_radix;
  21.     file_bubble.open("unsorted bubble.txt");
  22.     file_quick.open("unsorted quick.txt");
  23.     file_radix.open("unsorted radix.txt");
  24.  
  25.     for(int i = 0; i < arraysize; i++){
  26.         file_bubble >> bubblearr[i];
  27.         file_quick >> quickarr[i];
  28.         file_radix >> radixarr[i];
  29.     }
  30.  
  31.     timer_start = clock();
  32.     BubbleSort(bubblearr, arraysize);
  33.     timer_end = clock();
  34.     bubble_time = (timer_end - timer_start) / CLOCKS_PER_SEC;
  35.  
  36.     timer_start = clock();
  37.     QuickSort(quickarr, 0, arraysize);
  38.     timer_end = clock();
  39.     quick_time = (timer_end - timer_start) / CLOCKS_PER_SEC;
  40.  
  41.     timer_start = clock();
  42.     RadixSort(radixarr, arraysize);
  43.     timer_end = clock();
  44.     radix_time = (timer_end - timer_start) / CLOCKS_PER_SEC;
  45.  
  46.     cout << "Sorting is done, the execution times were:\nBubblesort: " << bubble_time << "\nQuicksort: " << quick_time << "\nRadixsort: " << radix_time;
  47.  
  48.     ofstream file_out;
  49.     file_out.open("sorted.csv");
  50.     file_out << "Bubblesort,Quicksort,Radixsort\n," << bubble_time << "," << quick_time << "," << radix_time << endl;
  51.     for(int i = 0; i < arraysize; i++){
  52.         file_out << bubblearr[i] << "," << quickarr[i] << "," << radixarr[i] << endl;
  53.     }
  54.  
  55.     file_bubble.close();
  56.     file_quick.close();
  57.     file_radix.close();
  58.     file_out.close();
  59.  
  60.     return 0;
  61. }
  62.  
  63. int* BubbleSort(int arr[], int arraysize)
  64. {
  65.     bool swapped = true;
  66.     int j = 0;
  67.     int temp;
  68.     while(swapped){
  69.         swapped = false;
  70.         j++;
  71.         for (int i = 0; i < arraysize - j; i++) {
  72.             if (arr[i] > arr[i + 1]) {
  73.                 temp = arr[i];
  74.                 arr[i] = arr[i + 1];
  75.                 arr[i + 1] = temp;
  76.                 swapped = true;
  77.             }
  78.         }
  79.     }
  80.     return arr;
  81. }
  82.  
  83. int* QuickSort(int arr[], int left, int right)
  84. {
  85.     int i = left, j = right;
  86.     int temp;
  87.     int pivot = arr[(left + right) / 2];
  88.  
  89.     //partitie
  90.     while (i <= j){
  91.         while (arr[i] < pivot){
  92.             i++;
  93.         }
  94.         while (arr[j] > pivot){
  95.             j--;
  96.         }
  97.         if (i <= j){
  98.             temp = arr[i];
  99.             arr[i] = arr[j];
  100.             arr[j] = temp;
  101.             i++;
  102.             j--;
  103.         }
  104.     }
  105.  
  106.     //recursie
  107.     if(left < j){
  108.         QuickSort(arr, left, j);
  109.     }
  110.     if(i < right){
  111.         QuickSort(arr, i, right);
  112.     }
  113.  
  114.     return arr;
  115. }
  116.  
  117. int* RadixSort(int arr[], int arraysize)
  118. {
  119.     //Sorteer loop
  120.     int output[arraysize];
  121.     int i, j;
  122.  
  123.     int n = arr[0];
  124.     for(i = 1; i < arraysize; i++){
  125.         if(arr[i] > n){
  126.             n = arr[i];
  127.         }
  128.     }
  129.  
  130.     for(i = 1; n / i > 0; i *= 10){
  131.         int digit[10] = {0};
  132.         for(j = 0; j < arraysize; j++){
  133.             digit[(arr[j] / i) % 10]++;  //categoriseer getallen
  134.         }
  135.         for(j = 1; j < 10; j++){
  136.             digit[j] += digit[j - 1];
  137.         }
  138.  
  139.         for(j = arraysize - 1; j >= 0; j--){
  140.             output[digit[(arr[j] / i) % 10] - 1] = arr[j];
  141.             digit[(arr[j] / i) % 10]--;
  142.         }
  143.  
  144.         for(j = 0; j < arraysize; j++){
  145.             arr[j] = output[j];
  146.         }
  147.     }
  148.     return arr;
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement