22.05.2011, 10:08 | #1 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Застопорился с qsort
Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального). Необходимо отсортировать массив со случайными числами используя qsort. Я вроде разобрался с возможностями qsort, но серавно незнаю куда подстаавить и что нужно доделать. Если возможно поясните что не так делаю или что-то забыл Вот код: #include <iostream> #include<time.h> using namespace std; void qsort(int* a, long int left, long int right); int main () { srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N]; cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%20; cout<<a[i]<<" "; } cout<<"\n"; qsort(a, 0, N); cout << "\n Konechnii massiv: " << endl; for (int i = 0; i < N; i++) cout << a[i] << " "; delete [] a; } else cout<<"\n Chislo elementov ne mozhet byt <=0"; system("pause"); return 0; } |
23.05.2011, 11:43 | #2 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Я пот переделал слегка, но неидет. Может я что-то нетак сделалал или забыл, подскажите
Вот код: #include <iostream> #include <cstdlib> using namespace std; int compare_ints(const void* a, const void* b) // comparison function { int* arg1 = (int*) a; int* arg2 = (int*) b; if( *arg1 < *arg2 ) return -1; else if( *arg1 == *arg2 ) return 0; else return 1; int main () { srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N]; int size = N; qsort(a, size, sizeof(int), compare_ints); cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%20; cout<<a[i]<<" "; } cout<<"\n"; qsort(a, size, sizeof(int), compare_ints); cout << "\n Konechnii massiv: " << endl; for (int i = 0; i < N; i++) cout << a[i] << " "; delete [] a; } else cout<<"\n Chislo elementov ne mozhet byt <=0"; system("pause"); return 0; } } |
24.05.2011, 13:20 | #3 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Что-то делаю не так, подскажите
Я изменил код и он работал и после того как я пытаюсь добавить еще один элемент массива, притом, чтобы массив оставлся отсортированным, но что-то идет не так, или я про что-то не так делаю
Вот код: Код:
#include <iostream> #include <cstdlib> using namespace std; int compare_ints (const void* a, const void* b) { int res = *(const int*) a - *(const int*) b; return (res < 0) ? -1 : (res > 0) ? 1 : 0; } int main () { srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N+1];// резервируем память под массив на 1 элемент больше int size = N; cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<"\n"; qsort(a, size, sizeof(int), compare_ints); cout << "\nKonechnii massiv1: " << endl; for (int i = 0; i < N; i++) cout << a[i] << " "; cout << "\n"; cout<<endl<<"k: "; //k - случайное число cin>>k; cout<<endl; i=0; while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число i++; for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент a[j]=a[j-1]; a[i]=k; //вставляем на найденное место случайный элемент cout << "Konechnii massiv: " << endl; for (int i = 0; i < N+1; i++) cout << a[i] << " "; cout << endl; delete [] a; } else cout<<"\nChislo elementov ne mozhet byt <=0" << endl; system("pause"); return 0; } |
24.05.2011, 14:28 | #4 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Нашел ответ. Если у кого есть другие варианты буду рад их увидеть
Ответ пришел: Уберал int перед i во всех циклах for
И все заработало нормально. Вот код: Код:
#include <iostream> #include <cstdlib> using namespace std; int compare_ints (const void* a, const void* b) { int res = *(const int*) a - *(const int*) b; return (res < 0) ? -1 : (res > 0) ? 1 : 0; } int main () { srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N+1];// резервируем память под массив на 1 элемент больше int size = N; cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<"\n"; qsort(a, size, sizeof(int), compare_ints); cout << "\nOtsortirovannii massiv: " << endl; for (i = 0; i < N; i++) cout << a[i] << " "; cout << "\n"; cout<<endl<<"k: "; //k - случайное число cin>>k; cout<<endl; i=0; while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число i++; for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент a[j]=a[j-1]; a[i]=k; //вставляем на найденное место случайный элемент cout << "Konechnii massiv: " << endl; for (i = 0; i < N+1; i++) cout << a[i] << " "; cout << endl; delete [] a; } else cout<<"\nChislo elementov ne mozhet byt <=0" << endl; system("pause"); return 0; } |
24.05.2011, 15:04 | #5 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
И еще вопрос: если нужно добавить подсчет количества перестановок в массиве, то что нужно добавить в этой программе?
|
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
25.05.2011, 13:19 | #6 (permalink) |
Новичок
Регистрация: 09.04.2011
Сообщений: 7
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 10
|
Одномерный массив
Я сделал саму задачу, и выкладываю ее код, может кому пригодится.
Задание: Дан одномерный массив длиной N. Массив заполняется датчиком случайных чисел (лучше использовать любое распределение, кроме нормального). Требуется: 1) отсортировать массив со случайными числами; 2) в отсортированный массив, вставить случайное число, чтобы он оставался отсортированным; 3) также на экране после выполнения программы должно появляться сообщение, о том, сколько сравнений элементов сделано программой; 4) также программа должна выдавать сколько времени потребовалось ПК на выполнение программы Вот мои три разных способа решения задачи: Первый: Код:
#include <iostream> #include <cstdlib> #include<windows.h> using namespace std; int compare_count = 0; int compare(const void* a, const void *b) { ++compare_count; return (*(int*)a - *(int*)b); } int main () { DWORD t1, t2, d_time; srand (time(NULL)); int i, N, j, k; t1 = GetTickCount(); //Задаем количество элементов N=rand()%100; cout<<endl<<"Dlina massiva - N: " <<N <<endl; //N - длина одномерного массива cout<<"\n"; //Резервируем место на диске под количество элементов int *a = new int[N+1];// резервируем память под массив на 1 элемент больше int size = N; cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<"\n"; t1 = GetTickCount(); qsort(a, size, sizeof(int), compare); cout << "\nOtsortirovannii massiv: " << endl; for (i = 0; i < N; i++) cout << a[i] << " "; cout << "\n"; cout << "\nKolichestvo sravnenii: " << compare_count <<endl; k=rand()%100; cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число cout<< endl; i=0; while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число i++; for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент a[j]=a[j-1]; a[i]=k; //вставляем на найденное место случайный элемент cout << "Konechnii massiv: " << endl; for (i = 0; i < N+1; i++) cout << a[i] << " "; cout << endl; t2 = GetTickCount(); d_time = t2 - t1; cout<<"\nVremia raboti: "<<d_time<<" milisek\n"; delete [] a; system("pause"); return 0; } Код:
#include <iostream> #include <cstdlib> #include<windows.h> using namespace std; int compare_count = 0; int compare(const void* a, const void *b) { ++compare_count; return (*(int*)a - *(int*)b); } int main () { DWORD t1, t2, d_time; srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N+1];// резервируем память под массив на 1 элемент больше int size = N; cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<"\n"; t1 = GetTickCount(); qsort(a, size, sizeof(int), compare); cout << "\nOtsortirovannii massiv: " << endl; for (i = 0; i < N; i++) cout << a[i] << " "; cout << "\n"; cout << "\nKolichestvo sravnenii: " << compare_count <<endl; k=rand()%100; cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число cout<< endl; i=0; while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число i++; for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент a[j]=a[j-1]; a[i]=k; //вставляем на найденное место случайный элемент cout << "Konechnii massiv: " << endl; for (i = 0; i < N+1; i++) cout << a[i] << " "; cout << endl; t2 = GetTickCount(); d_time = t2 - t1; cout<<"\nVremia raboti: "<<d_time<<" milisek\n"; delete [] a; } else cout<<"Chislo elementov ne mozhet byt <=0" << endl; system("pause"); return 0; } Код:
#include <iostream> #include<time.h> #include<windows.h> using namespace std; int main () { DWORD t1, t2, d_time; srand (time(NULL)); int i, N, j, k; //Задаем количество элементов cout<<endl<<"Dlina massiva - N: "; //N - длина одномерного массива cin>>N; cout<<"\n"; if(N > 0) { //Резервируем место на диске под количество элементов int *a = new int[N+1];// резервируем память под массив на 1 элемент больше cout << "Vremennii massiv: " << endl; for(i=0; i<N; i++) { a[i]=rand()%100; cout<<a[i]<<" "; } cout<<"\n"; cout<< endl; t1 = GetTickCount(); int count=0; for (i = 0; i < N - 1; i++) { for(j = N-1; j>i; j--) if (a[j-1] > a[j]) { swap(a[j], a[j-1]); count++; } } cout << "Otsortirovannii massiv: " << endl; for (i = 0; i < N; i++) cout << a[i] << " "; cout<< endl; cout<<"\nKolichestvo perestanovok: "<<count; cout<< endl; k=rand()%100; cout<< endl << "Sluchainoe chislo - k: " << k <<endl; //k - случайное число cout<< endl; i=0; while ((a[i]<k) && (i<N)) //ищем место, куда поставить случайное число i++; for (j=N; j>i; j--) //сдвигаем все элементы массива на 1 в конец, чтобы вставить случайный элемент a[j]=a[j-1]; a[i]=k; //вставляем на найденное место случайный элемент cout << "Konechnii massiv: " << endl; for (i = 0; i < N+1; i++) cout << a[i] << " "; cout <<"\n"; t2 = GetTickCount(); d_time = t2 - t1; cout<<"\nVremia raboti: "<<d_time<<" milisek\n"; delete [] a; } else cout<<"Chislo elementov ne mozhet byt <=0" << endl; system("pause"); return 0; } P.S. Если у кого есть еще какие варианты решения данной задачи пишите. Всем спасибо за помощь в решении задачи. |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|