Регистрация: 02.10.2018
Сообщений: 6
|
С++ цифровая сортировка
Код:
#include "iostream"
#include "windows.h"
#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include <ctime>
using namespace std;
int n, col_razr=0;
int max_razr(int chislo)
{
int max=0;
while(chislo>1)
{
chislo/=10;
max++;
}
return max;
}
int velich_razr(int chislo,int razr)
{
while(razr>1)
{
chislo/=10;
razr--;
}
return chislo%10;
}
void sort_razr(int **dop_mas, int *array_rand, int razr)
{
int *mas_col, i,j, temp=0;
mas_col=new int[n];
for(i=0; i<n; i++)
mas_col[i]=0;
for(i=0; i<n; i++)
{
int a=velich_razr(array_rand[i], razr);
dop_mas[mas_col[a]][a]=array_rand[i];
mas_col[a]++;
}
for(i=0; i<n; i++)
{
for(j=0; j<mas_col[i]; j++)
{
array_rand[temp]=dop_mas[j][i];
temp++;
}
}
}
int main()
{
setlocale(0,"");
int razr, i, *array_rand, **dop_mas;
int array1[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // Единицы
int array2[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90}; // Десятки
int array3[10] = {0, 100, 200, 300, 400, 500, 600, 700, 800, 900}; // Сотни
int array4[10] = {0, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000}; // Тысячи
int array5[10] = {0, 10000, 20000, 30000, 40000, 50000, 60000, 70000, 80000, 90000}; // Десятки тысяч
int array6[10] = {0, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000}; // Сотни тысяч
int array7[10] = {0, 1000000, 2000000, 3000000, 4000000, 5000000, 6000000, 7000000, 8000000, 9000000}; // Миллион
int index1,
index2,
index3,
index4,
index5,
index6,
index7,
index8,
index9,
index10,
SumNumber;
cout<<"Размер "<< endl;
cin>>n;
array_rand=new int[n];
srand(time(0));
for(int i = 0; i < n; i++){
index1 = rand() % 9;
index2 = rand() % 9;
index3 = rand() % 9;
index4 = rand() % 9;
index5 = rand() % 9;
index6 = rand() % 9;
index7 = rand() % 9;
index8 = rand() % 9;
index9 = rand() % 1;
index10 = rand() % 2;
if(n<=10){
SumNumber=array1[index1];
array_rand[i] = SumNumber % n;
}
else{
if(n<=100){
SumNumber=array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
else{if(n<=1000){
SumNumber=array3[index3] + array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
else{
if(n<=10000){
SumNumber=array4[index4] + array3[index3] + array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
else{
if(n<=100000){
SumNumber=array5[index5] +array4[index4] + array3[index3] + array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
else{
if(n<=1000000){
SumNumber=array6[index6] + array5[index5] +array4[index4] + array3[index3] + array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
else{
if(n>=1000000){
SumNumber=array7[index7] + array6[index6] +array5[index5] +array4[index4] + array3[index3] + array2[index2] + array1[index1];
array_rand[i] = SumNumber % n;
}
}}}}}}}
// В итоге и правильном алгоритме, мы получаем
ofstream out("D:\\сорт\\test.txt");
for (int i = 0; i<n; i++)
out << array_rand[i] << endl;
out.close();
dop_mas=new int*[n];
for(i=0; i<n; i++)
dop_mas[i]=new int[n];
for(i=0; i<n; i++)
if(col_razr<max_razr(array_rand[i]))
col_razr=max_razr(array_rand[i]);
for(razr=1; razr<=col_razr; razr++)
sort_razr(dop_mas, array_rand, razr);
ofstream out2("D:\\сорт\\test2.txt");
for (int i = 0; i<n; i++)
out2 << array_rand[i] << endl;
out2.close();
getchar();
return 0;
}
Данный код выполняет цифровую сортировку, записывая неупорядоченный порядок в 1ый файл, и отсортированный во 2ой, но есть проблема, что при вводе числа элементов больше 100к вылезает ошибка std bad_ alloc, прошу помощи в решении данной проблемы. Отладчик показывал, что в данном месте ошибка(появляется очень большое значение)
dop_mas=new int*[n];
for(i=0; i<n; i++)
dop_mas[i]=new int[n];
for(i=0; i<n; i++)
Последний раз редактировалось azunight; 02.10.2018 в 23:54.
|