Comment trouver le kème plus grand élément dans un tableau non trié de longueur n dans O (n)?

Je crois qu'il existe un moyen de trouver le kème plus grand élément dans un tableau non trié de longueur n dans O (n). Ou peut-être que c'est O (n) «attendu» ou quelque chose. Comment peut-on le faire?

C'est ce qu'on appelle trouver la statistique d'ordre k . Il existe un algorithme aléatoire très simple (appelé quickselect ) prenant le O(n)temps moyen, le O(n^2)pire des cas, et un algorithme non aléatoire assez compliqué (appelé introselect ) prenant le O(n)pire des cas. Il y a quelques informations sur Wikipédia , mais ce n'est pas très bon.

Tout ce dont vous avez besoin se trouve dans ces diapositives PowerPoint . Pour extraire l'algorithme de base de l'algorithme le O(n)plus défavorable (introsélection):

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

Il est également très bien détaillé dans le livre Introduction to Algorithms de Cormen et al.

Si vous voulez un vrai O(n)algorithme, par opposition à O(kn)quelque chose comme ça, alors vous devriez utiliser quickselect (c'est essentiellement quicksort où vous jetez la partition qui ne vous intéresse pas). Mon prof a une excellente synthèse, avec l'analyse d'exécution: ( référence )

L'algorithme QuickSelect trouve rapidement le k-ème plus petit élément d'un tableau d' néléments non triés . Il s'agit d'un RandomizedAlgorithm , nous calculons donc le temps d'exécution prévu le plus défavorable .

Voici l'algorithme.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

Quel est le temps d'exécution de cet algorithme? Si l'adversaire retourne des pièces pour nous, nous pouvons constater que le pivot est toujours l'élément le plus grand et kest toujours 1, ce qui donne un temps d'exécution de

T(n) = Theta(n) + T(n-1) = Theta(n2)

Mais si les choix sont bien aléatoires, le temps de fonctionnement attendu est donné par

T(n) <= Theta(n) + (1/n) ∑i=1 to nT(max(i, n-i-1))

où nous faisons l'hypothèse non entièrement raisonnable que la récursion atterrit toujours dans le plus grand de A1ou A2.

Imaginons cela T(n) <= anpour certains a. Ensuite, nous obtenons

T(n) 
 <= cn + (1/n) ∑i=1 to nT(max(i-1, n-i))
 = cn + (1/n) ∑i=1 to floor(n/2) T(n-i) + (1/n) ∑i=floor(n/2)+1 to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n T(i)
 <= cn + 2 (1/n) ∑i=floor(n/2) to n ai

et maintenant, d'une manière ou d'une autre, nous devons obtenir la somme horrible à droite du signe plus pour absorber celle cnde gauche. Si nous le relions juste comme , nous obtenons à peu près . Mais c'est trop grand - il n'y a pas de place pour ajouter un supplément . Développons donc la somme en utilisant la formule de série arithmétique:2(1/n) ∑i=n/2 to n an2(1/n)(n/2)an = ancn

∑i=floor(n/2) to n i  
 = ∑i=1 to n i - ∑i=1 to floor(n/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

où nous profitons du fait que n est "suffisamment grand" pour remplacer les floor(n/2)facteurs laids par le plus propre (et plus petit) n/4. Nous pouvons maintenant continuer avec

cn + 2 (1/n) ∑i=floor(n/2) to n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

fournis a > 16c.

Cela donne T(n) = O(n). C'est clairement Omega(n), donc nous obtenons T(n) = Theta(n).

Un rapide Google à ce sujet («kème plus grand tableau d'éléments») a renvoyé ceci: http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(c'était spécifiquement pour 3d plus grand)

et cette réponse:

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

Vous aimez le tri rapide. Choisissez un élément au hasard et enfoncez tout plus haut ou plus bas. À ce stade, vous saurez quel élément vous avez réellement choisi, et si c'est le kème élément que vous avez terminé, sinon vous répétez avec le bac (supérieur ou inférieur), que le kème élément tomberait. Statistiquement parlant, l'heure il faut pour trouver que le kième élément croît avec n, O (n).

Un compagnon de programmeur pour l'analyse d'algorithmes donne une version qui est O (n), bien que l'auteur déclare que le facteur constant est si élevé, vous préféreriez probablement la méthode naïve de trier la liste puis de sélectionner.

J'ai répondu à la lettre de ta question :)

La bibliothèque standard C ++ a presque exactement cet appel de fonctionnth_element , bien qu'elle modifie vos données. Il a prévu un temps d'exécution linéaire, O (N), et il effectue également un tri partiel.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

Bien qu'il ne soit pas très sûr de la complexité de O (n), mais il sera sûr d'être entre O (n) et nLog (n). Assurez-vous également d'être plus proche de O (n) que de nLog (n). La fonction est écrite en Java

public int quickSelect(ArrayList<Integer>list, int nthSmallest){
    //Choose random number in range of 0 to array length
    Random random =  new Random();
    //This will give random number which is not greater than length - 1
    int pivotIndex = random.nextInt(list.size() - 1); 

    int pivot = list.get(pivotIndex);

    ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
    ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();

    //Split list into two. 
    //Value smaller than pivot should go to smallerNumberList
    //Value greater than pivot should go to greaterNumberList
    //Do nothing for value which is equal to pivot
    for(int i=0; i<list.size(); i++){
        if(list.get(i)<pivot){
            smallerNumberList.add(list.get(i));
        }
        else if(list.get(i)>pivot){
            greaterNumberList.add(list.get(i));
        }
        else{
            //Do nothing
        }
    }

    //If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list 
    if(nthSmallest < smallerNumberList.size()){
        return quickSelect(smallerNumberList, nthSmallest);
    }
    //If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
    //The step is bit tricky. If confusing, please see the above loop once again for clarification.
    else if(nthSmallest > (list.size() - greaterNumberList.size())){
        //nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in 
        //smallerNumberList
        nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
        return quickSelect(greaterNumberList,nthSmallest);
    }
    else{
        return pivot;
    }
}

J'ai implémenté la recherche de kth minimum dans n éléments non triés en utilisant la programmation dynamique, en particulier la méthode des tournois. Le temps d'exécution est O (n + klog (n)). Le mécanisme utilisé est répertorié comme l'une des méthodes sur la page Wikipédia sur l'algorithme de sélection (comme indiqué dans l'une des publications ci-dessus). Vous pouvez lire sur l'algorithme et également trouver du code (java) sur ma page de blog Finding Kth Minimum . De plus, la logique peut faire un classement partiel de la liste - retourner d'abord K min (ou max) en temps O (klog (n)).

Bien que le code fourni donne kth minimum, une logique similaire peut être utilisée pour trouver le kth maximum dans O (klog (n)), en ignorant le travail préalable effectué pour créer un arbre de tournoi.

Vous pouvez le faire dans O (n + kn) = O (n) (pour k constant) pour le temps et O (k) pour l'espace, en gardant une trace des k plus grands éléments que vous avez vus.

Pour chaque élément du tableau, vous pouvez parcourir la liste des k plus grands et remplacer le plus petit élément par le nouveau s'il est plus grand.

La solution de tas prioritaire de Warren est plus nette cependant.

Sélection rapide sexy en Python

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]

Trouvez la médiane du tableau en temps linéaire, puis utilisez la procédure de partitionnement exactement comme dans le tri rapide pour diviser le tableau en deux parties, les valeurs à gauche de la médiane étant inférieures (<) à la médiane et à droite supérieures à (>) la médiane , cela aussi peut être fait en temps linéaire, maintenant, allez à la partie du tableau où se trouve le kième élément, maintenant la récurrence devient: T (n) = T (n / 2) + cn qui me donne O (n) global.

Vous trouverez ci-dessous le lien vers une implémentation complète avec une explication assez détaillée du fonctionnement de l'algorithme de recherche du Kème élément dans un algorithme non trié. L'idée de base est de partitionner le tableau comme dans QuickSort. Mais afin d'éviter les cas extrêmes (par exemple, lorsque le plus petit élément est choisi comme pivot à chaque étape, de sorte que l'algorithme dégénère en temps d'exécution O (n ^ 2)), une sélection de pivot spéciale est appliquée, appelée algorithme médiane des médianes. L'ensemble de la solution s'exécute en temps O (n) dans le pire et dans le cas moyen.

Voici le lien vers l'article complet (il s'agit de trouver Kth le plus petit élément, mais le principe est le même pour trouver Kth le plus grand ):

Trouver le Kth le plus petit élément dans un tableau non trié

Selon cet article Trouver le Kème élément le plus grand dans une liste de n éléments, l'algorithme suivant prendra du O(n)temps dans le pire des cas.

1. Divisez le tableau en n / 5 listes de 5 éléments chacune.
2. Trouvez la médiane dans chaque sous-tableau de 5 éléments.
3. Retrouver récursivement la médiane de toutes les médianes, appelons-la M
4. Partitionnez le tableau en deux sous-tableaux Le premier sous-tableau contient les éléments plus grands que M, disons que ce sous-tableau est a1, tandis que les autres sous-tableaux contiennent les éléments plus petits que M., appelons ce sous-tableau a2.
5. Si k <= | a1 |, retourne la sélection (a1, k).
6. Si k− 1 = | a1 |, retourne M.
7. Si k> | a1 | + 1, retourne la sélection (a2, k −a1 - 1).

Analyse: Comme suggéré dans le document original:

Nous utilisons la médiane pour partitionner la liste en deux moitiés (la première moitié, si k <= n/2, et la seconde moitié sinon). Cet algorithme prend du temps cnau premier niveau de récursivité pour une constante c, cn/2au niveau suivant (puisque nous récursions dans une liste de taille n / 2), cn/4au troisième niveau, et ainsi de suite. Le temps total pris est cn + cn/2 + cn/4 + .... = 2cn = o(n).

Pourquoi la taille de la partition est prise 5 et non 3?

Comme mentionné dans le document original :

La division de la liste par 5 assure une répartition dans le pire des cas de 70 à 30. Au moins la moitié des médianes est supérieure à la médiane des médianes, donc au moins la moitié des n / 5 blocs ont au moins 3 éléments et cela donne une 3n/10répartition, qui signifie que l'autre partition est de 7n / 10 dans le pire des cas. Cela donne T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, le pire temps de fonctionnement est O(n).

Maintenant, j'ai essayé d'implémenter l'algorithme ci-dessus comme:

public static int findKthLargestUsingMedian(Integer[] array, int k) {
        // Step 1: Divide the list into n/5 lists of 5 element each.
        int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
        // Step 2: Find pivotal element aka median of medians.
        int medianOfMedian =  findMedianOfMedians(array, noOfRequiredLists);
        //Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
        List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
        List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
        for (Integer element : array) {
            if (element < medianOfMedian) {
                listWithSmallerNumbers.add(element);
            } else if (element > medianOfMedian) {
                listWithGreaterNumbers.add(element);
            }
        }
        // Next step.
        if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
        else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
        else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
        return -1;
    }

    public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
        int[] medians = new int[noOfRequiredLists];
        for (int count = 0; count < noOfRequiredLists; count++) {
            int startOfPartialArray = 5 * count;
            int endOfPartialArray = startOfPartialArray + 5;
            Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
            // Step 2: Find median of each of these sublists.
            int medianIndex = partialArray.length/2;
            medians[count] = partialArray[medianIndex];
        }
        // Step 3: Find median of the medians.
        return medians[medians.length / 2];
    }

