Блог пользователя Renyxa

Автор Renyxa, 10 лет назад, По-русски

Как решить эту задачу ?

Дается массив целых чисел. Отсортируйте массив по возрастанию, используя не оптимизированный алгоритм сортировки вставкой . Первая строка содержит число n, количество элементов в массиве. Вторая строка содержит массив. Третья строка содержит чиcло m, номер итерации которую мы должны.

Итерацией считается действительной — если произошли изменения в массиве.

Начальное состояние массива — итерацией с нулевым индексом.

В единственной строке — вывести значения элементов массива на m-ой итерации сортировки.

  • Проголосовать: нравится
  • -18
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится
sort(arr.begin(), arr.begin() + m); // никто не узнает ;)
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -7 Проголосовать: не нравится

    В единственной строке — вывести значения элементов массива на m-ой итерации сортировки.
    По-моему это только частный случай...

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Почему? Сортировка вставками сортирует префикс массива и вставляет линейным проходом очередной элемент на нужную позицию. Через m итераций первые m элементов массива будут отсортированы.

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

        Моё решение таково. Что здесь не так ?

        #include <iostream>
        using namespace std;
        
        int main(){
            int n;
            cin >> n;
            int a[n];
            for(int i = 0; i < n; ++i) cin >> a[i];
            int m, z = 0;
            cin >> m;
            int temp;
           for(;;){
                   if(z == m)break;
           for(int i=1;i<=n;i++){
                    if(z == m)break;
                for(int j=i; j>0 && a[j-1]>a[j];j--){
                    int tmp=a[j-1];
                    a[j-1]=a[j];
                    a[j]=tmp;
                }
                ++z;
            }
        }
            
            for(int i = 0; i < n; ++i)
            if(i != n-1) cout << a[i] << " ";
            else cout << a[i] << endl;
            return 0;
        }
        
  • »
    »
    10 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Решение не подходит. Вот примеры:

    Примеры

    Входные данные

    8
    5346 -43 232 -5 0 3434 1 45
    3
    

    Результат работы

    -43 -5 232 5346 0 3434 1 45
    
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится -13 Проголосовать: не нравится

    Итерацией считается действительной — если произошли изменения в массиве.

    4
    1 2 4 3
    

    1ая итерация: 1 2 4 3

    2ая итерация: 1 2 3 4

    Надо еще учитывать начальное состояние массива.

»
10 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Международный гроссмейстер(Renyxa) :))))

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    long long n;
    cin >> n;
    long long a[n];
    for(int i = 0; i < n; ++i) cin >> a[i];
    long long m, z = 0;
    cin >> m;
    long long temp;
   sort(a, a + m);
    
    for(int i = 0; i < n; ++i)
    if(i != n-1) cout << a[i] << ' ';
    else cout << a[i] << endl;
    return 0;
}
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

встроенная сортировка решает вопрос!)