VPF::Сортировка с вводом чисел - Форум программистов

Syltan

Дата 26.9.2009, 16:24 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: нет
Всего: -2

Наконец-то разобрался с алгоритмом сортировки. Решил изменить код.
Я хочу задать ввод с клавиатуры чисел, а программа их уже должна отсортировать. То есть вначале, юзер, должен ввести количество чисел масива,после этого,сами числа, а программа должна вывести эти числа в отсортированном виде.
Вот исходник. Программа компилится,но работает не так,как хочется.

Код


#include <iostream>
using namespace std;

template < typename T>
void sort(T *a, long N)
{
    long i = 0,  j = N;
   T temp,p;
   p = a[N/2];
   do{
   while(a[i]<p) i++;
   while(a[j]>p) j--;
   if(i<=j)
   {
       temp = a[i]; a[i]= a[j]; a[j] = temp;
       i++; j--;
   }
   }while(i<=j);
   if(j>0) sort(a,j);
   if(N>i) sort(a+i,N-i);
 
}


int main()
{
setlocale(0,"");
int k1 = 0,ch1,i;
int k2 = 0,ch2, s;
cout<<"Введите пожалуйста количество чисел:\n";
cin>>k1;
int* a = new int[k1];

for(i = 0; i < k1; i++)
{
cin>>ch1;
a[i] = ch1;
cout<<a[i]<<' ';
}
sort(a,k1-1);
delete[] a; 

cout<<"Введите пожалуйста количество символов:\n";
cin>>k2;
int* b = new int[k2];
sort(b,k2-1);
for(s = 0; s < k2; s++)
{
cin>>ch2;
a[s] = ch2;
cout<<a[s]<<' ';
}
delete [] b;

cin.get();
}

ИванМ

Дата 26.9.2009, 17:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1260
Регистрация: 19.6.2006
Где: СПб

Репутация: нет
Всего: 23

функцию сортировки лень разбирать (вообще есть готовые, зачем изобретать велосипед?)
пишешь delete[] a;
а потом
a[s] = ch2;
а также:
int* b = new int[k2];
sort(b,k2-1);
т.е.сортируешь массив неопределенных чисел

элементы массива, который удалил, выводишь на экран:
cout<<a[s]<<' ';

Это сообщение отредактировал(а) ИванМ - 26.9.2009, 17:56

Cheloveck

Дата 26.9.2009, 18:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1578
Регистрация: 26.7.2008
Где: Тула

Репутация: нет
Всего: 32

Цитата(ИванМ @ 26.9.2009, 18:52

)

вообще есть готовые, зачем изобретать велосипед?

чтобы знать, как велосипед работает.

Цитата(Syltan @ 26.9.2009, 17:24

)

if(j>0) sort(a,j);
if(N>i) sort(a+i,N-i);

хм... это не есть хорошо. Рекурсия не нужна.

Хочу сказать, что нужно почитать о тех алгоритмах, которые уже существуют. Например здесь. А велосипеды если и нужно писать, то они должны быть правильные)))

--------------------

Syltan

Дата 26.9.2009, 19:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 301
Регистрация: 31.8.2009

Репутация: нет
Всего: -2

Хорошо,а как же можно заменить вот это место:

Код


if(j>0) sort(a,j);
   if(N>i) sort(a+i,N-i);

прийдётся переделывать весь код.

DenWPF

Дата 26.9.2009, 19:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1659
Регистрация: 26.9.2009

Репутация: нет
Всего: 1

извеняюсь. но что то я не сильно С++ вижу.

17dufa

Дата 5.10.2009, 16:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 324
Регистрация: 2.3.2006

Репутация: нет
Всего: 5

Cheloveck, вообще quicksort через рекурсию работает. похоже что у автора именно она и есть. так что рекурсия более чем оправдана бывает.

Это сообщение отредактировал(а) 17dufa - 5.10.2009, 16:25

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Visual C++/MFC/WTL \| Следующая тема »