#include <stdio.h>
#include <time.h>

#define MAX_LEN 70

int count;

void swap(int arr[], int n, int p) {
 int temp;
 temp = arr[n];
 arr[n] = arr[p];
 arr[p] = temp;
}

void print_arr(int arr[], int len)
{
 int i;
 for (i = 0; i < len; i++)
 {
  printf("%d ", arr[i]);
 }

 printf("\n");
}

int partiton(int arr[], int start, int len) {

 int i;
 int p = start;

 for (i = start; i < len; i++) {
  count++;
  if (arr[start] > arr[i])
  {
   swap(arr, ++p, i);
  }
 }

 swap(arr, start, p);

 return p;
}


void quicksort(int arr[], int left, int right) {
 int i, p = left, j;

 for (i = 1; i < right; i++) {
  p = partiton(arr, left, right); //遺遺꾩쓣 ?섎닎

  while (p > left) { //left留뚰겮 ?뺣젹????
   p = partiton(arr, left, p); //?섎늿 遺遺?理쒖냼媛?李얠쓬
  }

  left = i;
 }
}

int main(void) {

 int arr[MAX_LEN]; //100000 ?깃났
 int i;

 srand(time(NULL));

 for (i = 0; i < MAX_LEN; i++)
  arr[i] = rand() % MAX_LEN;

 print_arr(arr, MAX_LEN);

 printf("정렬된 함수 \n");
 quicksort(arr, 0, MAX_LEN);
 print_arr(arr, MAX_LEN);

 printf("count : %d", count);
}
//우리 조교가 틀렸다고 매겼네 내가 할때는 다 맞았는데