IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным. В описании темы указываем язык!!!

 
 Ответить  Открыть новую тему 
> не прямая сортировка, с++
сообщение
Сообщение #1


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Исправил ф-ю так, чтобы сортировался не сам массив, а массив индексов, в следствии программа работать перестала, помогите найти ошибку ...

Помогите пожалуйста, горю, как всегда оставил все на последний день ...

#include <iostream.h>
#include <stdlib.h>
#include <fstream.h>
//#include <windows.h>
#include <conio.h>

void FillA(long *a, long n); // заполнение массива a[i] = random
void FillI(long *idx, long n); // заполнение массива индексов a[i] = i;
void Print(long *a, long *idx, long n); // печать массива по индескам (cout << arr[idx[i]])

// пирамидальная сортировка
void downHeapIDx(long *a, long *idx, long k, long N);
void heapSortIdx(long *a, long *idx, long N);

long *a, *idx, L;
ofstream f1, f2;

int main (void){

clrscr();

/*
ofstream f1("f1.txt");
ofstream f2("f2.txt");

for (long L = 100000; L <= 1000000; L+=100000){
a = new long [L];
idx = new long [L];
FillA(a, L);
FillI(idx, L);

long start = GetTickCount();
qs(a, 0, L-1);
long stop = GetTickCount();

f1 << L << '\t' << stop - start << endl;

start = GetTickCount();
qsIdx(a, idx, 0, L-1);
stop = GetTickCount();

f2 << L << '\t' << stop - start << endl;

cout << L << '\t' << stop - start << '\t' << "Done." << endl;

free(a);
free(idx);
}
*/

L = 10; // размер массива
a = new long [L]; // массив
idx = new long [L]; // массив индексов

FillA(a, L);
FillI(idx, L);

Print(a, idx, L);
cout << endl;
heapSortIdx(a, idx, L);
Print(a, idx, L);

return 0;
}

void FillA(long *a, long n){
srand(time(NULL));
for (long i = 0; i< n; i++)
a[i] = rand() % 100;
}

void FillI(long *idx, long n){
for (long i = 0; i < n; i++)
idx[i] = i;
}

void Print(long *a, long *idx, long n){
for (long i = 0; i < n; i++)
cout << a[i] << endl;
}

void downHeapIdx(long *a, long *idx, long k, long N)
{ long newElt, child;
newElt=a[idx[k]];
while(k <= N/2)
{ child = 2*k;

if(child < N && a[idx[child]] < a[idx[child+1]])
child++;
if(newElt >= a[idx[child]]) break;

a[idx[k]] = a[idx[child]];
k = child;
}
a[idx[k]] = newElt;
}


void heapSortIdx(long *a, long *idx, long N)

{ long i, temp;
for(i=N/2; i >= 1; i--)
downHeapIdx(a, idx,i, N);


for(i=N; i > 1; i--)
{ temp = idx[i];
idx[i]=idx[1];
idx[1]=temp;

downHeapIdx(a, idx,1,i-1);
}
}


прямой метод отрабатывает нормально, код сортироочной функции взял тут : http://algolist.manual.ru/sort/faq/q9.php


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






rolleyes.gif
#include <conio.h>
#include <iostream.h>

void in_Sort(long *ar, long *idx, long Right, long Left) {

long i = Left, j = 2*i;
long x = idx[i - 1];

while(j <= Right) {
if(j < Right)
if(ar[idx[j - 1]] < ar[idx[j]]) ++j;

if(ar[x] >= ar[idx[j - 1]]) break;
idx[i - 1] = idx[j - 1];
i = j; j = 2 * i;
}

idx[i - 1] = x;
}

void HeapSort(long *ar, long *idx, long n) {

long Left = (n / 2) + 1, Right = n;
while(Left > 1) {
Left -= 1; in_Sort(ar, idx, Right, Left);
}

while(Right > 1) {
long T = idx[Left - 1];
idx[Left - 1] = idx[Right - 1];
idx[Right - 1] = T;

Right -= 1; in_Sort(ar, idx, Right, Left);
}
}

void Print(long *ar, long n) {

for(long i = 0; i < n; i++)
cout << ar[i] << " ";
cout << endl;

}

int main() {

const int n = 10;

long arr[n] = {96, 86, 29, 88, 30, 9, 43, 15, 33, 39};
long idx[n];

clrscr();

for(int i = 0; i < n; ++i) idx[i] = i;
Print(arr, n);
Print(idx, n);

HeapSort(arr, idx, n);

Print(arr, n);
Print(idx, n);
return 0;
}


Дальше разберешься?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Огромное спасибо !


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 




- Текстовая версия 19.10.2017 3:22
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"