1 / 1 / 0
Регистрация: 24.01.2009
Сообщений: 14
1

Сортировка методом Вставок

01.10.2009, 15:10. Показов 62373. Ответов 25
Метки нет (Все метки)

Вот собственно вопрос. Масив записей структура которого конечная остановка, и время прибытия, нужно посортировать по направлению.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
 
struct rep
{
char route[20];
char time[5];
};
 
int main() {
clrscr();
rep mas[20];
rep temp;
int kil,i,j;
cout<<"Enter number of Routes: ";
cin>>kil;
for (i=0; i<kil; i++)
{
    cout<<"Enter Destination: ";
    cin>>mas[i].route;
    cout<<"Enter Time of Arriving: ";
    cin>>mas[i].time;
}
        for (i = 0; i < kil; i++)
        {
        temp=mas[i];
        for (j = i - 1; j >= 0 && mas[j].route > temp.route; j--)
            mas[j + 1] = mas[j];
            mas[j + 1] = temp;
        }
 
clrscr();
for (i=0; i<kil; i++)
{
cout<<mas[i].route<<" - "<<mas[i].time<<endl;
}
getch();
return 0;
}
Вот мой код но он почему то не сортирует так как надо хз почему уже даже незнаю в чём проблема?
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.10.2009, 15:10
Ответы с готовыми решениями:

Сортировка методом вставок
Заполнить массив размером 20 случайными числами в диапазоне от 0 до 200. Во второй массив выбрать...

Сортировка методом вставок
Заполнить массив размером 20 случайными числами в диапазоне от 0 до 200. Во второй массив выбрать...

Сортировка методом центрированных вставок
Доброго времени суток. Помоги доделать программу. Я решил сделать эту сортировку через...

Сортировка по возрастанию методом вставок
Массив из 5 целых чисел заполнить вводом с клавиатуры.Произвести сортировку массива по возрастанию...

25
Псевдо программист
192 / 113 / 37
Регистрация: 19.09.2009
Сообщений: 303
01.10.2009, 16:15 2
Сортировка вставками
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template
void insertSort(T a[], long size) {
  T x;
  long i, j;
 
  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];   
        // поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
    a[j+1] = x;
  }
}
2
1 / 1 / 0
Регистрация: 24.01.2009
Сообщений: 14
01.10.2009, 18:19  [ТС] 3
Так вроде всё правильно но не сортирует.
0
Эксперт JavaЭксперт С++
8376 / 3598 / 419
Регистрация: 03.07.2009
Сообщений: 10,708
01.10.2009, 19:26 4
ALYX, C++ FAQ
0
Псевдо программист
192 / 113 / 37
Регистрация: 19.09.2009
Сообщений: 303
01.10.2009, 19:46 5
Цитата Сообщение от ALYX Посмотреть сообщение
char route[20];
Цитата Сообщение от ALYX Посмотреть сообщение
mas[j].route > temp.route
перегрузи операцию сравнивания
0
2 / 2 / 0
Регистрация: 21.11.2008
Сообщений: 67
26.11.2010, 22:22 6
На Си++ алгоритм сортировки методом вставки будет таким
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void insertion_sort(int mas[], const int n)
{
    int key = 0, j = 0;
    for (int i = 1; i < n; i++)
    {
        key = mas[i];
        j = i - 1;
        while (j >= 0 && mas[j] > key)
        {
            mas[j + 1] = mas[j];
            j--;
        }
        mas[j + 1] = key;
    }
}
1
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
22.10.2011, 18:33 7
Привет всем мне нужно замутить сортировку массива методом вставка, вроде написал но что то не правильно сортирует! Вот мой код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    Memo1 -> Lines -> Add("Сортування вставками");
    count = 0;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
 
            if(mas[j] > mas[j+1])
            {
                x = mas[j];
                mas[j] = mas[j + 1];
                mas[j + 1] = x;
                count++;
            }
        }
        sm += IntToStr(mas[i]) + "  ";
    }
    Memo1 -> Lines -> Add(sm);
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 18:38 8
Во первых, это банальная сортировка пузырьком, а не вставками. А во вторых, и та неправильная
0
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
22.10.2011, 18:50 9
Thinker, http://img-fotki.yandex.ru/get... 7d86_L.jpg
http://fotki.yandex.ru/users/gussca/view/439189/

