#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

/*
v[i]とv[j]を交換する
*/
void swap(int v[], int i, int j) {
    int temp;
    temp = v[i];
    v[i] = v[j];
    v[j] = temp;
}
/*
v[left]...v[right]を昇順にソートする
*/
void qsort(int v[], int left, int right) {
    if (left >= right) {
        return;
    }
    swap(v, left, (left + right) / 2);
    int last = left;
    for (int i = left + 1; i <= right; i++) {
        if (v[i] < v[left]) {
            swap(v, ++last, i);
        }
    }
    swap(v, left, last);
    qsort(v, left, last - 1);
    qsort(v, left + 1, right);
}

/*
Ｑソートの検証
*/
int main()
{
    srand((unsigned int)time(NULL));
    int arr[100];
    cout << "ソート前" << endl;
    for (int i = 0; i < 100; i++) {
        arr[i] = rand() % 1000;
        cout << arr[i] << ",";
        if (i % 10 == 9) {
            cout << endl;
        }
    }
    cout << endl;
    qsort(arr,0, 99);
    cout << "ソート後" << endl;
    for (int i = 0; i < 100; i++) {
        cout << arr[i] << ",";
        if (i % 10 == 9) {
            cout << endl;
        }
    }
    cout << endl;
    return 0;
}

ソート前
115,698,151,448,33,900,416,328,189,823,
170,859,778,776,284,397,962,577,61,395,
391,484,288,562,488,177,480,616,624,542,
696,474,228,503,590,574,244,374,697,810,
723,876,929,292,570,913,734,347,778,105,
443,662,113,616,860,828,631,846,86,579,
0,950,262,293,93,612,812,336,503,982,
273,533,75,92,136,108,261,602,857,453,
294,886,11,146,391,221,579,411,147,947,
584,618,983,114,673,776,846,506,569,528,

ソート後
0,11,33,61,75,86,92,93,105,108,
113,114,115,136,146,147,151,170,177,189,
221,228,244,261,262,273,284,288,292,293,
294,328,336,347,374,391,391,395,397,411,
416,443,448,453,474,480,484,488,503,503,
506,528,533,542,562,569,570,574,577,579,
579,584,590,602,612,616,616,618,624,631,
662,673,696,697,698,723,734,776,776,778,
778,810,812,823,828,846,846,857,859,860,
876,886,900,913,929,947,950,962,982,983,