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

Сортировка Вставкой
Автор Renyxa, 9 лет назад, По-русски

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

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

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

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

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

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

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

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

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

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

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← 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;
}
        → Ответить
  • »
    »
    9 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    Примеры

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

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

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

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

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

    4
1 2 4 3

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

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

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

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

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 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;
}
→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить