VPF::[C++] Сортировка вектора. - Форум программистов

Tyurs92

Дата 18.5.2011, 15:09 (ссылка)

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

Загрузка ...

Новичок

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

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

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

t_gran

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

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

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

Tyurs92, а какие алгоритмы или в каком количестве? Вектор самому разрабатывать или использовать std::vector?

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

Я знаю, что ничего не знаю© Сократ
user posted image

Tyurs92

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

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

Загрузка ...

Новичок

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

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

Отсортировать надо по убыванию элементов для 20 элементов введёных с экрана. (все числа целые)

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

1) Сортировка выбором;
2) Пузырьковая сортировка;
3) Сортировка вставкой.

Примерно выглядит так для десяти элементов.

1) Сортировка выбором:

Код



int vec[10] = {11, 4, -3, 5, 10, 8, 12, 6, 4, 0};
int i, j, max, nmax;
for (i=0; i<10; i++}
    {
     max=vec[i];
     nmax=i;
     for (j=i; j<10; i++)
         if (max < vec[j])
             {
              max=vec[j];
              nmax=j;
              }
     vec[nmax]=vec[i];
     vec[i]=max;
     }
for(i=0; i<10; i++)

Ответ: 12, 11,10, 8, 6, 5, 4, 4, 0 , -3

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

Это сообщение отредактировал(а) Tyurs92 - 21.5.2011, 00:22

t_gran

Дата 23.5.2011, 07:00 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

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

Код


#include <cstdio>
#include <cstring>

//----------------------------------------------//
inline void Swap(int *a, int *b)
{
   int buff = *a;
   *a = *b;
   *b = buff;
};
//----------------------------------------------//
void SortChoise(int *theArray, unsigned theSize)
{
  for (unsigned i = 0; i < theSize-1; ++i)
   {
      unsigned max = i;
      
      for (unsigned j = i+1; j < theSize; ++j)
      {
         if (theArray[max] < theArray[j])
         {
            max = j;
         }
      }
      Swap(&theArray[max], &theArray[i]);
   }
}
//----------------------------------------------//
void SortBuble(int *theArray, unsigned theSize)
{
   for (unsigned i = 1; i < theSize-1; ++i)
   {
      for (unsigned j = 0; j < theSize-i; ++j)
      {
         int g = j+1;
         if (theArray[j] < theArray[g])
         {
            Swap(&theArray[j], &theArray[g]);
         }
      }
   }
}
//----------------------------------------------//
void SortInsert(int *theArray, unsigned theSize)
{
   for (unsigned i = 1; i < theSize; ++i)
   {
      for (unsigned j = i; (j > 0) && (theArray[j] > theArray[j-1]); --j)
      {
         Swap(&theArray[j], &theArray[j-1]);
      }
   }
}
//----------------------------------------------//
void PrintArray(int *theArray, unsigned theSize)
{
   for (unsigned i = 0; i < theSize; ++i)
   {
      printf("%d ", theArray[i]);
   }
   printf("\n");
}
//----------------------------------------------//
int main()
{
   const int CVecSize = 10;
   const int CVec[CVecSize] = {11, 4, -3, 5, 10, 8, 12, 6, 4, 0};

   int vec[CVecSize];

   memcpy(vec, CVec, CVecSize * sizeof(int));
   SortChoise(vec, CVecSize);
   PrintArray(vec, CVecSize);
   
   memcpy(vec, CVec, CVecSize * sizeof(int));
   SortBuble(vec, CVecSize);
   PrintArray(vec, CVecSize);
   
   memcpy(vec, CVec, CVecSize * sizeof(int));
   SortInsert(vec, CVecSize);
   PrintArray(vec, CVecSize);

   return 0;
}

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

Присоединённый файл ( Кол-во скачиваний: 2 )

sort.7z 3,61 Kb

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

Я знаю, что ничего не знаю© Сократ
user posted image

Tyurs92

Дата 23.5.2011, 22:33 (ссылка)

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

Загрузка ...

Новичок

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

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

Спасибо большое !!! Но не могли бы вы изменить программу, чтобы цифры вводились с экрана.

Примерно всё должно выглядеть следующим образом:

Введите вектор: 12, 4, -3, 5, 10, 8, 12, 6, 4, 0

И затем на экране , мы должны увидеть полную диаграмму сортировки :

12 4 -3 5 10 8 11 6 4 0
12 11 -3 5 10 8 4 6 4 0
12 11 10 5 -3 8 4 6 4 0
12 11 10 8 -3 5 4 6 4 0
12 11 10 8 6 5 4 -3 4 0
12 11 10 8 6 5 4 4 -3 0
12 11 10 8 6 5 4 4 0 -3

Количество операций - это количество строк, и надо сравнить у какого вида сортировки будет сколько операций (строк).

Ещё раз большое спасибо ! Посоветуйте пару книжек для начинающего программиста на которых вы учились , пожалуйста.

t_gran

Дата 24.5.2011, 06:56 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

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

Цитата

