9.1 Minimum and maximum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int MINIMUM(int A[], int n)
{
    int min = A[0];
    for (int i = 1; i < n; i++)
    {
        if (min > A[i])
        {
            min = A[i];
        }
    }
    return min;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int MAXIMUM(int A[], int n)
{
    int max = A[0];
    for (int i = 1; i < n; i++)
    {
        if (max < A[i])
        {
            max = A[i];
        }
    }
    return max;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int second_MINIMUM(int A[], int n)
{
    int min = A[0];
    int sub_min = A[0];
    for (int i = 1; i < n; i++)
    {
        if (min > A[i])
        {
            sub_min = min;
            min = A[i];
        }
    }
    return sub_min;
}

9.2 Selection in expected linear time

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int PARTITION(int A[], int p, int r)
{
    int x = A[r]; //pivot
    int i = p - 1;

    for (int j = p; j < r - 1; j++)
    {
        if (A[j] <= x)
        {
            i++;
            std::swap(A[i], A[j]);
        }
    }
    std::swap(A[i + 1], A[r]);
    return i + 1;
}

int RANDOMIZED_SELECT(int A[], int p, int r, int i)
{
    if (p == r)
        return A[p];
    int q = PARTITION(A, p, r);
    int k = q - p + 1;
    if (i-1 == k)
        return A[q];
    else if (i < k)
        return RANDOMIZED_SELECT(A, p, q - 1, i);
    else 
        return RANDOMIZED_SELECT(A, q + 1, r, i - k);
}

9.3 Selection in worst-case linear time

Median of medians https://en.wikipedia.org/wiki/Median_of_medians

  1. Divide the n elements of the input array into bn=5c groups of 5 elements each and at most one group made up of the remaining n mod 5 elements.

  2. Find the median of each of the dn=5e groups by first insertion-sorting the elements of each group (of which there are at most 5) and then picking the median from the sorted list of group elements.

  3. Use SELECT recursively to find the median x of the dn=5e medians found in step 2. (If there are an even number of medians, then by our convention, x is the lower median.)

  4. Partition the input array around the median-of-medians x using the modified version of PARTITION. Let k be one more than the number of elements on the low side of the partition, so that x is the kth smallest element and there are nk elements on the high side of the partition.

  5. If i D k, then return x. Otherwise, use SELECT recursively to find the i th smallest element on the low side if i < k, or the .i  k/th smallest element on the high side if i > k.

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
// C++ implementation of worst case linear time algorithm 
// to find k'th smallest element 
#include<iostream> 
#include<algorithm> 
#include<climits> 

using namespace std;

int partition(int arr[], int l, int r, int k);

// A simple function to find median of arr[].  This is called 
// only for an array of size 5 in this program. 
int findMedian(int arr[], int n)
{
    sort(arr, arr + n);  // Sort the array 
    return arr[n / 2];   // Return middle element 
}


// Returns k'th smallest element in arr[l..r] in worst case 
// linear time. 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)
    {
        int n = r - l + 1; // Number of elements in arr[l..r] 

        // Divide arr[] in groups of size 5, calculate median 
        // of every group and store it in median[] array. 
        int i;
        int *median =  new int[(n + 4) / 5]; // There will be floor((n+4)/5) groups; 
        for (i = 0; i < n / 5; i++)
            median[i] = findMedian(arr + l + i * 5, 5);
        if (i * 5 < n) //For last group with less than 5 elements 
        {
            median[i] = findMedian(arr + l + i * 5, n % 5);
            i++;
        }

        // Find median of all medians using recursive call. 
        // If median[] has only one element, then no need 
        // of recursive call 
        int medOfMed = (i == 1) ? median[i - 1] :
            kthSmallest(median, 0, i - 1, i / 2);

        // Partition the array around a random element and 
        // get position of pivot element in sorted array 
        int pos = partition(arr, l, r, medOfMed);
        delete[]median;
        // 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 
            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;
}

// It searches for x in arr[l..r], and partitions the array  
// around x. 
int partition(int arr[], int l, int r, int x)
{
    // Search for x in arr[l..r] and move it to end 
    int i;
    for (i = l; i < r; i++)
        if (arr[i] == x)
            break;
    swap(&arr[i], &arr[r]);

    // Standard partition algorithm 
    i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}

// 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 = 5;
    cout << "K'th smallest element is "
        << kthSmallest(arr, 0, n - 1, k);
    return 0;
}