Counting sort (from the maximum to minimum) - c++

How can I change this counting sort to make a sort from the max to min? I have no idea how to do that. I can't write the array in reverse order or change order of array after the sort. It must be in the algorithm of the sort. Here is a code.
#include<iostream>
#include<stdio.h>
#include<time.h>
using namespace std;
int main()
{
int n;
int k;
cout<<"number of elements" <<n<<endl;
cin>>n;
cout<<"max number"<<endl;
cin>>k;
int tab[n];
cout<<"array before sort :"<<endl;
for(int i=0; i<n; i++)
{
cin>>tab[i];
}
cout<<"array after sort"<<endl;
int tabp[k];
int tabw[n];
for(int i=0; i<k; i++)
{
tabp[i]=0;
}
for(int i=0; i<n; i++)
{
tabp[tab[i]]=tabp[tab[i]]+1;
}
for(int i=1; i<=k; i++)
{
tabp[i]+=tabp[i-1];
}
for(int i=0; i<n; i++)
{
tabw[tabp[tab[i]]-1]=tab[i];
tabp[tab[i]]=tabp[tab[i]]-1;
}
for(int i=0;i<n;i++)
{
cout<<tabw[i]<<" ";
}
return 0;
}

You should use methods from standard template library(STL) in algorithm modules. There is a good method std::sort which can help you. You pass container data to it and the third parameter can accept the way to sort given container. Here you can use functional objects from functional module in STL. You need to look at std::less<> and std::greater<>. They will sort your array by ascending or descending. Also you can pass your own function to sort the way you need.
There is a useful method std::reverse, you can reverse order of your elements in container. For example if you need to sort in ascending and descending then you can sort by ascending at first and then call std::reverse to get descending result.
// Sort by ascending
std::sort(tabw, tabw+n, std::less<int>());
//Reverse current array
std::reverse(tabw, tabw+n);
Short example with default init array data:
#include <iostream>
#include <algorithm>
#include <functional>
void TraceArr( int arr[], const int len, ostream& out )
{
std::copy(arr, arr+len, ostream_iterator<int>(out,", "));
std::cout << std::endl;
}
int main(int argc, const char * argv[]) {
const int SIZE = 10;
int arr[SIZE] {2,3,2,4,6,4,2,4,6,2};
// Sort by ascending
std::sort(arr, arr+SIZE, std::less<int>());
TraceArr(arr, SIZE, std::cout);//2, 2, 2, 2, 3, 4, 4, 4, 6, 6,
// Sort by descending
std::sort(arr, arr+SIZE, std::greater<int>());
TraceArr(arr, SIZE, std::cout);//6, 6, 4, 4, 4, 3, 2, 2, 2, 2,
return 0;
}
If you want me to show it in your code, then it looks like this:
#include <iostream>
#include <algorithm>
#include <functional>
#include<stdio.h>
#include<time.h>
using namespace std;
void TraceArr( int arr[], const int len, ostream& out )
{
std::copy(arr, arr+len, ostream_iterator<int>(out,", "));
std::cout << std::endl;
}
int main()
{
int n = 0;
int k = 0;
cout<<"number of elements" <<n<<endl;
cin>>n;
cout<<"max number"<<endl;
cin>>k;
int tab[n];
cout<<"array before sort :"<<endl;
for(int i=0; i<n; i++)
{
cin>>tab[i];
}
cout<<"array after sort"<<endl;
int tabp[k];
int tabw[n];
for(int i=0; i<k; i++)
{
tabp[i]=0;
}
for(int i=0; i<n; i++)
{
tabp[tab[i]]=tabp[tab[i]]+1;
}
for(int i=1; i<=k; i++)
{
tabp[i]+=tabp[i-1];
}
for(int i=0; i<n; i++)
{
tabw[tabp[tab[i]]-1]=tab[i];
tabp[tab[i]]=tabp[tab[i]]-1;
}
TraceArr(tabw, n, std::cout);
cout<<"array after sort with stl:"<<endl;
// Sort by ascending
std::sort(tabw, tabw+n, std::less<int>());
TraceArr(tabw, n, std::cout);
// Sort by descending
std::sort(tabw, tabw+n, std::greater<int>());
TraceArr(tabw, n, std::cout);
cout<<"array after reverse with stl:"<<endl;
//Reverse current array
std::reverse(tabw, tabw+n);
TraceArr(tabw, n, std::cout);
return 0;
}
And the result is:
number of elements0
5
max number
10
array before sort :
8
5
7
9
1
array after sort
1, 5, 7, 8, 9,
array after sort with stl:
1, 5, 7, 8, 9,
9, 8, 7, 5, 1,
array after reverse with stl:
1, 5, 7, 8, 9,
Program ended with exit code: 0
May be you don't need tabp tabw arrays at all? Don't understand exactly their necessary, you can sort with a help of STL after input data with tab array, like this
std::sort(tab, tab+n, std::less<int>()); // tab keeps sorted array ascending
std::sort(tab, tab+n, std::greater<int>()); // tab keeps sorted array descending

