Анализ быстрой сортировки в C

Question

То, что я пытаюсь сделать, это получить желаемый результат ниже. Я пробовал печатать в начале быстрой сортировки и получаю некоторые правильные значения, но я чувствую, что весь мой подход не работает, поэтому мне нужна помощь.

уровень разделаNumber d [3a_spaces x1 x3 ... xn 3b_spaces]

Где

уровень - уровень рекурсии.

partitionNumber - номер, используемый для создания раздела.

d равен '>', если параметр partitionNumber больше, чем элементы в противном случае раздел '<'. </p>

3a_space - это набор из 3 пробелов для каждого элемента массив перед началом раздела.

x1 x3 ... xn - набор чисел в разделе. Примечание: печать эти числа с использованием дескриптора формата "% 3d".

3b_spaces - это набор из 3 пробелов для каждого элемента массив после конца раздела.

желаемый вывод:

1  0  [23 13 82 33 51 17 45 75 11 27 ]
2 51> [27 13 33 23 17 45 11          ]
3 23> [11 13 17                      ]
3 23> [11 13 17                      ]
3 23< [            33 45 27          ]
4 45> [            27 33             ]
4 45> [            27 33             ]
3 23< [            27 33 45          ]
2 51> [11 13 17 23 27 33 45          ]
2 51< [                        82 75 ]
2 51< [                        75 82 ]
1  0  [11 13 17 23 27 33 45 51 75 82 ]

мой вывод:

1  0  [23 13 82 33 51 17 45 75 11 27 ]
2 51> [27 13 33 23 17 45 11          ]
3 23> [11 13 17                      ]
2 13> [11 13 17                      ]
3 23< [            33 45 27          ]
4 45> [            27 33             ]
3 27? [            27 33             ]
2 45> [            27 33 45          ]
1 23> [11 13 17 23 27 33 45          ]
2 51< [                        82 75 ]
1 82> [                        75 82 ]
0 51> [11 13 17 23 27 33 45 51 75 82 ]






 #include<stdio.h>

int inputLine[10];

void quicksort(int v[], int left, int right, int level, int previousPivotPoint, char d);

int main()
{
  int v[] = { 23, 13, 82, 33, 51, 17, 45, 75, 11, 27 };
  quicksort(v, 0, 9, 0, -1, ' ');



  return 0;
}

void swap(int v[], int i, int j)
{
  int temp;
  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
}

void quicksort(int v[], int left, int right, int level, int previousPivotPoint, char d)
{
  int i, last;

  level++;
  if (previousPivotPoint > v[left]) d = '>';
  else if (previousPivotPoint < v[left]) d = '<';


  if (left >= right)
  {
    level--;
    return;
  }
  if (previousPivotPoint == -1)
  {
    printf("%d  0  [", level);
  } else
  {
    printf("%d %d%c [", level, previousPivotPoint, d);
  }

  previousPivotPoint = v[(left + right) / 2];

  d = '?';
  for (i = 0; i < 10; i++)
  {
    if (i > right || i < left)
    {
      printf("   ");
    } else
    {
      printf("%d ", v[i]);
    }
  }
  printf("]\n");

  swap(v, left, (left + right) / 2);

  last = left;

  for (i = left + 1; i <= right; i++)
  {
    if (v[i] < v[left])
    {
      last++;
      swap(v, last, i);
    }
  }

  swap(v, left, last);
  quicksort(v, left, last - 1, level, previousPivotPoint, d);
  quicksort(v, last + 1, right, level, previousPivotPoint, d);
  level--;


  if (previousPivotPoint > v[left]) d = '>';
  else if (previousPivotPoint < v[left]) d = '<';
  printf("%d %d%c [", level, previousPivotPoint, d);
  previousPivotPoint = v[(left + right) / 2];


  for (i = 0; i < 10; i++)
  {
    if (i > right || i < left)
    {
      printf("   ");
    } else
    {
      printf("%d ", v[i]);
    }
  }
  printf("]\n");

}

Answer 1

Я заметил пару вещей:

1. Если уровень будет модульной переменной, а не передаваемой в процедуру быстрой сортировки, он вряд ли когда-нибудь снизится. Попробуйте включить его в подпись вашей функции быстрой сортировки.
2. Вы начинаете с i = left - это не напечатает весь ваш исходный массив. Всегда обращайтесь к массиву и печатайте их все, проверяя, находитесь ли вы в текущем массиве или нет.
3. Вы делаете декларацию FORWARD void swap(int v[], int i, int j); внутри своей процедуры быстрой сортировки. Что с этим? Примечание: очевидно, это от K & R. Из личного вкуса я не самый большой поклонник нотации, но вы могли бы сделать хуже, чем следовать K & R, а?

Answer 2

Не было времени углубиться в ваш код, но вот несколько вещи.

Первое, что вы должны сделать, это заменить это жестко закодированное 10 на #define константа.

Не удивительно, что вы не установили значение d, отсюда и все пробелы. Кроме того, зачем делать d глобальным?

Ваш цикл печати должен пройти весь список, чтобы часть в скобки всегда будут одинакового размера.