Выполнить сортировку массива двумя способами

Комментарии

1. 

   Arthur

   28.02.2017

   /*Сравниваются пять алгоритмов сортировки:
     - сортировка выбором
     - шейкер сортировка
     - сортировка вставками
     - пузырьковая сортировка
     - сортировка методом Шелла */
   #include<iostream>
   #include<cstdlib>
   #include <ctime>
   using namespace std;
   
   template<class Item>
   void exch(Item &A, Item &B)
   {
       Item t = A;
       A = B;
       B = t;
   }
   //----------------------------------------------------------
   template<class Item>
   void compexch(Item &A, Item &B)
   {
       if(B < A) exch(A, B);
   }
   //-------------------------------------------------------
   //Сортировка выбором
   template<class Item>
   int selection(Item a[], int l, int r)
   {
      int startTime  = 0;
      int endTime    = 0;
   
      startTime = clock();
      for(int i = l; i<r; i++)
      {
          int min = i;
          for(int j = i + 1; j<=r; j++)
             if(a[j] < a[min])
                 min = j;
          exch(a[i], a[min]);
      }
       endTime = clock();
   
       return (endTime - startTime);
   }
   //----------------------------------------------------------
   //Шейкер сортировка
   template<class Item>
   int shaker(Item a[], int l, int r)
   {
      int startTime  = 0;
      int endTime    = 0;
   
      int left = l, right = r;
   
      startTime = clock();
   
      while(left<right)
      {
          for(int i = left; i<right; i++)
               compexch(a[i], a[i+1]);
   
          right--;
          for(int i = right; i>left; i--)
                compexch(a[i-1], a[i]);
   
          left++;
       }
       endTime = clock();
   
       return (endTime - startTime);
   }
   //-------------------------------------------------
   //Сортировка вставками
   template<class Item>
   int insertion(Item a[], int l, int r)
   {
      int startTime  = 0;
      int endTime    = 0;
   
      int i;
      startTime = clock();
      for( i = r; i<l; i--)
          compexch(a[i-1], a[i]);
   
      for( i = l+2; i<=r; i++)
      {
          int j = i;
          Item v = a[i];
          while(v < a[j-1])
          {
              a[j] = a[j-1];  j--;
          }
         a[j] = v;
      }
      endTime = clock();
   
      return (endTime - startTime);
   }
   //-----------------------------------------------------------
   //Пузырьковая сортировка
   template<class Item>
   int bubble(Item a[], int l, int r)
   {
      int startTime  = 0;
      int endTime    = 0;
      startTime = clock();
   
      for(int i = l; i<r; i++)
         for(int j = r; j>i; j--)
            compexch(a[j-1], a[j]);
   
      endTime = clock();
   
      return (endTime - startTime);
   }
   //------------------------------------------------------------------
   //сортировка методом Шелла
   template<class Item>
   int shellsort(Item a[], int l, int r)
   {
      int h;
      int startTime  = 0;
      int endTime    = 0;
      startTime = clock();
   
      for(h = 1; h<=(r-1)/9; h = 3*h+1);
      for(  ; h>0; h/=3)
        for(int i = l+h; i <= r; i++)
        {
          int j = i;
          Item v = a[i];
          while(j >= l+h && v < a[j-h])
          {
              a[j] = a[j-h];
              j -= h;
          }
          a[j] = v;
        }
        endTime = clock();
   
      return (endTime - startTime);
   }
   //------------------------------------------------------------------
   //Заполнение массива
   template<class Item>
   void randmass(Item *a, int N)
   {
     for(int i = 0; i<N; i++)
       a[i] = 1000*(1.0*rand()/RAND_MAX);
   }
   //Показать массив
   template<class Item>
   void showmass(Item *a, int N)
   {
      for(int i = 0; i<N; i++)
       cout<<a[i]<<"  ";
   }
   //---------------------------------------------------------------
   int main()
   {
    const int N = 10000;
    int *a = new int[N];
   
    setlocale(LC_ALL, "rus");
   
    cout<<"Результаты тестов: "<<endl;
    randmass(a, N);
    cout<<"Сортировка методом выбора: "<<selection(a, 0, N-1)<<endl;
   
    randmass(a, N);
    cout<<"Шейкер сортировка:         "<<shaker(a, 0, N-1)<<endl;
   
    randmass(a, N);
    cout<<"Сортировка вставками:      "<<insertion(a, 0, N-1)<<endl;
   
    randmass(a, N);
    cout<<"Пузырьковая сортировка:    "<<bubble(a, 0, N-1)<<endl;
   
    randmass(a, N);
    cout<<"Сортировка методом Шелла:  "<<shellsort(a, 0, N-1)<<endl;
   
    return 0;
   }

   Войдите, чтобы ответить
2. 

   Вова Качанов

   27.06.2015

   Вот моё:

   #include <iostream>
   #include <cstdlib>
   #include <ctime>
   
   using namespace std;
   int sort1(int *arr,int n);
   int sort2(int *arr,int n);
   
   void swap(int *mas,int a)
   {
       int tmp;
       tmp=mas[a];
       mas[a]=mas[a-1];
       mas[a-1]=tmp;
   }
   
   int main()
   {
       srand(time(0));
    const int n=10000;
    int s_arr[n];
    for (int i=0;i<n;i++) {s_arr[i]=rand()%100+1;
    //cout<<s_arr[i]<<" ";
    }
    unsigned int t1=sort1(s_arr,n);
    cout<<endl<<"selected sort:"<<t1<<endl;
    unsigned int t2=sort2(s_arr,n);
    cout<<"shaker sort: "<<t2<<endl;
   }
   
   int sort1(int *arr,int n)
   {
       int mini=0,x=0,k=0;
       unsigned int start_t=clock();
       for (int i=0;i<n;i++)
       {
           mini=arr[i];
          // cout<<mini<<" ";
           for (int j=i+1;j<n;j++) if (arr[j]<mini) {k=j;mini=arr[j];}
           if (arr[i]!=mini){
           x=arr[i]; arr[i]=mini; arr[k]=x;
           }
           //cout<<mini<<endl;
       }
       unsigned int end_t=clock();
       //for (int i=0;i<n;i++) {cout<<arr[i]<<" ";}
       return end_t-start_t;
   }
   int sort2(int *arr,int n)
   {
        unsigned int start_t=clock();
      int left,right,i;
      left=1;
      right=n;
      while (left<=right)
      {
          for (i=right;i>=left;i--)
               if (arr[i-1]>=arr[i]) swap(arr,i);
               left++;
          for (i=left;i<=right;i++)
               if (arr[i-1]>=arr[i]) swap(arr,i);
               right--;
      }
          unsigned int end_t=clock();
      //for (i=0;i<n;i++) cout<<arr[i]<<" ";
     // cout<<endl;
      return end_t-start_t;
   }

   Войдите, чтобы ответить
3. 

   petruska

   31.10.2014

   Мой вариант

   #include "stdafx.h"  //here all librarys
   
   int SingleSort(int A[],int SIZE);
   int ShakeSort(int A[],int SIZE);
   
   int _tmain(int argc, _TCHAR* argv[])
   {
   	srand(time(NULL));
   
   	int SIZE=0;
   	cout << "Enter size of arrays: ";
   	cin >>SIZE;
   	int *A= new int[SIZE];
   	int *B= new int[SIZE];
   
   	for (int i=0; i < SIZE; i++)
   	{
   		A[i]=rand() % 100;
   		B[i]=rand() % 100;
   	}
   
   	int res1=SingleSort(A,SIZE);
   	int res2=ShakeSort(B,SIZE);
   	cout << "Resolt:" <<endl;
   	cout << "Single array sort was completed for: " <<res1/1000.0<< " seconds!"<<endl;
   	cout << "Single array sort was completed for: " <<res2/1000.0<< " seconds!"<<endl;
   	
   	delete []A;
   	delete []B;
   
           return 0;
   }
   
   int SingleSort(int A[],int SIZE)
   {
   	int start_time=clock();
   	
   	for (int i = 0; i < SIZE - 1; i++)
   	{
           int min = i;
   		for(int j = i + 1; j < SIZE; j++)
   		{
               if(A[j] < A[min])
                   min = j;
           }
           if(min != i) 
               swap(A[i],A[min]);
       }
   
       int end_time=clock();
       int resolt_time=end_time-start_time;
       return resolt_time;
   }
   
   int ShakeSort(int B[],int SIZE)
   {
       int start_time=clock();
   	int Left, Right;
       Left = 0;
       Right = SIZE - 1;
   
       do
       {
           for (int i = Right; i > Left; i--)
           {
               if (B[i] < B[i - 1])
               {
                   swap(B[i], B[i-1]);
               }
           }
   
           Left = Left + 1;
   
           for (int i = Left; i < Right; i++)
           {
               if (B[i] > B[i + 1])
               {
                   swap(B[i],B[i + 1]);
               }
           }
    
           Right = Right - 1;
       }
       while (Left <= Right);
   
       int end_time=clock();
       int resolt_time=end_time-start_time;
       return resolt_time;
   }

   Войдите, чтобы ответить
