// Take a last element of array as Pivot element.
//Place at the right position in array and divide smaller element to left and greater 
//to right side of the pivot.
//Based on recursive calling.


function quickSort(array:number[]):number[]{
    if(array.length<1)
        return array;
    
    var pivot = array[array.length-1];
    
    const left: number[] = [];
    const right: number[] = [];
    
    for(let i=0;i<array.length-1; i++){
        if(array[i]<pivot){
            left.push(array[i]);
        }else{
            right.push(array[i]);
        }
    }
   // Recursively apply the quickSort function to the left and right arrays,
  // then combine the sorted arrays with the pivot in the middle
    return [...quickSort(left),pivot,...quickSort(right)];
}
            
            
// Example usage:
const unsortedArray = [6, 2, 9, 5, 1, 7, 4, 8, 3];
const sortedArray = quickSort(unsortedArray);
console.log(sortedArray);