Par souci de clarté, un autre algorithme utilise la file d'attente prioritaire et prend du temps O(nlogn).

public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums) {
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements - k + 1 > 0) {
            p = pq.poll();
            k++;
        }

        return p;
    }

Ces deux algorithmes peuvent être testés comme:

public static void main(String[] args) throws IOException {
        Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
        System.out.println(findKthLargestUsingMedian(numbers, 8));
        System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
    }

La sortie attendue est: 18 18

Que diriez-vous de cette approche

Maintenez a buffer of length ket a tmp_max, obtenir tmp_max est O (k) et se fait n fois donc quelque chose commeO(kn)

Est-ce bien ou ai-je raté quelque chose?

Bien qu'il ne bat pas le cas moyen de la sélection rapide et le pire des cas de la méthode des statistiques médianes, il est assez facile à comprendre et à mettre en œuvre.

parcourir la liste. si la valeur actuelle est plus grande que la plus grande valeur stockée, stockez-la en tant que valeur la plus grande et faites tomber les 1-4 et 5 supprime la liste. Sinon, comparez-le au numéro 2 et faites la même chose. Répétez, en le comparant aux 5 valeurs stockées. cela devrait le faire dans O (n)

je voudrais suggérer une réponse

si nous prenons les k premiers éléments et les trions dans une liste chaînée de k valeurs