4. 

   Liliia

   28.10.2013

   Предлагаю еще  один вариант решения.

   #include <iostream>
   #include <iomanip>
   #include <ctime> 
   
   int SortOtbor(int[], int);//прототип функции Сортировка выбором
   int ShakerSort(int[], int);//прототип функции Шейкерной сортировки
   using namespace std;
   
   int main()
   {
   	setlocale(LC_ALL, "rus");
   
   	const int size = 4000; //размер массива
   	int *array = new int [size];
   	int *array2 = new int [size];//создаем еще один массив, чтобы обе функции сортировок, использовали идентичные масивы(копия массива array)
   
   	int timeOfSortArray = 0;
   	int timeOfSortArray2 = 0;
   
   	//заполним массивы случайными числами от 1-го до 800-та
   	srand(time(NULL));
   
   	for(int i = 0; i < size; i++)
   	{
   		array[i] = 1 + rand() % 800;
   		array2[i] = array[i];//копируем значения первого массива во второй, чтобы использовать его в функции шейкерной сортировки
   	}
   
   
   	//выводим исходный (неотсортированный) массив на экран
   	cout << "Неотсортированный массив: " << endl;
   	for (int i = 0; i < size; i++)
   		cout << setw(4) << array[i];
   
   	cout << endl << endl;
   
   	timeOfSortArray = SortOtbor(array, size);
   
   	//выводим отсортированный массив (выбором) на экран
   	cout << "Отсортированный массив (выбором): " << endl;
   	for (int i = 0; i < size; i++)
   		cout << setw(4) << array[i];
   
   	cout << endl << endl;
   
   	timeOfSortArray2 = ShakerSort(array2, size);
   
   	//выводим отсортированный массив ("Шекером") на экран
   	cout << "Отсортированный массив (\"Шекером\"): " << endl;
   	for (int i = 0; i < size; i++)
   		cout << setw(4) << array2[i];
   
   	cout << endl << endl;
   
   	cout << "На сотрировку массива методом выбора потрачено: " << timeOfSortArray << " милисекунд!\n\n";
   	cout << "На сотрировку массива методом \"Шейкер\" потрачено: " << timeOfSortArray2 << " милисекунд!\n\n";
   
   	if (timeOfSortArray < timeOfSortArray2)
   	{
   		cout << "Более эффективным оказался метод сортировки выбором!" << endl << endl;
   	}
   		else if (timeOfSortArray2 < timeOfSortArray)
   		{
   			cout << "Более эффективным оказался метод сортировки \"Шейкер\"!" << endl << endl;
   		}
   			else cout << "Эффективность методов сортировки в данном случае равна!" << endl << endl;
   
   	delete [] array2;//освобождаем память
   	delete [] array;
   
   	return 0;
   }
   
   int SortOtbor(int Array[], int Size)
   {
   	int startTime = 0; // начальное время работы функции сортировки
   	int endTime = 0; // конечное времяработы функции сортировки
   	int searchTime = 0; //продолжительность работы функции сортировки	
   
   	int min; //минимальный элемент в массиве
   	int index; 
   	int temp; // временная переменная для хранения минимального значения элемента
   
   	startTime = clock(); //начинаем отсчет продолжительности сортировки
   
   		for (int i = Size - 1; i >= 1; i--)
   		{ 
   			//задаем начальные значения
   			min = Array[i];
   			index = i;
   
   			//цикл перебора элементов массива
   			for (int j = i - 1; j >= 0; j--)
   			{
   				//находим минимальный элемент
   				if (min > Array[j])
   				{
   					//запоминаем минимальный элемент и его индекс
   					min = Array[j];
   					index = j;
   				}
   			}
   
   			//запоминаем минимум
   			temp = Array[index];
   
   
   			for(int x = index; x < i; x++)//сдвигаем элементы влево
   			{
   				Array[x] = Array[x+1];
   			}
   
   			Array[i] = temp;
   		}
   		
   	endTime = clock(); // конечное время работы функции сортировки
   
   	return searchTime = (endTime - startTime); //искомое время работы функции ;
   }
   
   
   int ShakerSort(int Array2[], int Size)
   {
   	int startTime = 0; // начальное время работы функции сортировки
   	int endTime = 0; // конечное времяработы функции сортировки
   	int searchTime = 0; //продолжительность работы функции сортировки	
   
   	int temp; //буфер 
   
   	int Left, Right; //границы сортировки
   
   	Left = 1;
   	Right = Size - 1;
   
   	startTime = clock(); //начинаем отсчет продолжительности сортировки
   
   	do
   	{
   		for (int i = Right, j = Left; i >= Left, j <= Right; i--, j++)
   		{
   			if (Array2[i - 1] > Array2[i])
   			{
   				temp = Array2[i];
   				Array2[i] = Array2[i - 1];
   				Array2[i - 1] = temp;
   			}
   
   			if (Array2[j - 1] > Array2[j])
   			{
   				temp = Array2[j];
   				Array2[j] = Array2[j - 1];
   				Array2[j - 1] = temp;
   			}
   
   		}
   
   		Left = Left + 1;
   		Right = Right - 1;
   	} while (Left <= Right);
   
   	endTime = clock(); // конечное время работы функции сортировки
   
   	return searchTime = (endTime - startTime); //искомое время работы функции ;
   }

   Войдите, чтобы ответить

Оставить комментарий

Нажмите, чтобы отменить ответ.

Вы должны войти, чтобы оставить комментарий.