Related

Rotate array to right instead of left

I have some code that rotates a number array to the left but instead, I need it to rotate it to the right. There is other code online that rotates array to the right but that code lets you only rotate numbers in the middle of the array.
I have tried decrementing the loops differently & and changing where its initialized but doesn't seem to rotate the correct way.
Expected output: if array is this {1, 2, 3, 4, 5, 6, 7}. Then it should look like: {7, 1, 2, 3, 4, 5, 6}
Current output: {2, 3, 4, 5, 6, 7, 1}
#include <iostream>
using namespace std;
/*Function to left Rotate arr[] of size n by 1*/
void leftRotatebyOne(int arr[], int n);
/*Function to left rotate arr[] of size n by d*/
void leftRotate(int arr[], int d, int n)
{
int i;
for (i = 0; i < d; i++)
leftRotatebyOne(arr, n);
}
void leftRotatebyOne(int arr[], int n)
{
int i, temp;
temp = arr[0];
for (i = 0; i < n-1; i++)
arr[i] = arr[i+1];
arr[i] = temp;
}
/* utility function to print an array */
void printArray(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
cout << arr[i] << " ";
}
/* Driver program to test above functions */
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7};
printArray(arr, 7);
leftRotate(arr, 1, 7);
cout << "___" << endl;
printArray(arr, 7);
getchar();
return 0;
}
leftRotateByOne is the key function here. The others can stay the same. Have a look at what it is doing, preferably with a pen and paper to keep track of the operations:
Keeps a copy of the first element.
Moves all elements to the "left" (that is, to the element with index
one less), being careful not to overwrite anything you need later.
Puts the first element in the last place.
So you need to do the opposite:
Keep a copy of the last element.
Moves all elements to the "right" (that is, to the element with index
one more), being careful not to overwrite anything you need later.
Puts the last element in the first place.
For example:
void rightRotatebyOne(int arr[], int n)
{
int i, last;
last = arr[n-1];
for (i = n-1; i > 0; i--)
arr[i] = arr[i-1];
arr[0] = last;
}

sort entire 2d vector on the basis of a certain row

