Quick Sort Analysis in C

Question

What I'm trying to do is get the desired result below. I tried printing at the beginning of quicksort and I am getting some of the correct values, but I feel that my whole approach is not working, so I need help.

level partitionNumber d [3a_spaces x1 x3 ... xn 3b_spaces]

Where:

Level

is the level of recursion.

section number is the number used to create the section.

d is '>' if the section number is greater than the elements; otherwise it is '<'.

3a_space is a set of three space characters for each element of the array before the start of the section.

x1 x3 ... xn is the set of numbers in a section. Note: printing these numbers use a descriptor of the format "% 3d".

3b_spaces is a set of three space characters for each array element after the end of a section.

desired result:

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 ]

my conclusion:

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

A few things I notice:

• If the level is a modular variable and not passed to the quick sort procedure, it is unlikely to ever decline. Consider including it in the signature of your quick sort function.
• You start with i = left- this will not print the entire source base array. Think about whether to always go through the array and print them all out, checking if you are in the current array or not.
• FORWARD void swap(int v[], int i, int j); . ? :, -, K & R. , , , K & R, eh?

Answer 2

, .

, , hardcoded 10 #define .

, d, , . , d ?

, .