maintenant, pour toutes les autres valeurs, même dans le pire des cas, si nous faisons un tri par insertion pour les valeurs nk de repos, même dans le pire des cas, le nombre de comparaisons sera k * (nk) et pour les valeurs k précédentes à trier, que ce soit k * (k- 1) il en résulte que (nk-k) qui est o (n)

à votre santé

Une explication de l'algorithme médiane des médianes pour trouver le k-ième plus grand entier sur n peut être trouvée ici: http://cs.indstate.edu/~spitla/presentation.pdf

L'implémentation en c ++ est ci-dessous:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMedian(vector<int> vec){
//    Find median of a vector
    int median;
    size_t size = vec.size();
    median = vec[(size/2)];
    return median;
}

int findMedianOfMedians(vector<vector<int> > values){
    vector<int> medians;

    for (int i = 0; i < values.size(); i++) {
        int m = findMedian(values[i]);
        medians.push_back(m);
    }

    return findMedian(medians);
}

void selectionByMedianOfMedians(const vector<int> values, int k){
//    Divide the list into n/5 lists of 5 elements each
    vector<vector<int> > vec2D;

    int count = 0;
    while (count != values.size()) {
        int countRow = 0;
        vector<int> row;

        while ((countRow < 5) && (count < values.size())) {
            row.push_back(values[count]);
            count++;
            countRow++;
        }
        vec2D.push_back(row);
    }

    cout<<endl<<endl<<"Printing 2D vector : "<<endl;
    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            cout<<vec2D[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

//    Calculating a new pivot for making splits
    int m = findMedianOfMedians(vec2D);
    cout<<"Median of medians is : "<<m<<endl;

//    Partition the list into unique elements larger than 'm' (call this sublist L1) and
//    those smaller them 'm' (call this sublist L2)
    vector<int> L1, L2;

    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            if (vec2D[i][j] > m) {
                L1.push_back(vec2D[i][j]);
            }else if (vec2D[i][j] < m){
                L2.push_back(vec2D[i][j]);
            }
        }
    }