I am interested to sort the entire 2d vector on the basis of second row. I tried some code which sort only second row, however, i want it for the entire 2d vector.
#include<iostream>
#include<vector>
#include<algorithm>
int main()
{
std::vector< std::vector<int> > vect{{3, 5, 1},
{4, 8, 6},
{7, 2, 9}};
int m = vect.size();
int n = vect[0].size();
sort(vect[1].begin(), vect[1].end());
std::cout << "After sorting :\n";
for (int i=0; i<m; i++)
{
for (int j=0; j<n ;j++)
std::cout << vect[i][j] << " ";
std::cout << std::endl;
}
return 0;
}
The output come like:
3 5 1
4 6 8
7 2 9
But I want it to be
3 1 5
4 6 8
7 9 2
Create a function which transposes the vector, so it should modify {{3, 5, 1}, {4, 8, 6}, {7, 2, 9}} into {{3,4,7},{5,8,2},{1,6,9}}. Transpose the vector with your function, then sort the vector with custom comparator comparing the second elements of rows. Then call the transpose function again.
The transpose function could look like
std::vector< std::vector<int> > transpose(std::vector< std::vector<int> >& vect)
{
std::vector< std::vector<int> > transposed(vect[0].size(), std::vector<int>());
for (size_t i = 0; i < vect.size(); ++i)
for (size_t j = 0; j < vect[0].size(); ++j)
transposed[j].push_back(vect[i][j]);
return transposed;
}
Then the entire code would be
vect = transpose(vect);
std::sort(vect.begin(), vect.end(),
[](const std::vector<int>& lhs, const std::vector<int>& rhs)
{return lhs[1] < rhs[1];});
vect = transpose(vect);
If a vector is square then the transposition can be done in place making the solution much more effective then this general one.
The structure of question won't allow us to use built-in sort function. Because, custom sort will only provides "rows". And you can compare "rows" only.
But there are some alternative ways to accomplish that.
For example you can do that by transposing vector of vector.
"Transpose > Sort by column > Transpose" may solve your problem.
But my solution is based on another dynamic.
Sort nth column and keep indexes as array. (n is the position of ordered row)
Using the array defined at step 1, sort all rows one by one.
http://cpp.sh/4dkzg
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {
// initialize original index locations
vector<size_t> idx(v.size());
iota(idx.begin(), idx.end(), 0);
// sort indexes based on comparing values in v
sort(idx.begin(), idx.end(),
[&v](size_t i1, size_t i2) {return v[i1] < v[i2];});
return idx;
}
int main()
{
std::vector< std::vector<int> > vect{{3, 5, 1, 2},
{4, 8, 6, 1},
{7, 2, 9, 5}};
int m = vect.size();
int n = vect[0].size();
int sortByRow = 1; // starts from 0, if 1 => order by using 2nd row.
/* generate reference for our actual sort operation */
std::vector<size_t> indexSort = sort_indexes(vect[sortByRow]);
/* sort each row using our reference vector */
for (int i=0; i<m; i++)
{
int temp[n];
for (int j=0; j<n; j++)
temp[j] = vect[i][indexSort[j]];
// Copy back temp[] to vector
for (int j=0; j<n; j++)
vect[i][j] = temp[j];
}
std::cout << "After sorting :\n";
for (int i=0; i<m; i++)
{
for (int j=0; j<n ;j++)
std::cout << vect[i][j] << " ";
std::cout << std::endl;
}
return 0;
}
http://www.geeksforgeeks.org/reorder-a-array-according-to-given-indexes/ (if you want to apply in-place sorting, there are some fixes)
You could make an std::vector of std::pair<int,int> where in the first variable of the i-th element of the vector you have the i-th value of the second row while in the second variable you have the value of the index i.
Then you sort that vector based on the first values of the pairs. That way you can make a new 2D vector where in every row you order the elements based on the second value of the pairs, which are the old indices.
std::vector< std::vector<int> > vect{{ 3, 5, 1 },{ 4, 8, 6 },{ 7, 2, 9 }};
std::vector<std::pair<int, int>> row;
for (int i = 0; i < vect[1].size(); ++i){
row.push_back({vect[1][i],i});
}
sort(row.begin(), row.end());
std::vector< std::vector<int> > sorted;
std::vector<int> sortedRow;
for (int i = 0; i < vect.size(); ++i){
for (int j = 0; j < vect[i].size(); ++j){
sortedRow.push_back(vect[i][row[j].second]);
}
sorted.push_back(sortedRow);
sortedRow.clear();
}
You have to #include <utility>.
This code is very dirty. but exactly is the same code you want.
#include<iostream>
#include<vector>
#include<algorithm>
std::vector< std::vector<int> > vect = { {3, 5, 1}, {4, 8, 6}, {7, 2, 9} };
int findInVector(std::vector<int> input, int temp)
{
for(int i=0;i<input.size();i++)
{
if(input[i] == temp)
{
return i;
}
}
}
bool myfunction (int i,int j)
{
bool ret;
if(i<j)
{
int i_pos = findInVector( vect[1], i);
int j_pos = findInVector( vect[1], j);
int temp = vect[0][i_pos];
vect[0][i_pos] = vect[0][j_pos];
vect[0][j_pos] = temp;
temp = vect[2][i_pos];
vect[2][i_pos] = vect[2][j_pos];
vect[2][j_pos] = temp;
ret = true;
}
else
{
ret = false;
}
return ret;
}
int main()
{
int m = vect.size();
int n = vect[0].size();
sort(vect[1].begin(), vect[1].end(), myfunction);
std::cout << "After sorting :\n";
for (int i=0; i<m; i++)
{
for (int j=0; j<n ;j++)
std::cout << vect[i][j] << " ";
std::cout << std::endl;
}
return 0;
}

