Ошибка алгоритма. Определите, был ли массив уже разбит на разделы (т.е. Один шаг быстрой сортировки)

Последний вопрос о финале моих алгоритмов сводил меня с ума в течение последнего месяца. Вот вопрос:

У вас есть массив A[0...n], напишите алгоритм (в "правильном" псевдокоде), который работает в O (n), который может определить, был ли этот массив уже разбит по отношению к некоторому индексу k, и если да, найдите k; if not then return -1;

Чтобы уточнить, Partition:

Для каждого элемента e в A[0...n], если e < A[k] поместите e в "левый" A[k], добавьте e в "правую" сторону A[k].

Итак, пример многораздельного массива (w.r.t. k = 11):

A = [4 2 5 3 7 4 2 6 8 4 1 10 10 10 20 11 15 13 28 99 11]

затем

myAlgo(A) -> (11)

или

A = [10, 20, 30, 40, 11, 100 , 150, 101, 125]

затем

myAlgo(A) -> (5)

но не:

A = [10, 20, 30, 40, 5]

myAlgo(A) -> (-1)

Моя первая мысль (которая была невероятно наивной) была настолько ужасной, что я буквально не могу выразить это словами. В основном, он непреднамеренно проверял, отсортирован ли массив и вытащил довольно случайное значение из середины.

Моя следующая мысль состояла в том, чтобы отсканировать список и сначала проверить, чтобы найти наибольшее число, которое я ударил, прежде чем нанести удар по уменьшающемуся числу и вывести все эти цифры... в основном удерживая макс и мин, а если вещи выпадают вне и то, и другое меняет мой возможный индекс раздела на конец моего подмножества.

Вот где я пытался (очень, очень плохо) реализовать это (с тестовым примером):

int myAlgo(const int* A, int n);

int main() {

    const int A[] = {10, 20, 30, 40, 11, 100, 150, 101, 125};

    int index;
    if((index = myAlgo(A, 9)) != -1) {
        printf("A[%d] = %d", index, A[index]);
    }
    else {
        printf("Not Partitioned >:/");
    }

    return 0;
}

int myAlgo(const int* A, int n) {
    // the index of the smallest possible number in the remainder of the list
    int minIdx = 0;

    // the index of the largest number we've encountered
    int maxIdx = 0;

    // index of possible partition "center"
    int kIdx = 0;

    bool isPart = false;

    for(int i=0; i < n; ++i) {
        if( A[maxIdx] <= A[i] )  {
            maxIdx = i;
            if(isPart == false)  { kIdx = i; minIdx = i;} // if we flipped then this is a good time to grab a partitioner index
            isPart = true;
        }
        else { isPart = false; minIdx = i; }
        printf("A[%d] = %d <==> A[%d]: %d : %c\n", maxIdx, A[maxIdx], i, A[i], (isPart?'T':'F'));
        if( A[minIdx] > A[i] ) { isPart = false; }
        printf("A[%d] = %d <==> A[%d]: %d : %c\n", minIdx, A[minIdx], i, A[i], (isPart?'T':'F'));
    }

    printf("A[%d] = %d : %c\n\n", kIdx, A[kIdx], (isPart?'T':'F'));

    // We gotta check this to make sure it is a valid list...
    if(isPart) return kIdx;
    else return -1;
}

Но, что неудивительно, мой результат: <Предварительно > <Код > A [0] = 10 < == > A [0]: 10: T A [0] = 10 < == > A [0]: 10: T A [1] = 20 < == > A [1]: 20: T A [0] = 10 < == > A [1]: 20: T A [2] = 30 < == > A [2]: 30: T A [0] = 10 < == > A [2]: 30: T A [3] = 40 < == > A [3]: 40: T A [0] = 10 < == > A [3]: 40: T A [3] = 40 < == > A [4]: ​​11: F A [4] = 11 < == > A [4]: ​​11: F A [5] = 100 < == > A [5]: 100: T A [5] = 100 < == > A [5]: 100: T A [6] = 150 < == > A [6]: 150: T A [5] = 100 < == > A [6]: 150: T A [6] = 150 < == > A [7]: 101: F A [7] = 101 < == > A [7]: 101: F A [6] = 150 < == > A [8]: 125: F A [8] = 125 < == > A [8]: 125: F A [5] = 100: F < - индекс прав... но isPart неверен

Не разбит на разделы > :/

Мне бы очень хотелось спать сегодня вечером, поэтому любые советы/подсказки/идеи/и т.д. были бы очень, очень оценены.

Woo! @Amit помог мне решить мою проблему, вот моя обновленная функция:

int partIdx2(const int* A, int n) {

    int* max = malloc(n * sizeof(int));
    int* min = malloc(n * sizeof(int));

    for(int i=0; i < n; i++)
    {
        if(i==0) {
            max[i] = A[i];
            min[n - 1] = A[n-1];
        }
        else {
            max[i] = MAX(max[i-1], A[i]);
            min[n - 1 - i] = MIN(min[n - 1 - i + 1], A[n - 1 - i]);
        }
    }

    for(int i=1; i < n-1; i++) {
        if(A[i] >= max[i-1] && A[i] <= min[i+1]) { 
            free(max);
            free(min);
            return i; 
        }
    }

    free(max);
    free(min);

    return -1;
}

Ответы

max[i] = max{arr[0],arr[1],...,arr[i]}
min[i] = min{arr[i],arr[i+1],...,arr[n-1]}

arr[k] >= max[k-1] && arr[k] <= min[k+1]

Set highest value found on low side to value of first element
Set lowest value found on high side to value of last element
Set low index to first element
Set high index to last element
repeat
  increment low index
  if low index >= array length -> fail
  if value at new low index > highest so far on the low side
    set new highest-on-low-side value
      if new value greater than lowest value so far on right side,
        set low index back to what it was and mark it as stuck
        set highest-on-low-side value back to what it was
  decrement high index
  if high index < 0 -> fail
  if value at new high index < lowest so far on the high side
    set new lowest-on-high-side value
      if new value less than the highest value so far on the left side,
        set high index back to what it was and mark it as stuck
        set lowest-on-high-side value back to what it was
until both low and high index is stuck or until low index >= high index
if low index = high index
  pivot position = low index
else
  failure

function PivotIndex(a: array of integer): Integer;
var
  HighestValueOnLeftSide: Integer;
  LowestValueOnRightSide: Integer;
  LowIndex: Integer;
  HighIndex: Integer;
  LowStuck, HighStuck: Boolean;
begin
  HighestValueOnLeftSide := -1;
  LowestValueOnRightSide := MaxInt;
  LowIndex := -1;
  HighIndex := length(a);
  LowStuck := False;
  HighStuck := False;
  repeat
    if not LowStuck then begin
      inc(LowIndex);
      if LowIndex >= length(A) then begin
        Result := -1;
        exit;
      end;
      if A[LowIndex] > HighestValueOnLeftSide then
        if A[LowIndex] > LowestValueOnRightSide then begin
          LowStuck := True;
          dec(LowIndex);
        end else
          HighestValueOnLeftSide := A[LowIndex];
    end;
    if not HighStuck then begin
      dec(HighIndex);
      if HighIndex < 0 then begin
        Result := -1;
        exit;
      end;
      if A[HighIndex] < LowestValueOnRightSide then
        if A[HighIndex] < HighestValueOnLeftSide then begin
          HighStuck := True;
          inc(HighIndex);
        end else
          LowestValueOnRightSide := A[HighIndex];
    end;
  until LowStuck and HighStuck or (LowIndex >= HighIndex);
  if LowIndex = HighIndex then
    Result := LowIndex
  else
    Result := -1;
end;