//    Checking the splits as per the new pivot 'm'
    cout<<endl<<"Printing L1 : "<<endl;
    for (int i = 0; i < L1.size(); i++) {
        cout<<L1[i]<<" ";
    }

    cout<<endl<<endl<<"Printing L2 : "<<endl;
    for (int i = 0; i < L2.size(); i++) {
        cout<<L2[i]<<" ";
    }

//    Recursive calls
    if ((k - 1) == L1.size()) {
        cout<<endl<<endl<<"Answer :"<<m;
    }else if (k <= L1.size()) {
        return selectionByMedianOfMedians(L1, k);
    }else if (k > (L1.size() + 1)){
        return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
    }

}

int main()
{
    int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};

    vector<int> vec(values, values + 25);

    cout<<"The given array is : "<<endl;
    for (int i = 0; i < vec.size(); i++) {
        cout<<vec[i]<<" ";
    }

    selectionByMedianOfMedians(vec, 8);

    return 0;
}

Il y a aussi l'algorithme de sélection de Wirth , qui a une implémentation plus simple que QuickSelect. L'algorithme de sélection de Wirth est plus lent que QuickSelect, mais avec certaines améliorations, il devient plus rapide.

Plus en détail. En utilisant l'optimisation MODIFIND de Vladimir Zabrodsky et la sélection de pivot de la médiane de 3 et en prêtant une attention aux étapes finales de la partie de partitionnement de l'algorithme, j'ai trouvé l'algorithme suivant (imaginablement nommé "LefSelect"):

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

Dans les benchmarks que j'ai faits ici , LefSelect est 20-30% plus rapide que QuickSelect.

Solution Haskell:

kthElem index list = sort list !! index

withShape ~[]     []     = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys

sort []     = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
  where
   ls = filter (<  x)
   rs = filter (>= x)

Cela implémente la médiane des solutions médianes en utilisant la méthode withShape pour découvrir la taille d'une partition sans réellement la calculer.

Voici une implémentation C ++ de QuickSelect aléatoire. L'idée est de choisir au hasard un élément pivot. Pour implémenter une partition aléatoire, nous utilisons une fonction aléatoire, rand () pour générer un index entre l et r, échanger l'élément à un index généré aléatoirement avec le dernier élément, et enfin appeler le processus de partition standard qui utilise le dernier élément comme pivot.

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)  // If position is more, recur for left subarray
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Standard partition process of QuickSort().  It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]); // swap the pivot
    return i;
}

// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
    int n = r-l+1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}

// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

La pire complexité temporelle de la solution ci-dessus est toujours O (n2). Dans le pire des cas, la fonction aléatoire peut toujours choisir un élément de coin. La complexité temporelle attendue de QuickSelect randomisé ci-dessus est Θ (n)

1. Avoir une file d'attente prioritaire créée.
2. Insérez tous les éléments dans le tas.

3. Appelez poll () k fois.

   public static int getKthLargestElements(int[] arr)
   {
       PriorityQueue<Integer> pq =  new PriorityQueue<>((x , y) -> (y-x));
       //insert all the elements into heap
       for(int ele : arr)
          pq.offer(ele);
       // call poll() k times
       int i=0;
       while(i&lt;k)
        {
          int result = pq.poll();
        } 
      return result;        
   }
   

Ceci est une implémentation en Javascript.

Si vous libérez la contrainte que vous ne pouvez pas modifier le tableau, vous pouvez empêcher l'utilisation de mémoire supplémentaire en utilisant deux index pour identifier la "partition actuelle" (dans le style de tri rapide classique - http://www.nczonline.net/blog/2012/ 11/27 / computer-science-in-javascript-quicksort / ).

function kthMax(a, k){
    var size = a.length;

    var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2) 

    //Create an array with all element lower than the pivot and an array with all element higher than the pivot
    var i, lowerArray = [], upperArray = [];
    for (i = 0; i  < size; i++){
        var current = a[i];

        if (current < pivot) {
            lowerArray.push(current);
        } else if (current > pivot) {
            upperArray.push(current);
        }
    }

    //Which one should I continue with?
    if(k <= upperArray.length) {
        //Upper
        return kthMax(upperArray, k);
    } else {
        var newK = k - (size - lowerArray.length);

        if (newK > 0) {
            ///Lower
            return kthMax(lowerArray, newK);
        } else {
            //None ... it's the current pivot!
            return pivot;
        }   
    }
}  

Si vous souhaitez tester ses performances, vous pouvez utiliser cette variante:

    function kthMax (a, k, logging) {
         var comparisonCount = 0; //Number of comparison that the algorithm uses
         var memoryCount = 0;     //Number of integers in memory that the algorithm uses
         var _log = logging;

         if(k < 0 || k >= a.length) {
            if (_log) console.log ("k is out of range"); 
            return false;
         }      

         function _kthmax(a, k){
             var size = a.length;
             var pivot = a[parseInt(Math.random()*size)];
             if(_log) console.log("Inputs:", a,  "size="+size, "k="+k, "pivot="+pivot);

             // This should never happen. Just a nice check in this exercise
             // if you are playing with the code to avoid never ending recursion            
             if(typeof pivot === "undefined") {
                 if (_log) console.log ("Ops..."); 
                 return false;
             }

             var i, lowerArray = [], upperArray = [];
             for (i = 0; i  < size; i++){
                 var current = a[i];
                 if (current < pivot) {
                     comparisonCount += 1;
                     memoryCount++;
                     lowerArray.push(current);
                 } else if (current > pivot) {
                     comparisonCount += 2;
                     memoryCount++;
                     upperArray.push(current);
                 }
             }
             if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);

             if(k <= upperArray.length) {
                 comparisonCount += 1;
                 return _kthmax(upperArray, k);
             } else if (k > size - lowerArray.length) {
                 comparisonCount += 2;
                 return _kthmax(lowerArray, k - (size - lowerArray.length));
             } else {
                 comparisonCount += 2;
                 return pivot;
             }
     /* 
      * BTW, this is the logic for kthMin if we want to implement that... ;-)
      * 

             if(k <= lowerArray.length) {
                 return kthMin(lowerArray, k);
             } else if (k > size - upperArray.length) {
                 return kthMin(upperArray, k - (size - upperArray.length));
             } else 
                 return pivot;
     */            
         }

         var result = _kthmax(a, k);
         return {result: result, iterations: comparisonCount, memory: memoryCount};
     }