Using templates to sort strings and characters

I am trying to sort different types of arrays from the smallest to largest order using templates.
Though I got the int array to sort correctly, I couldn't get the character or string arrays from doing sorting. I kept getting an error that said "no matching function for call to bsort(char[10], int)" and "bsort(std::string[10], int)". What am I doing wrong?
In my template, I thought I had it accommodating to all the different types by the "Object" declaration.
#include <iostream>
#include <string>
using namespace std;
template <class Object>
void bsort(Object a[], Object n)
{
for (int i=0; i<n-1; i++)
{
for (int j=i+1; j<n; j++)
{
if(a[i]>a[j])
{
Object item;
item=a[i];
a[i]=a[j];
a[j]=item;
}
}
}
}
int main ()
{
int intarray[10]= {50, 10, 20, 15, 62, 32, 6, 80, 90, 100};
char chararray[10]= {'a', 'f', 'v', 'b', 'c', 's', 'm', 'i', 'j', 'i'};
string stringarray[10]= {"hi", "how", "are", "you", "today", "love", "eating", "food", "brownies", "icecream"};
cout<<"The intarray consists of"<<endl;
for (int i=0; i<10; i++)
cout<<intarray[i]<<endl;
cout<<"The sorted intarray sorted is"<<endl;
bsort(intarray, 10);
for (int i=0; i<10; i++)
cout<<intarray[i]<<endl;
cout<<"Sorted char array"<<endl;
bsort(chararray, 10);
for (int i=0; i<10; i++)
cout<<chararray[i]<<endl;
cout<<"The sorted stringarray is"<<endl;
bsort(stringarray, 10);
for (int i=0; i<10; i++)
cout<<stringarray[i]<<endl;
return 0;
}
**edit, I tried that a[] at first, but it still did not do anything to change the sorting/errors that it gave me
void bsort(Object *array, Object n)
should be
void bsort(Object *array, std::size_t n)
Demo
You can also take advantage of template deduction so you don't have to provide a type or size every time.
template <class Object>
void bsort(Object *array, int n) {
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j<n; ++j){
if (array[i] > array[j]) {
Object item;
item = array[i];
array[i] = array[j];
array[j] = item;
}
}
}
}
This is fine, but you have to provide a size each time. This could be annoying if you declared it like this:
intarray[] = {3, 1, 5, 2, 0, 8, 6, 9, 4, 7}; // do you really want to count these?
For this, you can create a very simple template wrapper (I put two):
template<class Object, size_t N>
void bsort(Object(&o)[N]) {
return bsort<Object>(o, N);
}
template<class Object, size_t N>
void bsort(Object(&o)[N], size_t &size) {
size = N;
return bsort<Object>(o, N);
}
The reason for the second one is that you can pass a size_t ref into it and it will set that as the size. For example, you could run either of these:
int intarray[] = {3, 1, 5, 2, 0, 8, 6, 9, 4, 7};
bsort(intarray);
bsort<int>(intarray, 10); // <int> is rather unnecessary
size_t size = 0;
bsort(intarray, size);
The reason you may want to use the last one is that now you have a way of printing the correct size.
int intarray[] = {3, 1, 5, 2, 0, 8, 6, 9, 4, 7};
size_t size = 0;
bsort(intarray, size);
for(size_t i = 0; i < size; ++i)
std::cout << intarray[i] << "\n";
Of course this specific template will only work on stack-based arrays, not dynamically allocated ones, but you can always use the other call.

Why is my selection sort returning a value that is not in the original vector?

