Сортировка

Меню сайта

Вход на сайт

Мини-чат

Програмка

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]

Страница 1 из 1
1

Сортировка (Сортировка в функциях)

Сортировка

vilgos

Дата: Пт, 03 Апр 2015, 02:29 | Сообщение # 1

Старший программист

Группа: Модераторы

Сообщений: 76

Репутация: 0

Статус: Offline

Сделать программу для сравнения эффективности сортировок.
Результаты работы:
1) Название сортировки
2) Время в милисикундах
3) Все сортировки должны сортировать один и тот же массив. Обязательно! Не каждый раз заново генерированый а однажды.
4) Можно добавить интерактива, типа зацикленость как в калькуляторе..

vilgos

Дата: Пн, 06 Апр 2015, 22:03 | Сообщение # 2

Старший программист

Группа: Модераторы

Сообщений: 76

Репутация: 0

Статус: Offline

Код

#include "stdafx.h"
#include <iostream>
#include <time.h>
#include <Windows.h>
#include <stdlib.h>

using namespace std;

const int N = 1000;

void privetstvie();
int generatsiya();
int glupaya(int mass[N]);
int puzirkovaya(int mass [N]);
int shejkernaya(int mass [N]);
int chetNechet(int mass [N]);
int roscheska(int mass [N]);
void print(int a, int b, int c, int d, int e);

int main()
{
    srand(time(NULL) || clock());
    int massiv [N]= { 0 };
    for (int i = 0; i < N; i++)
    {
       massiv [i]= generatsiya();
    }
    int time_glup = glupaya(massiv);
    int time_puz = puzirkovaya(massiv);
    int time_shejk = shejkernaya(massiv);
    int time_chetN = chetNechet(massiv);
    int time_ros = roscheska(massiv);
    print(time_glup, time_puz, time_shejk, time_chetN, time_ros);
    return 0;
}

void privetstvie(){
    cout << "Sravnenie sortirovok." << endl;
}
int generatsiya(){

    return rand() % 100 + 1;
}
int glupaya(int mass [N]){
    int arr1 [N]= { 0 };
    for (int i = 0; i < N; i++){
       arr1 [i]= mass[i];
    }
    int g = 0;
    int start = clock();
    for (int i = 0; i < (N - 1); i++){

       if (arr1[i]>arr1[i + 1]){
          g = arr1[i];
          arr1 [i]= arr1[i + 1];
          arr1[i + 1] = g;
          i = -1;
       }
    }
    int end = clock();
    return end - start;
}
int puzirkovaya(int mass [N]){
    int arr1 [N]= { 0 };
    for (int i = 0; i < N; i++){
       arr1 [i]= mass[i];
    }
    int g = 0;
    int start = clock();
    for (int i = 0; i < (N - 1); i++){
       for (int j = 0; j< (N - 1) - i; j++){
          if (arr1[j]>arr1[j + 1]){
             g = arr1[j];
             arr1 [j]= arr1[j + 1];
             arr1[j + 1] = g;

          }
       }
    }
    int end = clock();
    return end - start;
}
int shejkernaya(int mass [N]){
    int arr1 [N]= { 0 };
    for (int i = 0; i < N; i++){
       arr1 [i]= mass[i];
    }
    int g = 0;
    int start = clock();
    for (int i = 0; i < (N - 1); i++){
       for (int j = i; j< (N - 1) - i; j++){
          if (arr1[j]>arr1[j + 1]){
             g = arr1[j];
             arr1 [j]= arr1[j + 1];
             arr1[j + 1] = g;

          }
       }
       for (int k = N - 1 - i; k > i; k--){
          if (arr1[k]<arr1[k - 1]){
             g = arr1[k];
             arr1 [k]= arr1[k - 1];
             arr1[k - 1] = g;

          }
       }
    }
    int end = clock();
    return end - start;
}
int chetNechet(int mass [N]){
    int arr1 [N]= { 0 };
    for (int i = 0; i < N; i++){
       arr1 [i]= mass[i];
    }
    int g = 0;
    int l = 0;
    int start = clock();
    for (;;){
       int k = 0;
       for (int j = 0; j< (N - 1); j += 2){
          if (arr1[j]>arr1[j + 1]){
             g = arr1[j];
             arr1 [j]= arr1[j + 1];
             arr1[j + 1] = g;
             k++;
          }
       }

       for (int j = 1; j< (N - 1); j += 2){
          if (arr1[j]>arr1[j + 1]){
             g = arr1[j];
             arr1 [j]= arr1[j + 1];
             arr1[j + 1] = g;
             k++;
          }
       }
       l++;
       if (k == 0)
          break;
    }

    int end = clock();
    return end - start;
}
int roscheska(int mass [N]){
    int K = N;
    int arr [N]= { 0 };
    for (int i = 0; i < N; i++){
       arr [i]= mass[i];
    }
    int start = clock();
    for (;;)
    {
       int count = 0;
       if (K / 1.247330950103979 >= 1)

          K = (int) K / 1.247;

       for (int j = 0; j + K <= N - 1; j++)
       {
          if (arr[j]>arr[j + K])
          {
             int g = arr[j];
             arr [j]= arr[j + K];
             arr[j + K] = g;
             count += 1;
          }
       }

       if (count == 0)
       {
          break;
       }

    }

    int end = clock();
    return end - start;
}
void print(int a, int b, int c, int d, int e){
    cout << "Vremya glupoj sortirovky: " << a << "ms." << endl;
    cout << "Vremya puzirkoj sortirovky: " << b << "ms." << endl;
    cout << "Vremya shejkernoj sortirovky: " << c << "ms." << endl;
    cout << "Vremya sortirovky chetnaya-nechetnaya: " << d << "ms." << endl;
    cout << "Vremya sortirovky roscheska: " << e << "ms." << endl;
    _gettch();
}