Добавлено через 2 минуты
Thinker, может я ошибку допустил?
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 18:52 10
gorin, просто поверьте на слово, а лучше почитайте более серьезную литературу или посты выше, что у вас не сортировка вставками, а обычная пузырьковая, причем неверно реализованная, так как вы обращаетесь к несуществующим элементам

Добавлено через 50 секунд
Цитата Сообщение от gorin Посмотреть сообщение
Thinker, может я ошибку допустил?
C++
1
for(int j = 0; j < n - 1; j++)
0
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
22.10.2011, 18:53 11
Thinker, а как правильно?
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 18:55 12
В посте 4 есть ссылка на несколько сортировок
0
209 / 16 / 4
Регистрация: 18.08.2009
Сообщений: 571
22.10.2011, 19:27 13
Thinker, вот этот код?
C++
1
2
3
4
5
6
7
8
  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];   
        // поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
    a[j+1] = x;
  }
он тупо переписывает первоначальный массив
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 22:10 14
gorin, не может быть, может вы не так алгоритм применили?
0
277 / 172 / 21
Регистрация: 10.07.2011
Сообщений: 441
22.10.2011, 22:32 15
Цитата Сообщение от gorin Посмотреть сообщение
Thinker, вот этот код?
C++
1
2
3
4
5
6
7
8
  for ( i=0; i < size; i++) {  // цикл проходов, i - номер прохода
    x = a[i];   
        // поиск места элемента в готовой последовательности 
    for ( j=i-1; j>=0 && a[j] > x; j--)
      a[j+1] = a[j];    // сдвигаем элемент направо, пока не дошли
        // место найдено, вставить элемент
    a[j+1] = x;
  }
он тупо переписывает первоначальный массив
у вас при i == 0, j будет равно -1. a[j+1] = a[j]; т.е. a[-1+1] = a[-1] как вы себе это представляете?
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 22:37 16
Цитата Сообщение от greeezz Посмотреть сообщение
у вас при i == 0, j будет равно -1. a[j+1] = a[j]; т.е. a[-1+1] = a[-1] как вы себе это представляете?
Это все нормально, там условие j>=0
0
277 / 172 / 21
Регистрация: 10.07.2011
Сообщений: 441
22.10.2011, 22:40 17
Цитата Сообщение от Thinker Посмотреть сообщение
Это все нормально, там условие j>=0
так в том то и дело что цикл не выполнится ни одного раза. потому что изначально j < 0
0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 22:42 18
Цитата Сообщение от greeezz Посмотреть сообщение
так в том то и дело что цикл не выполнится ни одного раза. потому что изначально j < 0

Не по теме:

Он при i==0 не выполнится ни разу, поэтому надо было с i=1 начинать, но это не страшно. Зато при i>0 процесс пойдет)

0
greeezz
22.10.2011, 22:46
  #19

Не по теме:

Thinker, вы правы. на мой взгляд нет логики в такой инициализции.

0
Эксперт С++
4264 / 2238 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
22.10.2011, 22:47 20
Цитата Сообщение от greeezz Посмотреть сообщение

Не по теме:

Thinker, вы правы. на мой взгляд нет логики в такой инициализции.

Не по теме:

Это само собой, лишние проверки ни к чему, поэтому, конечно, стоит с i=1 начинать, но это не страшно, алгоритм верный)

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.10.2011, 22:47
Помогаю со студенческими работами здесь

Сортировка методом простых вставок
Сортировка методом простых вставок - алгоритм S с. Вычисление трудоемкости Замер времени для...

Сортировка списка методом простых вставок
Помогите сделать чтобы в программе были двусвязные списки и чтобы списки из файла выводились в...

Сортировка двумерного массива методом вставок
Создать программу, сортирующую методом вставок двумерный массив целых чисел. При этом самое...

Сортировка диагоналей матрицы методом Шелла/вставок
Дана матрица размерностью n*n, содержащая целые числа. Отсортировать диагонали матрицы,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru