10 maja 2011

Algorytm selekcji Hoare'a (QuickSelect) w C# .NET

Algorytm selekcji k-tego elementu


W poprzednim poście opisałem obliczanie mediany za pomocą prostego algortymu używającego sortowania. W celu uzyskania krótszych czasów wykonania, natknąłem się na algortym selekcji Hoare'a zwany QuickSelectem. Ponieważ obliczenie mediany dla uszeregowanego zbioru n-elementowego (dla uproszczenia n jest nieparzyste), wymaga wyznaczenia k-tego element gdzie k = (n+1)/2, QuickSelect okazał się bardzo pomocny.

Poniżej podaję implementację rekurencyjną QuickSelect'a w C# , w następnym poście podam pełną wersję algorytmu obliczającego medianę.


QuickSelect jest ideowo podobny do QuickSort'a (Hoare jest jego autorem). Lista elementów jest dzielona na partycje, w QuickSort każda partycja jest w końcu posortowana. W QuickSelect tylko partycja, która zawiera poszukiwany k-ty element jest rozważana do dalszych poszukiwań.

public class HoareAlgorithm
    {
         public SqlDouble GetKthElement(List<SqlDouble> list, int k)
         {
            return Select(list, 0, list.Count - 1, k);
         }

         private SqlDouble Select(List<SqlDouble> list, 
             int leftBoundIndex, 
             int rightBoundIndex, 
             int kthElementIndex)
         {
            SqlDouble locatedElementValue = -1;
            int randomPivotIndex = PickRandomPivotIndex(leftBoundIndex, rightBoundIndex);
            int newPivotIndex = PartitionListByPivotValue(list, 
                leftBoundIndex, 
                rightBoundIndex, 
                randomPivotIndex);
            if( newPivotIndex == kthElementIndex)
            {
                locatedElementValue = list[newPivotIndex];
            }
            else if(kthElementIndex < newPivotIndex)
            {
                //search for kth-element in left part of the partition
                locatedElementValue = Select(list, 
                    leftBoundIndex, 
                    newPivotIndex - 1, 
                    kthElementIndex);
            }
            else if(kthElementIndex > newPivotIndex)
            {
                //search for kth-element in right part of the partition
                locatedElementValue = Select(list, 
                    newPivotIndex + 1, 
                    rightBoundIndex, 
                    kthElementIndex);
            }
            return locatedElementValue;
         }

        private int PickRandomPivotIndex(int minumum, int maximum)
        {
            return new Random().Next(minumum, maximum);
        }

        private int PartitionListByPivotValue(List<SqlDouble> list, 
            int leftBoundIndex, int rightBoundIndex, int pivotValueIndex)
         {
            if (leftBoundIndex == rightBoundIndex)
            {
                return leftBoundIndex;
            }

            SqlDouble pivotValue = list[pivotValueIndex];
            SwapValues(list, pivotValueIndex, rightBoundIndex);
            int currentIndex = leftBoundIndex;
            for (int i = leftBoundIndex; i < rightBoundIndex; i++)
            {
                if(list[i] < pivotValue)
                {
                    SwapValues(list, i, currentIndex);
                    currentIndex++;
                }
            }
            SwapValues(list, currentIndex, rightBoundIndex);
            return currentIndex;
         }

         private void SwapValues(List<SqlDouble> list, 
             int value1Index, 
             int value2Index)
         {
             SqlDouble temp = list[value1Index];
             list[value1Index] = list[value2Index];
             list[value2Index] = temp;
         }
    }


Przykłady użycia


Wyznacz 4-ty element

List<SqlDouble> from1to7 = new List<SqlDouble> {7, 5, 2, 1, 3, 4, 6};
var algorithm = new HoareAlgorithm();
SqlDouble result = algorithm .GetKthElement(from1to7, 4 - 1);
//result should be equal to 4.0

Lub Wyznacz 10-ty element

List<SqlDouble> from10to120 = new List<SqlDouble> { 
120, 10, 110, 20, 100, 30, 
90, 40, 80, 50, 70, 60 
};
var algorithm = new HoareAlgorithm();
SqlDouble result = algorithm.GetKthElement(from10to120, 10 - 1);
//result should be equal to 100.0

Brak komentarzy:

Prześlij komentarz

Uwaga: tylko uczestnik tego bloga może przesyłać komentarze.