sort-an-array.cpp (1385B)
1 #include <vector> 2 #include <iostream> 3 4 5 //Leet Ratings 6 // Speed Memory 7 //Total 105ms 68.4MB 8 //Beats 99.25% 45.24% 9 // This was very fast and used count sort. I would like to go through this again 10 // with a 0(nlog(n)) sorting algorithm. 11 12 13 using namespace std; 14 15 16 vector<int> sortArray(vector<int>& nums) { 17 int highest_val = nums[0]; 18 int lowest_val = nums[0]; 19 for(int i = 0 ; i < nums.size() ; ++i ){ 20 if(nums[i] > highest_val){ 21 highest_val = nums[i]; 22 } 23 if(nums[i] < lowest_val){ 24 lowest_val = nums[i]; 25 } 26 } 27 int diff = highest_val - lowest_val; 28 vector<int> counted_nums(diff + 1, 0); 29 for(int i = 0; i < nums.size(); ++i){ 30 counted_nums[nums[i] - lowest_val] = counted_nums[nums[i] - lowest_val] + 1; 31 } 32 33 vector<int> sorted_nums(nums.size(), 0); 34 int count = 0; 35 for (int i = 0 ; i < counted_nums.size() ; ++i){ 36 int val = counted_nums[i]; 37 int stored_val = i + lowest_val; 38 for(int x = 0 ; x < val; ++x){ 39 sorted_nums[count] = stored_val; 40 count += 1; 41 } 42 } 43 return sorted_nums; 44 } 45 46 int main(){ 47 48 vector<int> vec = {0 , 3, 5, 2, 1, 5, 65}; 49 vec = sortArray(vec); 50 cout << "["; 51 for(int i = 0; i < vec.size() - 1; ++i){ 52 cout << vec[i] << ","; 53 } 54 cout << vec[vec.size()-1] << "]" << endl; 55 56 }