Un moyen efficace de compter le nombre de swaps à insérer trie un tableau d'entiers dans un ordre croissant

Donné un tableau de valeurs de longueur n, il est un moyen de compter le nombre de swaps, qui serait effectuée par l'insertion de tri pour trier ce tableau dans le temps de mieux que O(n²)?

Par exemple :

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

Algorithme:

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

source d'informationauteur Anil Kumar Arya

algorithm arrays c c++sorting

21

Si vous voulez compter le nombre d'échanges nécessaires dans le tri par insertion, alors vous voulez trouver le numéro suivant: pour chaque élément, le nombre d'éléments inn le tableau sont plus petites que? La somme de ces valeurs est alors le nombre total de permutations.

Pour trouver le numéro, vous pouvez utiliser une commande de statistique de l'arbre, l'équilibre binaire un arbre de recherche qui peut efficacement vous dire combien d'éléments dans l'arbre sont plus petites que certains élément donné. Plus précisément, une orde de statistique de l'arbre prend en charge O(log n) insertion, suppression, recherche, et le nombre d'éléments dans l'arbre, à moins de quelque valeur. Vous pouvez alors compter le nombre de swaps sera effectuée comme suit:
1. Initialiser un nouveau, vide afin de statistique de l'arbre.
2. Nombre = 0
3. Pour chaque élément du tableau, dans l'ordre:
  1. Ajouter l'élément à l'ordre de statistique de l'arbre.
  2. Ajouter de compter le nombre d'éléments dans l'arbre inférieur à la valeur ajoutée.
4. Retour comte,
Ce n'est O(n) itérations d'une boucle qui prend O(log n) le temps, de sorte que le total des travaux est de O(n log n), qui est plus rapide que la force brute approche.

Si vous voulez compter le nombre de swaps de tri de la sélection, vous pouvez utiliser le fait que le tri par insertion ne procédera à un échange sur la kième passer si, après le traitement de la première k-1 éléments de la liste, l'élément en position k n'est pas la k-ième plus petit élément. Si vous pouvez faire cela efficacement, nous avons alors le suivant de la base de l'esquisse d'un algorithme:
1. Somme = 0
2. Pour k = 1 à n:
  1. Si l'élément à l'indice k n'est pas la kième plus grand élément:
    
    Il échange avec la kième plus grand élément.
    
    Incrément total
3. Rendement total
Alors, comment pouvons-nous mettre en œuvre de manière efficace? Il nous faut mieux être en mesure de vérifier si l'élément à un index donné est le bon élément, et doivent également efficace de trouver la position de l'élément qui appartient vraiment à un index donné le contraire. Pour ce faire, commencez par en créer un équilibre binaire un arbre de recherche qui fait correspondre à chaque élément de sa position dans le tableau d'origine. Cela prend du temps O(n log n). Maintenant que vous avez l'équilibre de l'arbre, nous pouvons compléter la structure en attribuant à chaque élément dans l'arbre, la position dans la séquence triée que cet élément appartient. Une façon de le faire est avec un ordre statistique de l'arbre, et l'autre pour effectuer une itération sur l'arbre avec un afinde de la traversée, l'annotation de chaque valeur dans l'arbre, avec sa position.

À l'aide de cette structure, nous pouvons vérifier en O(log n) si un élément est dans la bonne position par la recherche de l'élément dans l'arbre (en temps O(log n)), puis, regardant la position dans la séquence triée à laquelle elle devrait être et à la position à laquelle il est actuellement (rappelez-vous que nous avons mis cela en place lors de la création de l'arbre). Si elle n'est pas d'accord avec notre position attendue, alors qu'il est au mauvais endroit, et sinon, il est à la bonne place. Aussi, nous pouvons efficacement simuler un échange de deux éléments en regardant ces deux éléments dans l'arbre (O(log n) temps total) et puis échange de leurs positions en O(1).

Comme un résultat, nous pouvons appliquer l'algorithme ci-dessus en temps O(n log n) O(n log n) le temps de construire l'arbre, puis n itérations de faire de O(log n) travail pour déterminer si ou de ne pas remplacer.

Espérons que cette aide!
8

Le nombre d'échangeurs de suite les éléments nécessaires pour organiser dans leur ordre naturel est égal au nombre d'inversions dans la permutation.

Donc la solution à ce problème est de trouver le nombre d'inversions dans le tableau de nombres.

Cela peut être résolu en temps O(n log n) en utilisant la fusion de tri.

Dans l'étape de fusion et publipostage, si vous copiez un élément à partir de la droite de tableau, incrémenter un compteur global (qui compte des inversions) par le nombre d'éléments restant à gauche dans le tableau. Ceci est fait parce que l'élément à partir de la droite de tableau qui vient d'être copié est impliqué dans l'inversion de tous les éléments présents dans la gauche de la matrice.

Espère que cette aide
1

Je ne suis pas sûr, mais je le soupçonne de trouver le nombre minimum est un problème difficile. Sauf si il y a un raccourci, vous aurez juste être à la recherche pour optimiser tri des réseauxvous devriez être en mesure de trouver de bonnes ressources sur votre moteur de recherche préféré (ou Wikipedia).

Si vous ne se soucient que le big-O de la complexité, la réponse est O(n log n)et vous pouvez probablement obtenir plus concret limites (certaines constantes) si vous regardez l'analyse de certains efficace en place des algorithmes de tri comme heapsort ou smoothsort.

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;
}
}

0

Chaque swap dans le tri d'insertion se déplace de deux éléments adjacents - un par un, un par un et de `corrige' un seul passage en le faisant. Donc:
- Annoter chaque élément, X, avec son premier index de tableau Xi.
- Trier les éléments à l'aide d'un tri stable (vous pouvez utiliser quicksort, si vous traiter de la "position initiale" de l'annotation comme un mineur)
- Retour moitié de la somme des différences absolues entre chaque élément annoté de la position initiale et la position finale (c'est à dire juste en boucle à travers les annotations de sommation abs(Xi - i)).
Comme la plupart des autres réponses, c'est O(n) et O(n*log n) fois. Si une fusion pourrait être modifiée à compter les passages à niveau, ce serait mieux. Je ne suis pas sûr que ça peut bien.

#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;
}

Vous devez vous connecter pour publier un commentaire.