VPF::[СИ]сортировка хоара - Форум программистов

MemphisMayFire

Дата 20.5.2011, 15:38 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

Добрый день!
помогите, пожалуйста, написать сортировку хоара(рекурсивный метод) для массива структур, с элементами:

Код


typedef struct {
  char val[256];
  int key;
} elem;

Сортировать нужно по ключу (d[i].val)
Я не могу найти, где бы нормально был описан алгоритм(может не догоняю просто).
Если вам не сложно, то напишите как вообще реализовывать это. Было бы совсем отлично, если бы кто-нибудь дал код, курсовую надо сдать в выходные smile

Вот код с добавлением элементов в массив:

Код


iint main() {
int n, i = 0, j = 0;
scanf("%d", &n);
elem d[n];
for (i = 0; i < n; i++) {
  scanf("%d ", &d[i].key);
  scanf("%[^\n]", d[i].val);
} 
}

заранее спасибо!

вот рабочий код для данной задачи:

Код


#include <stdio.h>

typedef struct {
  char val[256];
  int key;
} elem;

void sortHoar(elem *d, int from, int to) {
int i, j;
elem x, temp;
if (from >= to) {
  return;
}
i = from;
j = to;
x = d[(from+to)/2];
temp = d[i];
while (i <= j) {
  while (d[i].key < x.key) {
    i++;
  }
  while (d[j].key > x.key) {
    j--;
  }
  if (i <= j) {
    temp = d[i]; 
    d[i] = d[j];
    d[j] = temp;
    i++;
    j--;
  }
}
sortHoar(d, from, j);
sortHoar(d, i, to);
}

int main() {
int n, i = 0, j = 0;
scanf("%d", &n);
elem d[n];
for (i = 0; i < n; i++) {
  scanf("%d ", &d[i].key);
  scanf("%[^\n]", d[i].val);
} 
sortHoar(d, 0, n-1);
for (i = 0; i < n; i++) {
  printf("%d %s\n", d[i].key, d[i].val);
}
}

Это сообщение отредактировал(а) MemphisMayFire - 20.5.2011, 22:17

borisbn

Дата 20.5.2011, 15:59 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

Цитата(MemphisMayFire @ 20.5.2011, 15:38

)

Я не могу найти, где бы нормально был описан алгоритм

не знаю, как ты искал...
http://lmgtfy.com/?q=%D1%81%D0%BE%D1%80%D1...1%D0%B8&l=1
первая ссылка

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 20.5.2011, 16:09 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

а from и to что такое?

Добавлено через 4 минуты и 15 секунд
а, вроде понял, все.

Добавлено через 6 минут и 33 секунды
только вот придется, наверное, писать функцию поиска минимального/максимального элемента массива, так как числа определяются пользователем и могут быть, например, 2 4 5 8.

borisbn

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

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

изначально индекс первого и последнего элемента массива. в твоём случае 0 и n-1. Затем они изменяются в соответствии с алгоритмом

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

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

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

а, это номера. спасибо!

borisbn

Дата 20.5.2011, 16:35 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

учти, что в том алгоритме сортируется массив целых чисел, а тебе нужно

Цитата(MemphisMayFire @ 20.5.2011, 15:38

)

Сортировать нужно по ключу (d[i].val)

т.е. вместо простого сравнения

Код


while ( A[i] < x ) i ++;
while ( A[j] > x ) j --;

нужно делать как-то так

Код


while ( strcmp(A[i].val, x.val) < 0 ) i ++;
while ( strcmp(A[j].val, x.val) > 0 ) j --;

не уверен, что именно так - нужно проверять

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 20.5.2011, 16:45 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

вроде нужно вот так

Код


while (d[i].val < 0 ) i ++;

borisbn

Дата 20.5.2011, 16:47 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

Цитата(MemphisMayFire @ 20.5.2011, 16:45

)

while (d[i].val < 0 ) i ++;

val - массив символов. как он м.б. < 0 ???
smile

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 20.5.2011, 16:51 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

ну ты обращаешься к элементу массива как a[i], а тут у тебя массив структур и тебе нужно обратиться к элементам одного поля(key в моем случае, тк сортировка идет по ключам), то есть d[i].key.

Добавлено через 57 секунд
случаенно val вместо key написал

Добавлено через 9 минут и 1 секунду

Код


#include <stdio.h>

typedef struct {
  char val[256];
  int key;
} elem;

void sort(elem *d, int from, int to) {
int x, i, j, temp;
if (from >= to) {
  return;
}
i = from;
j = to;
x = d[(from+to)/2].key;
while (i <= j) {
  while (d[i].key < x) {
    i++;
  }
  while (d[j].key > x) 
    j --;
  }
  if (i <= j) {
    temp = d[i].key; 
    d[i].key = d[j].key;
    d[j].key = temp;
    i++;
    j--;
  }
}
sort(d, from, j);
sort(d, i, to);
}

int main() {
int n, i = 0, j = 0;
scanf("%d", &n);
elem d[n];
for (i = 0; i < n; i++) {
  scanf("%d ", &d[i].key);
  scanf("%[^\n]", d[i].val);
} 
sort(d, 0, n-1);
for (i = 0; i < n; i++) {
  printf("%d %s", d[i].key, d[i].val);
}
}

фэйлы какие-то непонятные(

borisbn

Дата 20.5.2011, 17:03 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

так, как ты сделал - неправильно, т.к. у тебя сортируется не массив целиком, а только поля key, при этом val остаются на своих местах

Цитата(MemphisMayFire @ 20.5.2011, 16:51

)

фэйлы какие-то непонятные(

наверное, что-то где-то не работает

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 20.5.2011, 17:05 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

а, ну да, будет только одно сортироваться.
походу придется указатели сделать.

borisbn

Дата 20.5.2011, 17:06 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

подсказка: x и temp должны быть не типа int, а типа elem

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

Дата 20.5.2011, 17:12 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

о, точно, спасибо!

borisbn

Дата 20.5.2011, 17:14 (ссылка)

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

Загрузка ...

Эксперт

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

Репутация: 11
Всего: 135

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

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

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

MemphisMayFire

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

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 22
Регистрация: 22.4.2011
Где: москва

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

только фэйлы выдает при передаче val
>>incompatible types when assigning to type ‘char[256]’ from type ‘char *’

Код


x.val = d[(from+to)/2].val;
temp.val = d[i].val;
...

что не так?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »