Эффективный способ подсчета количества свопов к вставке сортирует массив целых чисел в порядке возрастания

Question

Учитывая массив значений длины n, есть ли способ подсчитать количество перестановок, которые будут выполнены сортировкой вставкой, чтобы отсортировать этот массив по времени лучше, чем O (n ² )?

Например:

arr[]={2 ,1, 3, 1, 2};  // Answer is 4.

Алгоритм:

for i <- 2 to N

    j <- i

 while j > 1 and a[j] < a[j - 1]

       swap a[j] and a[j - 1]  //I want to count this   swaps?

       j <- j - 1

Answer 1

Если вы хотите посчитать количество перестановок, необходимое для сортировки вставок, то вы хотите найти следующее число: для каждого элемента, сколько предыдущих элементов в массиве меньше его?Сумма этих значений равна общему количеству выполненных обменов.

Чтобы найти число, вы можете использовать дерево статистики заказов, сбалансированное двоичное дерево поиска, которое может эффективно подсказать, сколько элементов в деревеменьше, чем некоторый данный элемент.В частности, дерево статистики orde поддерживает O (log n) вставку, удаление, поиск и подсчет того, сколько элементов в дереве меньше некоторого значения.Затем вы можете подсчитать, сколько свопов будет выполнено, следующим образом:

1. Инициализировать новое пустое дерево статистики заказов.
2. Установить счетчик = 0
3. Для каждого массиваэлемент в порядке:
   1. Добавьте элемент в дерево статистики заказов.
   2. Добавьте, чтобы подсчитать количество элементов в дереве меньше добавленной стоимости.
4. Возвращаемое количество,

Это делает O (n) итераций цикла, который занимает O (log n) времени, поэтому общая выполненная работа составляет O (n log n), чтобыстрее, чем метод грубой силы.

---

Если вы хотите посчитать количество перестановок в сортировке выбора, то вы можете использовать тот факт, что сортировка вставкой будет выполнять своп только на k-м проходе, если,после обработки первых k-1 элементов списка элемент в позиции k не является k-м наименьшим элементом.Если вы можете сделать это эффективно, то у нас есть следующий базовый набросок алгоритма:

1. Установить итог = 0
2. Для k = 1 до n:
   1. Если элемент с индексом k не является k-м наибольшим элементом:
      1. Поменяйте его местами с k-м наибольшим элементом.
      2. Всего увеличения
3. Возврат итого

Так, как мы реализуем это эффективно?Нам необходимо эффективно проверять, является ли элемент в данном индексе правильным элементом, а также эффективно находить позицию элемента, которая действительно принадлежит данному индексу.Для этого начните с создания сбалансированного бинарного дерева поиска, которое отображает каждый элемент на его позицию в исходном массиве.Это занимает время O (n log n).Теперь, когда у вас есть сбалансированное дерево, мы можем расширить структуру, назначив каждому элементу дерева позицию в отсортированной последовательности, которой принадлежит этот элемент.Один из способов сделать это - использовать дерево статистики заказов, а другой - перебирать дерево с помощью обхода по порядку, аннотируя каждое значение в дереве своей позицией.

Используя эту структуру, мы можем проверитьO (log n) время, когда элемент находится в правильном положении, просматривая элемент в дереве (время O (log n)), затем просматривая положение в отсортированной последовательности, в котором он должен быть, и в которомположение, в котором он находится в данный момент (помните, что мы установили это при создании дерева).Если он не согласен с нашей ожидаемой позицией, то он находится не в том месте, в противном случае он находится в правильном месте.Кроме того, мы можем эффективно смоделировать обмен двух элементов, посмотрев эти два элемента в дереве (O (log n) общего времени), а затем поменяв их местами в O (1).

В результатемы можем реализовать вышеупомянутый алгоритм за время O (n log n) - O (n log n) времени, чтобы построить дерево, затем n итераций выполнения O (log n) работы, чтобы определить, следует ли поменяться местами.

Надеюсь, это поможет!

Answer 2

Количество чередований последовательных элементов, необходимых для их упорядочения в естественном порядке, равно количеству инверсий в данной перестановке.

Таким образом, решение этой проблемы состоит в том, чтобы найти число инверсий в данном массиве чисел.

Это можно решить в O (n log n), используя сортировку слиянием.