akostenko

Дата: Чт, 09 Апр 2015, 22:30 | Сообщение # 3

Выучил типы

Группа: Кодеры

Сообщений: 2

Репутация: 0

Статус: Offline

#include "Header.h";
/*Фунция ввода размера массива пользоватлем, возвращает размер массива*/
int razmer()
{
   int N;
   cout << "Для выхода из программы введите 999" << endl;
   cout << "Введите размер массива: " << endl;
   cin >> N;
   return N;
}
/*Функция выполняющая глупую сортировку, выводит на екран время сортировки в милисикундах*/
void stupid(int* mas, int N)
{
   int counter = 0;
   int start = clock();
   for (int i = 0; i < N - 1; i++){
       if (mas>mas[i + 1]){
           int per = mas;
           mas = mas[i + 1];
           mas[i + 1] = per;
           i = -1;
           counter++;
       }
   }
   int end = clock();
   cout << "Глупая сортировка: " << end - start << " ms " << "перестановок: " << counter << endl;
}
/*Функция выполняющая пузырьковую сортировку, выводит на екран время сортировки в милисикундах*/
void bubble(int* mas, int N)
{
   int counter = 0;
   int tmp;
   int start = clock();
   for (int i = 0; i < N - 1; i++)
   {
       for (int j = 0; j<N - i - 1; j++)
       {
           if (mas
>mas[j + 1])
           {
               tmp = mas;
               mas = mas[j + 1];
               mas[j + 1] = tmp;
               counter++;
           }
       }
   }
   int end = clock();
   cout << "Пузырьковая сортировка: " << end - start << " ms " << "перестановок: " << counter <<endl;
}
/*Функция выполняющая шейкерную сортировку, выводит на екран время сортировки в милисикундах*/
void shake(int* mas, int N)
{
   int counter = 0;
   int tmp;
   int start = clock();
   for (int i = 0; i < N - 1; i++)
   {
       for (int j = i; j<N - i - 1; j++)
       {
           if (mas>mas[j + 1])
           {
               tmp = mas;
               mas = mas[j + 1];
               mas[j + 1] = tmp;
               counter++;
           }
       }
       for (int j = N - i - 1; j >= 0; j--)
       {
           if (mas<mas[j - 1])
           {
               tmp = mas;
               mas = mas[j - 1];
               mas[j - 1] = tmp;
               counter++;
           }
       }
   }
   int end = clock();
   cout << "Шейкерная сортировка: " << end - start << " ms " << "перестановок: " << counter << endl;
}
/*Функция выполняющая четно-нечетную сортировку, выводит на екран время сортировки в милисикундах*/
void chet_nechet(int* arr, int N)
{
   int count=0;
   int counter = 0;
   int tmp;
   int start = clock();
   while (counter >= 0)
   {
       for (int j = 1; j<N - 1; j = j + 2)
       {
           if (arr>arr[j + 1])
           {
               tmp = arr;
               arr = arr[j + 1];
               arr[j + 1] = tmp;
               counter = 1;
               count++;
           }
       }

       for (int j = 0; j<N - 1; j = j + 2)
       {
           if (arr>arr[j + 1])
           {
               tmp = arr;
               arr = arr[j + 1];
               arr[j + 1] = tmp;
               counter = 1;
               count++;
           }
       }
       counter = counter - 1;
   }
   int end = clock();
   cout << "Чет-нечет сортировка: " << end - start << " ms " << "перестановок: " << count << endl;
}
/*Функция выполняющая сортировку вставками, выводит на екран время сортировки в милисикундах*/
void insert(int* mas, int N)
{
   int counter = 0;
   int i,j,tmp;
   int start = clock();
   for (i = 1; i < N; i++)
   {
       tmp = mas;
       for (j = i - 1; j >= 0 && mas > tmp; j--)
       {
           mas[j + 1] = mas;
           counter++;
       }
       mas[j + 1] = tmp;

   }
   int end = clock();
   cout << "Вставками сортировка: " << end - start << " ms " << "перестановок: " << counter << endl;
}
/*Функция выполняющая сортировку расческа, выводит на екран время сортировки в милисикундах*/
int createGap(int gap)
{
   gap = (gap * 10) / 1.3;

   if (gap == 9 || gap == 10)
       gap = 11;

   if (gap < 1)
       gap = 1;

   return gap;
}//end newGap Function
void combSort(int data[], int size)
{
   int counter = 0;
   int gap = size;
   int start = clock();
   while (true) {
       gap = createGap(gap);
       bool swapped = false;

       for (int i = 0; i < size - gap; i++) {
           int j = i + gap;

           if (data > data){
               swap(data, data);
               swapped = true;
               counter++;
           }//end if

       }//end for

       if (gap == 1 && !swapped)
           break;
   }//end for
   int end = clock();
   cout << "Расческа сортировка: " << end - start << " ms " << "перестановок: " << counter << endl;
}//end combSort Function
/*конец расчески*/

