package main

import (
	"fmt"
)

// Função que implementa o algoritmo Quick Sort para ordenar um array
func quickSort(array []int, inicio, fim int) {
	if inicio < fim {
		indicePivo := particionar(array, inicio, fim)
		quickSort(array, inicio, indicePivo-1) // Ordena a parte esquerda
		quickSort(array, indicePivo+1, fim)   // Ordena a parte direita
	}
}

// Função para particionar o array em relação ao pivô
func particionar(array []int, inicio, fim int) int {
	pivo := array[fim] // Escolhe o último elemento como pivô
	indiceMenor := inicio

	// Reorganiza os elementos menores que o pivô à esquerda
	for j := inicio; j < fim; j++ {
		if array[j] <= pivo {
			array[indiceMenor], array[j] = array[j], array[indiceMenor]
			indiceMenor++
		}
	}

	// Coloca o pivô na posição correta
	array[indiceMenor], array[fim] = array[fim], array[indiceMenor]
	return indiceMenor
}

func main() {
	// Array fixo para simular a entrada do usuário
	numeros := []int{33, 15, 10, 7, 40, 22}

	// Ordenando o array usando Quick Sort
	quickSort(numeros, 0, len(numeros)-1)

	// Exibindo o array ordenado
	fmt.Println("Array ordenado com Quick Sort:")
	for _, num := range numeros {
		fmt.Printf("%d ", num)
	}
	fmt.Println()
}