Количество операций - это количество строк, и надо сравнить у какого вида сортировки будет сколько операций (строк).

Ну это не совсем верно. Вы ведь таким образом много чего в расчёт не берёте. Ну да ладно, это Ваши проблемы. Вернее, это проблемы Вашего преподавателя.

Вообще, в своё время я требовал, чтобы студенты загружали большие последовательности из файла, а результат выполнения анализировали через профилировщик или на крайний случай использовали функции а-ля GetTickCount.

Код


#include <cstdio>
#include <cstring>

//----------------------------------------------//
void PrintArray(int *theArray, unsigned theSize)
{
   for (unsigned i = 0; i < theSize; ++i)
   {
      printf("%d ", theArray[i]);
   }
   printf("\n");
}
//----------------------------------------------//
inline void Swap(int *a, int *b)
{
   int buff = *a;
   *a = *b;
   *b = buff;
};
//----------------------------------------------//
void SortChoise(int *theArray, unsigned theSize)
{
   for (unsigned i = 0; i < theSize-1; ++i)
   {
      PrintArray(theArray, theSize);

      unsigned max = i;
      
      for (unsigned j = i+1; j < theSize; ++j)
      {
         if (theArray[max] < theArray[j])
         {
            max = j;
         }
      }
      Swap(&theArray[max], &theArray[i]);
   }

   PrintArray(theArray, theSize);
}
//----------------------------------------------//
void SortBuble(int *theArray, unsigned theSize)
{
   for (unsigned i = 1; i < theSize-1; ++i)
   {
      PrintArray(theArray, theSize);

      for (unsigned j = 0; j < theSize-i; ++j)
      {
         int g = j+1;
         if (theArray[j] < theArray[g])
         {
            Swap(&theArray[j], &theArray[g]);
         }
      }
   }

   PrintArray(theArray, theSize);
}
//----------------------------------------------//
void SortInsert(int *theArray, unsigned theSize)
{
   for (unsigned i = 1; i < theSize; ++i)
   {
      PrintArray(theArray, theSize);

      for (unsigned j = i; (j > 0) && (theArray[j] > theArray[j-1]); --j)
      {
         Swap(&theArray[j], &theArray[j-1]);
      }
   }

   PrintArray(theArray, theSize);
}
//----------------------------------------------//
unsigned InputValues(int *theArray, unsigned theMaxSize)
{
   unsigned i = 0;

   bool exit = false;

   while (!exit)
   {
      int val;
      scanf("%d", &val);
      
      if ((val == -1) || (i == theMaxSize))
      {
         exit = true;
      }
      else
      {
         theArray[i++] = val;
      }
   }
   
   return i;
}
//----------------------------------------------//

int main()
{
   const unsigned CMaxSize = 10;
   int initialVector[CMaxSize];

   printf("input elements (input -1 for exit; maximum = %d elements)\n", CMaxSize);
   unsigned size = InputValues(initialVector, CMaxSize);
   
   int vec[size];

   memcpy(vec, initialVector, size * sizeof(int));
   printf("\nchoice sorting\n");
   SortChoise(vec, size);
   
   memcpy(vec, initialVector, size * sizeof(int));
   printf("\nbuble sorting\n");
   SortBuble(vec, size);
   
   memcpy(vec, initialVector, size * sizeof(int));
   printf("\ninsert sorting\n");
   SortInsert(vec, size);

   return 0;
}

Присоединённый файл ( Кол-во скачиваний: 4 )

Sort.7z 4,01 Kb

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

Tyurs92

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

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

Загрузка ...

Новичок

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

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

Спасибо большое !!! Извините меня пожалуйста, я не правильно понял значение слово диаграмма. Надо сделать не числовую, а

графическую столбчатую диаграмму.

Помогите решить любым одним видом сортировки (желательно выбором). Отсортировать по убыванию для 10 членов. Поясните ,

пожалуйста главную часть программы.

Вектор также вводим с экрана.

А теперь диаграмма: вот на данном изображении приведены начальная и конечная диаграммы.

Мы ввели вектор и должны увидеть начальную диаграмму. Потом при нажатии клавиши "Enter" увидеть как поменяются столбцы местами в

диаграмме, и так нажимать пока столбцы станут строго в убывающем порядке( как показано на конечной диаграмме). Имено мы

должны

увидеть как столбцы меняются местами между собой.

Параметры поля : в высоту 400 пикселей (+200 пикселей вверх и -200 пикселей вниз);

Для элемента 1 (единицы) столбик равен 4 (высота) x 4 (ширина) пикселя

Для элемента 2 (двойка) столбик равен 8 x 4 пикселя, ширина всегда 4 пикселя , меняется только высота.

Для элемента 5 (пятёрка) столбик равен 20 х 4 пикселя,

Для элемента -1 равен -4 х 4;

Для остальных чисел будет соответсвенно;

http://i016.radikal.ru/1105/78/f87824d31c9e.jpg

Спасибо вам БОЛЬШОЕ !!!

Это сообщение отредактировал(а) Tyurs92 - 26.5.2011, 18:42

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