#include "pch.h"
#include <iostream>
using namespace std;
void swap(int& a, int& b) {
    int pomoc = b;
    b = a;
    a = pomoc;
}
void sort(int tab[], int l, int r) {
    for (int i = 1; i <= r; i++) {
        int key = tab[i];
        int j = i - 1;
        while (j >= l && tab[j] > key) {
            tab[j + 1] = tab[j];
            j--;
            tab[j + 1] = key;
        }
    }
}
int partition(int tab[], int k, int l, int r) {
    int i = 0;
    while (tab[i] != k)i++;
    swap(tab[i], tab[r]);
    i = l - 1;
    for (int j = l; j <= r - 1; j++) {
        if (tab[j] <= k) {
            i++;
            swap(tab[i], tab[j]);
        }
    }

    swap(tab[i + 1], tab[r]);
    return i + 1;

}
int find_median(int tab[], int start, int end) {
    sort(tab, start, end);
    return tab[(end + start) / 2];
}
int ksmallest(int tab[], int l, int r, int k) {
    if (k > 0 && k <= r - l + 1) {
        int n = r - l + 1;
        int *medians = new int[(n + 4) / 5];
        int start = l;
        int end = l + 4;
        int i = 0;
        while (end <= r) {
            medians[i] = find_median(tab, start, end);
            i++;
            start = end + 1;
            end = start + 4;
        }
        if (5 * i < n) {
            medians[i] = find_median(tab, start, r);
            i++;
        }
        int medOfMed = (i == 1) ? medians[i - 1] : ksmallest(medians, 0, i - 1, i / 2);
        int pos = partition(tab, medOfMed, l, r);
        if (pos - l == k - 1)return tab[pos];
        if (pos - l > k - 1) return ksmallest(tab, l, pos - 1, k);
        if (pos - l < k - 1) return ksmallest(tab, pos + 1, r, k - pos + l - 1);

    }
}
void sortFrom(int tab[], int from, int to) {
    for(int i = from; i <= to; i++){
        ksmallest(tab, from, to, i);
}
}
int main()
{
    int tab[10] = { 4,15,2,3,17,65,8,9,13,6 };
    //cout << ksmallest(tab, 0, 9, 5)<<endl;
    sortFrom(tab, 3, 7);
        for (int i = 0; i < 10; i++) {
        cout << tab[i]<<" ";
}
}