Le reste du code consiste simplement à créer une aire de jeux:

    function getRandomArray (n){
        var ar = [];
        for (var i = 0, l = n; i < l; i++) {
            ar.push(Math.round(Math.random() * l))
        }

        return ar;
    }

    //Create a random array of 50 numbers
    var ar = getRandomArray (50);   

Maintenant, exécutez vos tests quelques fois. En raison de Math.random (), il produira à chaque fois des résultats différents:

    kthMax(ar, 2, true);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 34, true);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);

Si vous le testez plusieurs fois, vous pouvez voir même empiriquement que le nombre d'itérations est, en moyenne, O (n) ~ = constant * n et la valeur de k n'affecte pas l'algorithme.

Je suis venu avec cet algorithme et semble être O (n):

Disons que k = 3 et nous voulons trouver le 3ème plus grand élément du tableau. Je créerais trois variables et comparerais chaque élément du tableau avec le minimum de ces trois variables. Si l'élément de tableau est supérieur à notre minimum, nous remplacerions la variable min par la valeur de l'élément. Nous continuons la même chose jusqu'à la fin du tableau. Le minimum de nos trois variables est le troisième plus grand élément du tableau.

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

Et, pour trouver le Kème élément le plus grand, nous avons besoin de K variables.

Exemple: (k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

Quelqu'un peut-il revoir ceci et me faire savoir ce qui me manque?

Voici l'implémentation de l'algorithme eladv proposée (j'ai également mis ici l'implémentation avec pivot aléatoire):

public class Median {

    public static void main(String[] s) {

        int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
        System.out.println(selectK(test,8));

        /*
        int n = 100000000;
        int[] test = new int[n];
        for(int i=0; i<test.length; i++)
            test[i] = (int)(Math.random()*test.length);

        long start = System.currentTimeMillis();
        random_selectK(test, test.length/2);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        */
    }

    public static int random_selectK(int[] a, int k) {
        if(a.length <= 1)
            return a[0];

        int r = (int)(Math.random() * a.length);
        int p = a[r];

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return random_selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return random_selectK(temp,k-small-equal);
        }
    }

    public static int selectK(int[] a, int k) {
        if(a.length <= 5) {
            Arrays.sort(a);
            return a[k-1];
        }

        int p = median_of_medians(a);

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return selectK(temp,k-small-equal);
        }
    }

    private static int median_of_medians(int[] a) {
        int[] b = new int[a.length/5];
        int[] temp = new int[5];
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<5; j++)
                temp[j] = a[5*i + j];
            Arrays.sort(temp);
            b[i] = temp[2];
        }

        return selectK(b, b.length/2 + 1);
    }
}

elle est similaire à la stratégie quickSort, où nous choisissons un pivot arbitraire, et amenons les petits éléments à sa gauche et les plus grands à droite

    public static int kthElInUnsortedList(List<int> list, int k)
    {
        if (list.Count == 1)
            return list[0];

        List<int> left = new List<int>();
        List<int> right = new List<int>();

        int pivotIndex = list.Count / 2;
        int pivot = list[pivotIndex]; //arbitrary

        for (int i = 0; i < list.Count && i != pivotIndex; i++)
        {
            int currentEl = list[i];
            if (currentEl < pivot)
                left.Add(currentEl);
            else
                right.Add(currentEl);
        }

        if (k == left.Count + 1)
            return pivot;

        if (left.Count < k)
            return kthElInUnsortedList(right, k - left.Count - 1);
        else
            return kthElInUnsortedList(left, k);
    }

Allez à la fin de ce lien: ...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/

Vous pouvez trouver le kème plus petit élément dans le temps O (n) et l'espace constant. Si nous considérons que le tableau est uniquement pour les entiers.

L'approche consiste à effectuer une recherche binaire sur la plage de valeurs de tableau. Si nous avons un min_value et un max_value à la fois dans la plage entière, nous pouvons faire une recherche binaire sur cette plage. Nous pouvons écrire une fonction de comparaison qui nous dira si une valeur est la kth-plus petite ou plus petite que kth-plus petite ou plus grande que kth-plus petite. Effectuez la recherche binaire jusqu'à ce que vous atteigniez le kième plus petit nombre

Voici le code pour ça

Solution de classe:

def _iskthsmallest(self, A, val, k):
    less_count, equal_count = 0, 0
    for i in range(len(A)):
        if A[i] == val: equal_count += 1
        if A[i] < val: less_count += 1

    if less_count >= k: return 1
    if less_count + equal_count < k: return -1
    return 0

def kthsmallest_binary(self, A, min_val, max_val, k):
    if min_val == max_val:
        return min_val
    mid = (min_val + max_val)/2
    iskthsmallest = self._iskthsmallest(A, mid, k)
    if iskthsmallest == 0: return mid
    if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
    return self.kthsmallest_binary(A, mid+1, max_val, k)

# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
    if not A: return 0
    if k > len(A): return 0
    min_val, max_val = min(A), max(A)
    return self.kthsmallest_binary(A, min_val, max_val, k)

Il existe également un algorithme qui surpasse l'algorithme de sélection rapide. Il s'agit de l' algorithme Floyd-Rivets (FR) .

Article d'origine: https://doi.org/10.1145/360680.360694

Version téléchargeable: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

Article de Wikipédia https://en.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

J'ai essayé d'implémenter quickselect et l'algorithme FR en C ++. Je les ai également comparés aux implémentations standard de la bibliothèque C ++ std :: nth_element (qui est essentiellement un hybride introsélection de quickselect et heapselect). Le résultat a été quickselect et nth_element a fonctionné de manière comparable en moyenne, mais l'algorithme FR a fonctionné environ. deux fois plus vite par rapport à eux.

Exemple de code que j'ai utilisé pour l'algorithme FR:

template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
    if (n == 0)
        return *(std::min_element(data.begin(), data.end()));
    else if (n == data.size() - 1)
        return *(std::max_element(data.begin(), data.end()));
    else
        return _FRselect(data, 0, data.size() - 1, n);
}

template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
    size_t leftIdx = left;
    size_t rightIdx = right;

    while (rightIdx > leftIdx)
    {
        if (rightIdx - leftIdx > 600)
        {
            size_t range = rightIdx - leftIdx + 1;
            long long i = n - (long long)leftIdx + 1;
            long long z = log(range);
            long long s = 0.5 * exp(2 * z / 3);
            long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);

            size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
            size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);

            _FRselect(data, newLeft, newRight, n);
        }
        T t = data[n];
        size_t i = leftIdx;
        size_t j = rightIdx;
        // arrange pivot and right index
        std::swap(data[leftIdx], data[n]);
        if (data[rightIdx] > t)
            std::swap(data[rightIdx], data[leftIdx]);

        while (i < j)
        {
            std::swap(data[i], data[j]);
            ++i; --j;
            while (data[i] < t) ++i;
            while (data[j] > t) --j;
        }

        if (data[leftIdx] == t)
            std::swap(data[leftIdx], data[j]);
        else
        {
            ++j;
            std::swap(data[j], data[rightIdx]);
        }
        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= n)
            leftIdx = j + 1;
        if (n <= j)
            rightIdx = j - 1;
    }

    return data[leftIdx];
}

template <typename T>
int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}

Ce que je ferais c'est ceci:

initialize empty doubly linked list l
for each element e in array
    if e larger than head(l)
        make e the new head of l
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

Vous pouvez simplement stocker des pointeurs vers le premier et le dernier élément de la liste chaînée. Ils ne changent que lorsque des mises à jour de la liste sont effectuées.

Mettre à jour:

initialize empty sorted tree l
for each element e in array
    if e between head(l) and tail(l)
        insert e into l // O(log k)
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

D'abord, nous pouvons construire un BST à partir d'un tableau non trié qui prend du temps O (n) et à partir du BST, nous pouvons trouver le kème plus petit élément dans O (log (n)) qui, au total, compte jusqu'à un ordre de O (n).