using System;
class GFG {
static int partition(int []arr, int low,
int high)
{
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++)
{
if (arr[j] < pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp1 = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp1;
return i+1;
}
static void quickSort(int []arr, int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi-1);
quickSort(arr, pi+1, high);
}
}
static void printArray(int []arr, int n)
{
for (int i = 0; i < n; ++i)
Console.Write(arr[i] + " ");
Console.WriteLine();
}
public static void Main()
{
int []arr = {10, 7, 8, 9, 1, 5};
int n = arr.Length;
quickSort(arr, 0, n-1);
Console.WriteLine("sorted array ");
printArray(arr, n);
}
}
IAp1c2luZyBTeXN0ZW07IAoKY2xhc3MgR0ZHIHsgCgkKCXN0YXRpYyBpbnQgcGFydGl0aW9uKGludCBbXWFyciwgaW50IGxvdywgCgkJCQkJCQkJaW50IGhpZ2gpIAoJeyAKCQlpbnQgcGl2b3QgPSBhcnJbaGlnaF07IAoJCQoKCQlpbnQgaSA9IChsb3cgLSAxKTsgCgkJZm9yIChpbnQgaiA9IGxvdzsgaiA8IGhpZ2g7IGorKykgCgkJeyAKCQkJaWYgKGFycltqXSA8IHBpdm90KSAKCQkJeyAKCQkJCWkrKzsgCgoKCQkJCWludCB0ZW1wID0gYXJyW2ldOyAKCQkJCWFycltpXSA9IGFycltqXTsgCgkJCQlhcnJbal0gPSB0ZW1wOyAKCQkJfSAKCQl9IAoKCgkJaW50IHRlbXAxID0gYXJyW2krMV07IAoJCWFycltpKzFdID0gYXJyW2hpZ2hdOyAKCQlhcnJbaGlnaF0gPSB0ZW1wMTsgCgoJCXJldHVybiBpKzE7IAoJfSAKCgoJc3RhdGljIHZvaWQgcXVpY2tTb3J0KGludCBbXWFyciwgaW50IGxvdywgaW50IGhpZ2gpIAoJeyAKCQlpZiAobG93IDwgaGlnaCkgCgkJeyAKCQkJCgkJCWludCBwaSA9IHBhcnRpdGlvbihhcnIsIGxvdywgaGlnaCk7IAoKCgkJCXF1aWNrU29ydChhcnIsIGxvdywgcGktMSk7IAoJCQlxdWlja1NvcnQoYXJyLCBwaSsxLCBoaWdoKTsgCgkJfSAKCX0gCgoKCXN0YXRpYyB2b2lkIHByaW50QXJyYXkoaW50IFtdYXJyLCBpbnQgbikgCgl7IAoJCWZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSAKCQkJQ29uc29sZS5Xcml0ZShhcnJbaV0gKyAiICIpOyAKCQkJCgkJQ29uc29sZS5Xcml0ZUxpbmUoKTsgCgl9IAoKCglwdWJsaWMgc3RhdGljIHZvaWQgTWFpbigpIAoJeyAKCQlpbnQgW11hcnIgPSB7MTAsIDcsIDgsIDksIDEsIDV9OyAKCQlpbnQgbiA9IGFyci5MZW5ndGg7IAoJCXF1aWNrU29ydChhcnIsIDAsIG4tMSk7IAoJCUNvbnNvbGUuV3JpdGVMaW5lKCJzb3J0ZWQgYXJyYXkgIik7IAoJCXByaW50QXJyYXkoYXJyLCBuKTsgCgl9IAp9IAoKCg==