Advertisement
Guest User

andré's sorting

a guest
Apr 3rd, 2020
366
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. /**
  8.  * Orders an array of positive integers with a time complexity of N
  9.  * Each of the integer must be less than 1123456 (around 1 million).
  10.  * Integers must be different.
  11.  *
  12.  * @author André Souza Abreu
  13.  * @param array An array of integers, passed by reference.
  14.  * @param int The size of the aray
  15.  * @param bool The sorting direction. false => ascending, true => descending.
  16.  * @return void
  17. */
  18. void andre_sort(int array[], int array_length, bool descending_sort = false) {
  19.     // get the size of the
  20.     int max_size = -1;
  21.     for (int i = 0; i < array_length; i++) {
  22.         if (array[i] > max_size) {
  23.             max_size = array[i];
  24.         }
  25.     }
  26.     max_size++; // increment by 1 because array index starts from zero
  27.  
  28.     // register the values
  29.     int blueprint[max_size];
  30.     for (int i = 0; i < max_size; i++) {
  31.         blueprint[i] = 0;
  32.     }
  33.  
  34.     //
  35.     for (int i = 0; i < array_length; i++) {
  36.         int value = array[i];
  37.         blueprint[value]++;
  38.     }
  39.  
  40.     //
  41.     int index = 0;
  42.     for (int i = 0; i < max_size; i++) {
  43.         int j = i;
  44.  
  45.         if (descending_sort) {
  46.             j = max_size - i - 1;
  47.         }
  48.  
  49.         if (blueprint[j] != 0) {
  50.             while (blueprint[j] != 0) {
  51.                 array[index] = j;
  52.                 index++;
  53.                 blueprint[j]--;
  54.             }
  55.         }
  56.     }
  57. }
  58.  
  59. int main () {
  60.     int numbers[8];
  61.     numbers[0] = 12;
  62.     numbers[1] = 754;
  63.     numbers[2] = 76;
  64.     numbers[3] = 4123;
  65.     numbers[4] = 230;
  66.     numbers[5] = 754;
  67.     numbers[6] = 43;
  68.     numbers[7] = 754;
  69.  
  70.     andre_sort(numbers, 8);
  71.  
  72.     for (int i = 0; i < 8; i++) {
  73.         int number = numbers[i];
  74.         cout << number << endl;
  75.     }
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement