Сортировка: вариации на тему

Опубликовано Sep 3, 2012 в Массивы и строки | 16 коммент.

, ,

Сортировка: вариации на тему

Задание выглядит настолько невинно, что даже неинтересно.

Нужно отсортировать целочисленный массив. Только при этом в написанной программе не должно быть операторов цикла. Таким образом, речь идет о демонстрации использования стандартных библиотечных средств. Желательно показать  разные варианты.

После того, как первая часть благополучно решена, предлагается модифицировать написанный код, чтобы массив сортировался бы, например, так: 

  • сначала бы шли положительные элементы, отсортированные по возрастанию;
  • потом бы шел 0;
  • потом – отрицательные элементы, отсортированные по возрастанию.
      //Given
      int[] arr = {8, -1, 3, 5, 0, -45, -6, 13, 55, 22};
 
      // Result
      // {3, 5, 8, 22, 55, 0, -45, -6, -1}

Автор публикации:

16 Коммент. : “Сортировка: вариации на тему”

  1. Решение на С++:

    #include <algorithm> //Добавлено модератором
     
    bool cmp(int a, int b) {
        if (!a) return b < 0;
        else if (a > 0) return (b > 0) ? a < b : true;
        else return (b < 0) ? a < b : false;
    }
     
    int a[] = {8, 0, -1, 3, 5, 0, -45, -6, 13, 55, 22};
     
    int main() {
        int n = sizeof(a) / sizeof(int);
        sort(a, a + n); // по возрастанию
        sort(a, a + n, cmp); //положительные по возрастанию, ноль, отрицательные по возрастанию
    }
    • Галина says:

      Вполне годится. Нормальное стандартное решение написать и использовать свой компаратор в методе sort.

    • А не проще ли использовать компаратор, который будет рассматривать числа как unsigned? После такой сортировки будет идти сначала 0, затем положительные числа в порядке возрастания, а потом отрицательные числа в порядке возрастания. (В дополнительном коде чем больше отрицательное число, тем больше его бинарное дополнительное представление). Получаем один вызов функции сортировки и остается перенос 0 в нужное положение в массиве.

      • Галина says:

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

  2. Пацык says:
    #include <algorithm>
    #include <iostream>
    #include <vector>
     
    int main()
    {
    	int arr[] = {8, -1, 3, 5, 0, -45, -6, 13, 0, 55, 22};
    	int lengthOfArr_ = sizeof(arr) / sizeof(int);
    	std::sort(arr, arr + lengthOfArr_);
    	int index = std::find(arr, arr + lengthOfArr_, 0) - arr;
    	std::reverse(arr, arr + index);
    	std::reverse(arr, arr + lengthOfArr_);
    	index = std::find(arr, arr + lengthOfArr_, 0) - arr;
    	std::reverse(arr, arr + index);
     
    	std::for_each(arr, arr + lengthOfArr_, [] (int i) { std::cout << i << " "; });
    	std::cout << std::endl;
    	// {3, 5, 8, 13, 22, 55, 0, -45, -6, -1}
    	return 0;
    }
    • Галина says:

      Получится вот что – вроде бы правильно на приведенных данных…

      int arr[] = {8, -1, 3, 5, -45, -6, 13, 55, 22};
      int lengthOfArr_ = sizeof(arr) / sizeof(int);
      std::sort(arr, arr + lengthOfArr_);
       
      int index = std::find(arr, arr + lengthOfArr_, 0) - arr; //index = 3;
       
      std::reverse(arr, arr + index);//-1,-6,-45,0,0,3,5,8,13,22,55
      std::reverse(arr, arr + lengthOfArr_); //55,22,13,8,5,3,0,0,-45,-6,-1
      index = std::find(arr, arr + lengthOfArr_, 0) - arr; 
      //index = 6;
      std::reverse(arr, arr + index);//3,5,8,13,22,55,0,0,-45,-6,-1

      Но нет…
      Если в исходном массиве нет нуля, то реверсирование не работает как нужно…

    • Пацык says:

      исправил недоработку

      #include <algorithm>
      #include <iostream>
       
      int main()
      {
      	int arr[] = {8, -1, 3, 5, 0, -45, -6, 13, 0, 55, 22};
      	int lengthOfArr_ = sizeof(arr) / sizeof(int);
      	std::sort(arr, arr + lengthOfArr_);
      	int negCount_ = 0, posCount_ = 0;
      	//подсчитываем кол-во отрицательных и положительных элементов
      	std::for_each(arr, arr + lengthOfArr_, [&] (int i) mutable {
      		if (i < 0) ++negCount_;
      		else if (i > 0) ++posCount_;
      	});
      	std::reverse(arr, arr + negCount_); // реверс отр элем
      	std::reverse(arr + lengthOfArr_ - posCount_, arr + lengthOfArr_); //реверс пол элем
      	std::reverse(arr, arr + lengthOfArr_); 
      	std::for_each(arr, arr + lengthOfArr_, [] (int i) { std::cout << i << " "; });
      	std::cout << std::endl;
      	// {3, 5, 8, 13, 22, 55, 0, 0, -45, -6, -1}
      	return 0;
      }
      • Галина says:

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

        1) Использование компаратора подсказано библиотечной реализацией метода sort – это ход поймут все.
        2) Сложность “пресловутое O(?)” вашего решения – какова она? Все, что после сортировки: 4 цикла по массиву (1 – явный и 3 из reverse) ее увеличивают по сравнению с вариантом с компаратором.
        3)Все эти вызовы нужно обернуть в одну функцию – нельзя при каждой сортировке массива по этому правилу писать все вот это:

        std::sort(arr, arr + lengthOfArr_);
        	int negCount_ = 0, posCount_ = 0;
        	std::for_each(arr, arr + lengthOfArr_, [&] (int i) mutable {
        		if (i < 0) ++negCount_;
        		else if (i > 0) ++posCount_;
        	});
        	std::reverse(arr, arr + negCount_); 
        	std::reverse(arr + lengthOfArr_ - posCount_, arr + lengthOfArr_); 
        	std::reverse(arr, arr + lengthOfArr_);
        • Пацык says:

          Хорошо. Давайте посчитаем
          цитирую:
          Сложность “пресловутое O(?)” вашего решения – какова она?

          std::sort(arr, arr + lengthOfArr_);
          //n*log n
          std::for_each(arr, arr + lengthOfArr_, [&] (int i) mutable {
          		if (i < 0) ++negCount_;
          		else if (i > 0) ++posCount_;
          	});
          //n
          std::reverse(arr, arr + negCount_);
          std::reverse(arr + lengthOfArr_ - posCount_, arr + lengthOfArr_);
          //два этих реверса сделают n / 2 , если в 
          //массиве нет нулей, если есть, то ...
          std::reverse(arr, arr + lengthOfArr_);
          //n / 2

          итого получим:
          n*log n + n + n/2 + n/2 == n log n + 2*n
          при n = 1024 получаем 12288
          Сортировка с помощью компаратора:
          2 * n*log n
          при n = 1024 получаем 20480

          • Галина says:

            Этого вызова достаточно

            int main() {
                int n = sizeof(a) / sizeof(int);
             
                sort(a, a + n, cmp); 
            }

            Сложность с компаратором – n*log n, а не 2*n*log n
            Сложность с реверсированием – согласна – n*log n + c*n (где с = const)
            Согласна также, что всегда
            n*log n + c*n лучше, чем 2*n*log n при достаточно большом n.

            ЗЫ. Сложность считаем количеством выполнений циклов, предполагая, что в циклах примерно одинаковые по скорости действия. Хотя в сортировке с компаратором будет чуть помедленнее, чем просто
            std::sort(arr, arr + lengthOfArr_);

  3. КотМатроскин says:

    А вот на C#. Просто отсортировать.

     int[] A = { 8, -1, 3, 5, 0, -45, -6, 13, 55, 22 }; Array.Sort(A);
    //или так
     foreach (int arrItem in arr.OrderBy(i => i)) Console.WriteLine(arrItem);
                Console.ReadLine();

    Есть задачка поинтересней – как слить два уже отсортированных массива, сохранив порядок сортировки, не вызывая при этм Sort/OrderBy ни в каком виде?

  4. Артур says:

    Как такой вариант?

    #include "stdafx.h"
    #include <iostream>
    #include <conio.h>
    #include <time.h>
    #include <algorithm>
    #include <functional>
    using namespace std;
     
    void show(int a){cout<<a<<" ";}
    struct randGen{
    	randGen(){srand((unsigned int)time(NULL));}
    	int operator()(int n){return n + rand() % abs(n*2);}
    };
    bool myPred(int a, int b){
    	return a > 0 && (b == 0 || b < 0);
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int sz = 20, dpz = -5; // cin>>sz;
    	int *ar = new int[sz];
    	fill(ar,ar+sz,dpz);
    	transform(ar,ar+sz,ar,randGen());
    	for_each(ar,ar+sz,show); cout<<endl;
    	sort(ar,ar+sz,greater<int>());
    	if(*(ar+sz - sizeof(int)) < 0){
    		reverse(find_if(ar,ar+sz, bind2nd(less<int>(),0)),ar+sz);
    	}
    	if(*ar > 0 && *(ar+sz - sizeof(int)) > 0){
    		reverse(ar,adjacent_find(ar,ar+sz,myPred));
    	}else if(*ar > 0){
    		reverse(ar,adjacent_find(ar,ar+sz,myPred)+1);
    	}
    	for_each(ar,ar+sz,show); cout<<endl;
    	_getch();
    	return 0;
    }

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

Ваш адрес email не будет опубликован.


*