Если на шаге слияния вы скопируете элемент из правого массива, увеличьте глобальный счетчик (который подсчитывает инверсии) на количество элементов, оставшихся в левом массиве. Это сделано потому, что элемент из только что скопированного правого массива вовлечен в инверсию со всеми присутствующими элементами в левом массиве.

Надеюсь, это поможет

Answer 3

package insertoinSortAnalysis;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

    private int[] originalArray;

    public static void main(String[] args) {

        Scanner sc;
        try {
            sc = new Scanner(System.in);

            int TestCases = sc.nextInt();

            for (int i = 0; i < TestCases; i++) {
                int sizeofarray = sc.nextInt();

                Solution s = new Solution();
                s.originalArray = new int[sizeofarray];

                for (int j = 0; j < sizeofarray; j++)
                    s.originalArray[j] = sc.nextInt();

                s.devide(s.originalArray, 0, sizeofarray - 1);
                System.out.println(s.count);
            }

        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    public int[] devide(int[] originalArray, int low, int high) {
        if (low < high) {
            int mid = (low + high) / 2;
            int[] result1 = devide(originalArray, low, mid);
            int[] result2 = devide(originalArray, mid + 1, high);

            return merge(result1, result2);
        }

        int[] result = { originalArray[low] };
        return result;
    }

    private long count = 0;

    private int[] merge(int[] array1, int[] array2) {

        int lowIndex1 = 0;
        int lowIndex2 = 0;
        int highIndex1 = array1.length - 1;
        int highIndex2 = array2.length - 1;
        int result[] = new int[array1.length + array2.length];
        int i = 0;

        while (lowIndex2 <= highIndex2 && lowIndex1 <= highIndex1) {
            int element = array1[lowIndex1];
            while (lowIndex2 <= highIndex2 && element > array2[lowIndex2]) {
                result[i++] = array2[lowIndex2++];
                count += ((highIndex1 - lowIndex1) + 1);
            }
            result[i++] = element;
            lowIndex1++;
        }

        while (lowIndex2 <= highIndex2 && lowIndex1 > highIndex1) {
            result[i++] = array2[lowIndex2++];
        }

        while (lowIndex1 <= highIndex1 && lowIndex2 > highIndex2) {
            result[i++] = array1[lowIndex1++];
        }

        return result;
    }

}

Answer 4

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

Если вас волнует только сложность big-O, ответ будет O(n log n), и вы, вероятно, сможете получить более конкретные оценки (некоторые реальные константы там), если вы посмотрите на анализ некоторых эффективных алгоритмов сортировки на месте как heapsort или smoothsort.

Answer 5

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[200001];
int te[200001];
unsigned long long merge(int arr[],int temp[],int left,int mid,int right)
{
    int i=left;
    int j=mid;
    int k=left;
    unsigned long long int icount=0;
    while((i<=mid-1) && (j<=right))
    {
        if(arr[i]<=arr[j])
        temp[k++]=arr[i++];
        else
        {
            temp[k++]=arr[j++];
            icount+=(mid-i);
        }
    }
    while(i<=mid-1)
    temp[k++]=arr[i++];
    while(j<=right)
    temp[k++]=arr[j++];
    for(int i=left;i<=right;i++)
    arr[i]=temp[i];
    return icount;
}
unsigned long long int mergesort(int arr[],int temp[],int left,int right)
{
    unsigned long long int i=0;
    if(right>left){
        int mid=(left+right)/2;
        i=mergesort(arr,temp,left,mid);
        i+=mergesort(arr,temp,mid+1,right);
        i+=merge(arr,temp,left,mid+1,right);
    }
    return i;
}
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        printf("%llu\n",mergesort(a,te,0,n-1));
    }
    return 0;
}

Answer 6

Каждый своп в сортировке вставки перемещает два смежных элемента - один за другим, один вниз за один - и таким образом «исправляет» одно пересечение.Итак:

• Аннотируйте каждый элемент X с начальным индексом массива Xi.

• Сортируйте элементы с помощью стабильной сортировки (вы можетеиспользуйте быструю сортировку, если вы рассматриваете аннотацию «начальная позиция» как вспомогательный ключ)

• Возвращает половину суммы абсолютных разностей между аннотированной начальной позицией каждого элемента и его конечной позицией (т. е. просто циклчерез аннотации, суммирующие abs (Xi - i)).

Как и большинство других ответов, это O (n) пробел и O (n * log n) время.Если слияние на месте можно изменить для подсчета пересечений, это было бы лучше.Хотя я не уверен, что это возможно.