I've been tinkering around with it for a while now and I'm so close! Now the output seems to be continuously printing a zero as the first value of the "sorted" vector. This is homework on how to create a selection sort in C++.
Example Output
Vector: 6, 2, 11, 1, 12, 4
Sorted Vector: 0, 2, 11, 6, 12, 4
Code
void selectionSort (vector<int>& data)
{
int min, temp, n=data.size(), i, j;
for (i=0; i<n; i++)
{
min = i;
for (j=i+1; j<n; j++)
{
if (data[min]>data[j])
{
min=j;
}
temp=data[min];
data[min]=data[i];
data[i]=temp;
}
return;
}
}
int main()
{
int n;
vector<int> data;
cout<<"Vector length?: "<<endl;
cin>>n;
srand(time(0));
for (int i=0; i<n; i++)
{
data.push_back(rand()%20+1);
}
cout<<"Vector: "<<endl;
for (int i=0; i<n; i++)
{
cout<<data[i]<<" "<<endl;
}
selectionSort(data);
cout<<"Selection Sorted Vector: "<<endl;
for (int i=0; i<data.size(); i++)
{
cout<<data[i]<<" "<<endl;
}
system("Pause");
return 0;
}
Consider the following correct implementation of a selection sort and compare it to yours:
#include <iostream>
#include <vector>
void selection_sort(std::vector<int> &numbers)
{
// Iterate through all possible start indices.
for (int i = 0; i < numbers.size(); ++i)
{
// Determine the index of the minimum for this iteration.
int index_of_min = i;
for (int j = i; j < numbers.size(); ++j)
{
if (numbers[j] < numbers[index_of_min])
{
index_of_min = j;
}
}
// Swap the minimum element with the element at the start index.
int temp = numbers[i];
numbers[i] = numbers[index_of_min];
numbers[index_of_min] = temp;
}
}
int main()
{
std::vector<int> numbers = { 20, 17, 13, 12, 25 };
selection_sort(numbers);
for (size_t i = 0; i < numbers.size(); ++i)
{
std::cout << numbers[i] << " ";
}
}
Given an array of n elements, a selection sort performs n swaps.
You're performing far more swaps than that.
You also have an unexpectedly early call to return.
Let's look at a proper implementation of the sort:
#include <iostream>
#include <vector>
using namespace std;
void selectionSort (vector<int>& data)
{
const int n = data.size();
for (int i=0; i<n; i++)
{
int min = i;
for (int j=i+1; j<n; j++)
if (data[min]>data[j])
min = j;
swap(data[min], data[i]);
}
}
int main() {
vector<int> data = {6, 2, 11, 1, 12, 4};
selectionSort(data);
for (auto element : data)
cout << element << " ";
cout << "\n";
}
Which outputs:
1 2 4 6 11 12

Find in array the biggest multiple and write it vica versa

I was given a task:
it is given an array of five numbers
First - Find all numbers that are multiples of four
Second - Find the biggest of them and write it vice versa.
I have written a code.
#include <iostream>
#include <iomanip>
using namespace std;
#define size 12
int main()
{
int new_max=0;
int a1, a2;
int i=0, j=0;
int a, b, c=0;
int u[size]={38,12,36,45,16,46,14,19,54,53,95, 98};
int max=0;
cout<<"Array: \n";
for(i=0; i<size; i++)
cout<<u[i]<<" \n";
for (int i=0; i<size; i++)
{
if (u[i]%4==0)
{
cout<<"array "<<u[i]<<" \n";
for (int j=0; j<size; j++)
{
if(max<u[i])
{
max=u[i];
}}}}
cout<<"max "<<max<<endl;
while(max > 0)
{
new_max = new_max*10 + ( max % 10);
max = max/10;
}
cout << new_max << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <string>
#include <array>
int main() {
std::array<int, 5> input = { 36, 12, 38, 45, 16 };
auto validRangeEnd = std::remove_if(std::begin(input),
std::end(input),
[](int i){ return i % 4 != 0; });
// Now std::begin(input) -> validRangeEnd contain the ones divisible by 4
auto max = std::max_element(std::begin(input), validRangeEnd);
// Max contains the max number from the filtered range
auto stringMax = std::to_string(*max);
std::reverse(std::begin(stringMax), std::end(stringMax));
// Reverse reverses the max number
std::cout << stringMax;
}
By no means optimal but I feel it's useful for educational purposes :).
(Both remove_if and max_elements do a pass so I'll re-examine some stuff that I don't need to but this is a good algorithmic representation of the problem anyway. Also, no loops, look! :))

Resources