int main()
{
   setlocale(LC_ALL, "rus");
   /*=НАЧАЛО=переменной N присваиваем размер размер введенного пользователем массива*/
   while (true)
   {
       int N = razmer();
       /*=КОНЕЦ=переменной N присваиваем размер размер введенного пользователем массива*/
       /*=НАЧАЛО=генерируем массив размера который ввел пользователь*/
       srand(time(NULL));
       int *mas = new int[N];
       int *mass = new int[N];
       int *masss = new int[N];
       int *massss = new int[N];
       int *masssss = new int[N];
       int *massssss = new int[N];
       /*=НАЧАЛО=Выход из программы*/
       if (N == 999)
       {
           delete[] mas;
           delete[] mass;
           delete[] masss;
           delete[] massss;
           delete[] masssss;
           break;
       }
       /*=КОНЕЦ=выход из программы*/
       /*=НАЧАЛО=генерируем массив+делаем копии*/
       for (int i = 0; i < N; i++)
       {
           mas = rand() % 100;
           mass = mas;
           masss = mas;
           massss = mas;
           masssss = mas;
           massssss = mas
;
       }
       /*=КОНЕЦ=генерируем массив размера который ввел пользователь*/
       bubble(mas, N);//пузырьковая
       shake(mass, N);//шейкерная
       chet_nechet(masss, N);//чет-нечет
       insert(massss, N);//вставками
       combSort(masssss, N);//расческа
       //stupid(massssss, N);//глупая
       delete[] mas;
       delete[] mass;
       delete[] masss;
       delete[] massss;
       delete[] masssss;
   }
   system("pause");
   return 0;
}

Сортировка (Сортировка в функциях)

Страница 1 из 1
1