Implementando QuickSort con Python: main code

Lo mejor para poder entender el código es comentarlo linea a linea, como si depuraras, si a alguien se le hizo difícil entenderlo. Se los dejo comentado 😄

#necesitamos dividir nuestro data set
#necesitamos el punto pivotal
#recursivamente ordenar cada mitad de mi array

def partition(arr, low, high): #creamos la particion del array
    i = (low-1) # i va a tomar el valor del indice mas bajo low-1
    pivot = arr[high] #valor medio de los datos, que separa los datos altos y bajos | dividimos el data set

    for j in range(low,high): #recorrer todo el rango de indices de low a high
        if arr[j] <= pivot: #de un lado se ponen todos los valores menores al pivot 
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1] #de otro lado se ponen los valores mayores al pivot
    return (i+1)

def quickSort(arr, low, high): #creamos la funcion del quick sort
    if low < high: 
        pi = partition(arr, low, high)  #llamamos a la funcion partition
        quickSort(arr, low, pi-1)  #recursivamente usamos quicksort del low a la mitad(pi-1)
        quickSort(arr, pi+1, high) #recursivamente usamos quicksort en la otra mitad del (pi+1) al high

arr = [1991, 1990, 10, 5, 6, 0, 1, -10]
n = len (arr) #len nos da el tamaño del arreglo n=8
quickSort(arr, 0, n-1) #ejecutamos quickSort (arr, 0, 7)
print("Array Ordenado:") #imprimimos el arreglo
for i in range (n): 
    print("%d" %arr[i]),

Código en C

#include <stdio.h>

int partition(int arr[], int low, int high)
{
    int i = low - 1;
    int pivot = arr[high];
    int temp;

    for(int j = low; j < high; j++)
    {
        if(arr[j] <= pivot)
        {
            i = i + 1;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return (i + 1);
}

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);
    }
}

int main()
{
    int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};
    int n = sizeof(arr) / sizeof(int);
    quickSort(arr, 0, n - 1);

    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

really hard to get it. Did it at the end but, as and advice, You sohuld give bit more info about how ir works, befor jumping into the code that fast. Thanks any way, helped me to understand couple of things related with variables and arrays.

code in java:

import java.util.Arrays;
import java.util.Scanner;

public class QuickSort {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Please instert the size of your array: ");
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i=0; i < n; i++){
            System.out.println("Please insert the value No. " + i);
            arr[i]=in.nextInt();
        }
        quickSort(arr, 0, arr.length-1);
        System.out.println("El array ordenado es: "+ Arrays.toString(arr));
    }

    static int particionar(int[] arr, int low, int high ){

        int i = low -1;
        int pivot = arr[high];
        int tempVal;

        for(int j = low; j < high; j++){
            if(arr[j] <= pivot){
                i=i+1;
                //arr[i], arr[j] = arr[j], arr[i];
                int temp = arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
            }
        }

        tempVal = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = tempVal;

        return (i+1);
    }

    static void quickSort(int[] arr, int low, int high){
        if(low < high){
            int pi = particionar(arr, low, high);
            quickSort(arr, low, pi-1);
            quickSort(arr, pi+1, high);
        }

    }
}```

solución JS 😄

implemente una función que cambia de posición

function particion(arr,low,high){
    function changePosition(arr,n1,n2){ 
        //intercambian posiciones
        let temp = arr[n1];
        arr[n1] =  arr[n2];
        arr[n2] = temp;
    }

    let i=low-1;
    let pivot=arr[high];

    for(let j = low;j < high;j++){
        if(arr[j] <= pivot){
            i = i+1;
            changePosition(arr,j ,i);
        }
    }

    changePosition(arr,high,i + 1)
    return i+1
}

function quickSort(arr,low,high){
    if(low < high){
        var pi = particion(arr,low,high);
        quickSort(arr,low,pi-1);
        quickSort(arr,pi+1,high);
    }
}

let arr = [7,1,3,4,1];
let n = arr.length;
quickSort(arr,0,n-1);

console.table(arr); //Node.js

Aquí les comparto mi aporte con Java Script:

function partition(arr, low, high) {
    var i = (low - 1);
    var pivot = arr[high];
    var temp;
    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high]  = temp;
    return (i + 1);
}

function quickSort(arr, low, high) {
    if (low < high) {
        pi = partition(arr, low, high);
        quickSort(arr, low, pi -1);
        quickSort(arr, pi + 1, high);
    }
}

var arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10];
var n = arr.length;
quickSort(arr, 0, n - 1);
console.log("Array ordenado:");
arr.forEach(element => {
    console.log(element);
});

En JavaScript

const quickSort = array => {
     let left = [];
     let right = [];
     let pivot = array[0];
     //caso base 
     if (array.length < 1) {
       return [];
     }
     // Division 
     for (let i = 1; i < array.length; i++) {
       if (array[i] < pivot) {
         left.push(array[i]);
       }else {
         right.push(array[i]);
       }
     }
     return [].concat(quickSort(left), pivot, quickSort(right));
   }

    let vector = Array.from({length: 100}, () => Math.floor(Math.random() * 200));
    console.log(`El array generado es: ${vector}`);
    let vectorOrdenado = quickSort(vector);
    console.log(`El array ordenado queda: ${vectorOrdenado}`);```

https://www.youtube.com/watch?v=kFeXwkgnQ9U

me parecio mas claro todo con este video 😃

Por qué en la particion ponemos el pivote como el valor de high “pivot=arr[high]” en vez de poner el numero de en medio?

Implementacion de quickSort con C

#include<stdio.h> 

int print_array(int arr[], int n)
{
    int i;
    for(i=0; i < n; i++)
        printf("%d  ,", arr[i]);
    printf("\n Fin del ordenamiento");
}

void cambiar_posicion(int *n1, int *n2) //Funcion para cambiar la posicion de los elementos desordenados
{ 
    int temp =*n1;//Variable temporal que almacena un dato mientras hacemos el cambio
    *n1 = *n2;
    *n2 = temp;
} 
  
int particion (int arr[], int low, int high) //Funcion para particionar el array
{ 
    int i = (low - 1);  //Indice del elemento mas pequeño 
    int pivot = arr[high];    //Pivot 
    
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) //Si el elemento actual es menor o igual a pivote 
        { 
            i++;     
            cambiar_posicion(&arr[i], &arr[j]); 
        } 
    } 
    cambiar_posicion(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
void quickSort(int arr[], int low, int high) //Funcion de ordenamiento
{ 
    if (low < high) 
    { 
        int pi = particion(arr, low, high); //pi es el indice de particionamiento
        quickSort(arr, low, pi - 1); //Organiza los elementos antes de la particion
        quickSort(arr, pi + 1, high); //Organiza los elementos de despues de la particion
    } 
} 
  
void printArray(int arr[], int n) //Funcion para imprimir el array
{ 
    int i; 
    for (i=0; i < n; i++) 
        printf("%d ", arr[i]); 
    printf("\n Fin del ordenamiento"); 
} 
  
int main(int argc, char const *argv[]) //Funcion principal
{ 
    int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};
    int n = sizeof(arr)/sizeof(arr[0]);  //sizeof es una funcion que da el tamaño de bites de lo que necesitemos
    quickSort(arr, 0, n-1); 
    printf("El array ordenado: \n"); 
    printArray(arr, n); 
    printf("\n");
    return 0; 
} 

Hola, comparto mi implementación en javascript(typescript):

const partition = (arr: number[], low: number, hi: number) => {
  const pivot = arr[low];
  let i = low;
  let j = hi;

  while (i < j) {
    do { i++; } while (arr[i] <= pivot);
    do { j--; } while (arr[j] > pivot);

    if (i < j) {
      swap(arr, i, j);
    }
  }
  swap(arr, low, j);
  return j;
}

const swap = (arr, i: number, j: number) => {
  [arr[i], arr[j]] = [arr[j], arr[i]];
}

const quickSort = (arr: number[], low: number, hi: number) => {
  if (low < hi) {
    let j = partition(arr, low, hi);
    quickSort(arr, low, j);
    quickSort(arr, j+1, hi);
  }

  return arr;
}

QuickSort con JavasCript 😄

const c = console.log

const particion = (arrayInteger, lower, higher) =>{
  let i, pivot, accountA, accountB
  i = ( lower - 1 )
  pivot = arrayInteger[higher]

  for (let j =  lower; j < higher; j++) {
    if (arrayInteger[j] <= pivot){
      i = i + 1
      accountA = arrayInteger[i]
      arrayInteger[i] = arrayInteger[j] 
      arrayInteger[j] = accountA
    }
  }
  accountB = arrayInteger[i+1]
  arrayInteger[i+1] = arrayInteger[higher]
  arrayInteger[higher] = accountB

  return (i+1)
}

const quickSort = (arrayInteger, lower, higher) => {
  let pi
  if (lower < higher){
    pi = particion(arrayInteger, lower, higher)
    quickSort(arrayInteger, lower, pi-1)
    quickSort(arrayInteger, pi+1, higher)
  }
}
  
  
const arr = [1998, 1990, 10, 5, 6, 0, 1, -10, 3]
const n = arr.length
quickSort(arr, 0 , n-1)
c("Arreglo Ordenado: ")
arr.forEach(element => {
  c(`${element}`)
})

En Python, QuickSort sin complicarse tanto como el profe:

def ordenar(not_ordened_list):
	if len(not_ordened_list) == 0:
		return []
	elif len(not_ordened_list) ==1:
		return not_ordened_list

	left = []
	right = []
	equals = []
	pivote = not_ordened_list[0]

	for n in not_ordened_list[1:]:
		if pivote > n:
			left.append(n)
		elif pivote < n:
			right.append(n)
		elif pivote == n:
			equals.append(n)

	return ordenar(left) + [pivote] + equals + ordenar(right)



def run():
	not_ordened_list = [
3, 94, 86, 82, 90,
10, 87, 36, 61, 8,
17, 15, 22, 10, 23,
78, 25, 2, 30, 45,
98, 43, 98, 59, 53,
57, 2, 64, 1, 41,
32, 58, 19, 99, 60,
74, 48, 80, 44, 25,
68, 1, 89, 77, 60,
25, 99, 30, 76, 32,
57, 82, 52, 44, 72,
87, 34, 87, 65, 30,
54, 6, 31, 33, 44,
44, 42, 82, 90, 17,
9, 98, 28, 86, 69,
3, 17, 8, 45, 98,
12, 47, 95, 43, 72,
39, 41, 82, 74, 56,
65, 79, 50, 26, 67,
100, 24, 67, 38, 57]
	
	print('LISTA NO ORDENADA')
	print(not_ordened_list)
	ordened_list = ordenar(not_ordened_list)
	print('\nLISTA ORDENADA')
	print(ordened_list)



if __name__ == '__main__':
	run()```

¡Hola! Les comparto la implementación con C# con ordenamiento asc y desc:
 
Código fuente

using System;

namespace QuickSort
{
  public class QuickSort
  {
    public void Sort(ref int[] target, int order = 1)
    {
      Sort(ref target, order, 0, target.Length - 1);
    }

    private void Sort(ref int[] target, int order, int min, int max)
    {
      if (min < max)
      {
        int pi = Partition(ref target, order, min, max);
        Sort(ref target, order, min, pi - 1);
        Sort(ref target, order, pi + 1, max);
      }
    }

    private int Partition(ref int[] target, int order, int min, int max)
    {
      bool right = true, asc = order == 1;
      int pi = min, index = max, piv, prevIndex;

      while (pi != index)
      {
        if ((right != asc && target[pi] < target[index]) || (right == asc && target[pi] > target[index]))
        {
          prevIndex = index;
          piv = target[pi];
          target[pi] = target[index];
          target[index] = piv;
          index = pi;
          pi = prevIndex;
          right = !right;
        }
        else
        {
          if (right) index--; else index++;
        }
      }

      return pi;
    }
  }
}

Mi aporte en php

<?php

#necesitamos dividir nuestro dataset
#necesitamos un punto pivoltal
#recursivamente ordenar cada mitad de mi array

class quickSortClass{
  public $arr = array();
  public $n;
  
  public function main(){
    $this->arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10];
    $this->n = count($this->arr);
    $this->quickSort(0, $this->n-1);
    echo("Arrar Ordenado: ");
    foreach($this->arr as $item){
        echo($item.', ');
    } 
  }
  public function particion($low, $high){
      
      $i =$low-1;
      $pivot = $this->arr[$high];
      
      for($j=$low; $j<$high; $j++){
          if($this->arr[$j]<= $pivot){
              $i = $i+1;
              $aux = $this->arr[$i];
              $this->arr[$i] = $this->arr[$j];
              $this->arr[$j] = $aux;
          }
      }

      $aux = $this->arr[$i+1];
      $this->arr[$i+1] =  $this->arr[$high];
      $this->arr[$high] = $aux;
      return ($i+1);
  }

  function quickSort($low, $high){
      if($low < $high){
          $pi = $this->particion($low, $high);
          $this->quickSort($low, $pi-1);
          $this->quickSort($pi+1, $high);
      };
  }  
}

    
$obj = new quickSortClass();
$obj->main();
    

Mi aporte en javascript

function quickSort(array,origin,limit){
    
    if(array.length > 1){
        var pivote = array[limit];
        var i = origin, j = limit;

        while(i <= j){
            while(i <= limit && array[i] < pivote){
                i++;
            }
            while(j >=0 && array[j] > pivote){
                j--;
            }

            if(i <= j){
                change(array,i,j)
                i++;
                j--;
            }

        }

        if(j > origin){
            quickSort(array,origin,j);
        }
        if(i < limit){
            quickSort(array,i,limit);
        }
        
        
    }
    
}

function change(data,starPosition,finalPosition){
    var tempValue = data[finalPosition];
    data[finalPosition] = data[starPosition];
    data[starPosition] = tempValue;
}

var vector = [-6688,5904,4735,-2940,8830,9976,-3674,4222,-1446,6187,
   -3181,-8882,5487,-6939,-7885,3786,-6234,-1062,-4553,-5709,8459,5008,3352,6586,537,-7610,3261,
    8246,-2105,5107,7957,-7886,-2925,-2541,-7449,9521,5073,-239,-8054,-4379,-8323,-6485,-4828,
   -5294,-2720,595];

   quickSort(vector,0,vector.length-1);

   console.log(vector);

Kotlin:

/*
* Necesitamos dividir nuestro dataset
* Necesitamos un punto pivotal
* Recursivamente ordenar cada mitad de mi array
* */


fun main(args: Array<String>) {
    val list = mutableListOf(1992, 1990, 10, 5, 6, 100, 0, 1, -10)
    quickSort(list, 0, list.size - 1)
    println("Ordenado: ")
    list.map {
        print("$it ")
    }
}

fun particion(v: MutableList<Int>, low: Int, high: Int) : Int{
    var i = (low-1)
    val pivot = v[high]

    for (j in low until high){
        if(v[j] <= pivot){
            i++
            val temp = v[i]
            v[i] = v[j]
            v[j] = temp
        }
    }

    val aux = v[i+1]
    v[i+1] = v[high]
    v[high] = aux
    return (i+1)
}

fun quickSort(v: MutableList<Int>, low: Int, high: Int){
    if(low < high){
        val partitionIndex = particion(v, low, high)
        quickSort(v, low, partitionIndex-1)
        quickSort(v, partitionIndex +1, high)
    }
}

Buenas a todos, aquí está el código en C, con unas funciones extra para facilitar el trabajo, cuales son swap para realizar el intercambio entre valores de variables y print para imprimir el array resultante.

#include <stdio.h>

void swap(int *n1, int *n2)
{
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

void print(int S[], int n)
{
    int i;
    for (i = 0; i < n; i++)
        printf("%d,  ", S[i]);
    printf("\n");
}

int partition(int arr[], int low, int high)
{
    int j;
    int i = low - 1;
    int pivot = arr[high];
    for( j = low; j < high; j++)
    {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i+1], &arr[high]);
    return (i+1);
}

void quickSort(int arr[], int low, int high)
{
    int pi;
    if (low < high)
    {
        pi = partition(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
    
}

int main(int argc, char const *argv[])
{
    int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -1};
    int sizeOf = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, sizeOf-1);
    print(arr, sizeOf);

    return 0;
}

En Java 😃

package sorting;

import java.util.Random;

public class QuickSort {
	
	static void sort(int arr[], int start, int end) {
		if(start >= end) {
			return;
		}
	
	int index = partition(arr, start, end);
	sort(arr, start, index - 1);
	sort(arr, index + 1, end);
	}
	
	static int partition(int arr[], int start, int end) {
		int pivotIndex = start;
		int pivotValue = arr[end];
		for(int i = start; i < end; i++) {
			if(arr[i] < pivotValue) {
				swap(arr, i, pivotIndex);
				pivotIndex++;
			}
		}
		swap(arr, pivotIndex, end);
		return pivotIndex;
	}
	
	static void swap(int arr[], int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}

	public static void main(String[] args) {
		int array[];
		Random generator = new Random();
		int lenght = 100;
		array = new int[lenght];
		for(int i = 0; i < lenght; i++) {
			array[i] = generator.nextInt(1000);
		}
		
		sort(array, 0, 99);
		for(int i = 0; i < lenght; i++) {
			System.out.println(array[i]);
		}
	}

}

Hasta que la practique bien

Explicación, parte que le falto al profe

No me quedaba claro el ordenamiento de la funcion particion pero este video me ayudo a entender el orden lógico en el que se desplazan los números de izquierda a derecha:
https://www.youtube.com/watch?v=WprjBK0p6rw

Les comparto el código implementado en python y explicado de forma simple.

def quick_sort(lista):
    # Entendamos que el algoritmo de QuickSort se basa en recursivamente ir partiendo la lista en una mitad izquierda,
    # derecha y ordenarlas, haciendo uso de la recursividad, hasta que solo quedan 1 elemento a ser ordenado 
    # Empezamos por definir nuestras 3 listas auxiliares, valores menores al pivote, valores iguales al pivote y valores 
    # mayores al pivote.
    izquierda = []
    centro = []
    derecha = []
    # Si la cantidad de elementos que contiene la lista es > 1 significa que al menos hay 2 y estos pueden ser ordenados como
    # menor, igual o mayor que el elemento pivote y aún puede llamarse a si misma la función quicksort
    if len(lista) > 1:
        # Nuestro valor pivote, será siempre el primer elemento que tenga la lista a ser ordenada (está NO necesariamente
        # es la forma más eficiente de implementar el algoritmo, pero sí es la más simple de programar)
        pivote = lista[0]
        # Para cada elemento de la lista (solo puede haber 3 casos)
        for i in lista:
            # ese elemento es menor al pivote, por ende se añade a los elementos del lado izquierdo
            if i < pivote:
                izquierda.append(i)
            # ese elemento es igual al pivote, por ende se añade a los elementos del centro
            elif i == pivote:
                centro.append(i)
            # ese elemento es mayor al pivote, por ende se añade a los elementos del lado derecho
            elif i > pivote:
                derecha.append(i)
        # De manera auxiliar vamos a imprimir los valores de las 3 listas que conforman nuestra solución
        print("L", izquierda, "C", centro, "R", derecha)
        # Este return SOLO terminará hasta que la condición de escape se cumpla (len(lista) < = 1) mientras no se cumpla
        # Entonces estará ejecutándose hacia adentro de sí misma de forma recursiva.
        return quick_sort(izquierda) + centro + quick_sort(derecha)
    else:
        # Finalmente, cuando la lista solo contiene un elemento, entonces por definición ya se encuentra ordenada y podemos
        # terminar el ciclo recursivo, porque ya no podemos volver a llamar a quicksort en una lista de un solo elemento.
        return lista

Este ya lo habia echo en la escuela jeje
#include<stdio.h>
int part(int arr[],int piv,int l,int r){
while(l<=r){
while(arr[l]<piv){
l++;
}
while(arr[r]>piv){
r–;
}
if(l<=r){
int temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l++;
r–;
}
}
return l;
}
void quicksort(int arr[],int l,int r){
if(l>=r){
return;
}
int pivote=arr[(l+r)/2];
int pos=part(arr,pivote,l,r);
quicksort(arr,l,pos-1);
quicksort(arr,pos,r);
}
int main(){
int cad[300];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&cad[i]);
}
quicksort(cad,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",cad[i]);
}
return 0;
}

Para explicar algoritmo se utilizan diagramas de flujo en lugar de hacer cada algoritmo con un lenguaje distinto.

El curso que sigue a este es Introducción al C ¡¡¡insólito!!!
Hay que felicitar al coordinador de IOT ya que nadie podrá hacer las cosas peor.

Ejemplo con JS!
Explicado.

let items = [1,-3,7,6,2,9,50,47,20,11,8];

function swap(items, leftIndex, rightIndex){
    var temp = items[leftIndex];
    items[leftIndex] = items[rightIndex];
    items[rightIndex] = temp;
}
// (f) que busca el elemento pivote en la matriz, he inicializamos ambos punteros del extremo izquierdo y el derecho 
function partition(items, left, right) { 
  let pivot = items[Math.floor((right + left )/ 2)], //divide a la mitad los elementos
    i       =left, //puntero izquierdo
    j       =right; //puntero derecho 

//Compara el puntero izquierdo con el pivote y si es menor al pivote agrega 1 al indice izq.Continua hasta que el elemento izq sea > o = que el pivote

// Luego se compara el puntero derecho, si este es > que el pivote se resta 1, es decir se mueve el puntero derecho hacia la izquierda. 
  while (i <= j) { 
    while(items[i] < pivot) { 
      i++;
    }
    while (items[j] > pivot) { 
      j--;
    }
      //(f) swap intercambia elementos de cada indice, devolviendo el indice del puntero izquierdo 
    if (i <= j) { 
      swap(items, i, j); 
      i++; 
      j--; 
    }
  }
  return i; 
}

function quickSort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //Se devuelve el puntero izquierdo y se divide la matriz, realizando la  clasificación. divide and conquer 
        if (left < index - 1) { //elementos para el lado izq del pivote 
            quickSort(items, left, index - 1);
        }
        if (index < right) { //elementos para el lado derecho del pivote 
            quickSort(items, index, right);
        }
    }
    return items;
}
// Se llama a la función 
var sortedArray = quickSort(items, 0, items.length - 1);
console.log(sortedArray);

No comprendo! lo he escrito idéntico y siempre en el compilador me da errores
![](

Comparto mi código en C

#include<stdio.h>
#include<stdlib.h>

void quickSort(int intArray[], int left, int right)
{
    //if the left and right index are the same or left index is the last one of the index, just return
    if(left >= right) { return; }

    //Find the pivot reference to do the partition "without take it"
    int pivot = partition(intArray, left, right);

    //Do quicksort in the array partitions
    quickSort(intArray, left, pivot - 1);
    quickSort(intArray, pivot + 1, right);
}

int partition(int intArray[], int left, int right)
{
    //Find the last reference of the array, and set it as the pivot to sort the array
    int pivot = intArray[right];
    int i = left - 1;
    for(int j = left; j < right; j++)
    {
        //If array in the actual index is less than pivot, swap positions
        if(intArray[j] < pivot)
        {
            i++;
            swap(&intArray[i], &intArray[j]);
        }
    }
    //Swap the original pivot and the last "i" + 1 value, this determine the new position of the pivot to do the partition
    swap(&intArray[right], &intArray[i + 1]);
    return i + 1;
}

void swap(int *n1, int *n2)
{
    int nTemporal = *n1;
    *n1 = *n2;
    *n2 = nTemporal;
}

void printSorted(int intArray[], int length)
{
    int i;
    printf("The sorted array is: \n");
    for(i = 0; i < length; i++)
        printf("%d\n", intArray[i]);
}

int main(int argc, char const *argv)
{
    int number;
    int intArray[300];
    int i = 0;
    FILE *file = fopen("numbers.txt", "r");

    //Read the file line by line and set the numbers into intArray
    while(fscanf(file, "%d", &number) == 1)
    {
        intArray[i] = number;
        i++;
    }

    int arrayLength = sizeof(intArray)/sizeof(intArray[0]);

    //Do quick sort
    quickSort(intArray, 0, arrayLength);

    //print sorted array
    printSorted(intArray, arrayLength);

    fclose(file);
    return 0;
}

Con JavaScript:

function swap(arr, i, j){
    const temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

function partition(arr, l, r){
    const p = arr[r]
    let i = l - 1
    for(let j = l; r - 1 >= j; j++){
        if(arr[j] < p){
            i += 1
            swap(arr, i, j)
        }
    }

    swap(arr, i + 1, r)

    // Pivot index
    return i + 1
}

function qs(arr, l, r){
    if(l >= r){
        return arr
    }

    const p = partition(arr, l , r)

    qs(arr, l, p - 1)
    qs(arr, p + 1, r)

    return arr
}

const arr = [-2,3,-1,5,4,-3,0]


qs(arr, 0, arr.length - 1

# Para esta clase aprenderemos a reordenar una serie de números mediante quick sort, que no es más que un algoritmo de divide y vencerás, nuestro algoritmo se dividirá en 3:

# Necesitamos dividir nuestro data set
# Obtener un punto pivotal
# Recursivamente ordenar cada mitad de mí array

def particion(arr, low, high):
    i = (low - 1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quickSort(arr, low, high):
    if low < high:
        pi = particion(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Array ordenado: ")
for i in range(n):
    print(arr[i])

En lenguaje C

#include <stdio.h>

int particion(int *arr, int low, int high)
{
  int i = (low - 1);
  int j, aux, pivot;

  pivot = arr[high];

  for (j = low; j < high; j++)
  {
    if (arr[j] <= pivot)
    {
      i = i + 1;
      aux = arr[i];
      arr[i] = arr[j];
      arr[j] = aux;
    }
  }
  aux = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = aux;

  return (i + 1);
}

void quickSort(int *arr, int low, int high)
{
  int pi;
  if (low < high)
  {
    pi = particion(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}

int main(int argc, char const *argv[])
{
  int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};

  int n = sizeof(arr) / sizeof(arr[0]);
  int i;

  quickSort(arr, 0, n - 1);

  printf("Array ordenado: ");

  for (i = 0; i < n; i++)
  {
    printf("%d, ", arr[i]);
  }

  return 0;
}

listo copia al detalle, entiendo que es lo que hace pero no sabria como hacerlo solo, 😦 sigamos por que no hay tiempo.

QuickSort en Java

public class Main {

    public static void main(String[] args) {
	// write your code here
        QuickSort quickSort = new QuickSort();
        int[] array = {6,5,3,11,10,23,123,1,-1,2,3,6,6};
        int[] array2 = quickSort.quickSort(array,0, array.length-1);
        quickSort.printArray(array2);
    }
}

public class QuickSort {

    public int[] quickSort(int[] array,int start, int end)
    {
        if(start < end)
        {
            int pIndex = partition(array,start,end);
            quickSort(array,start,pIndex-1);
            quickSort(array,pIndex+1,end);
        }
        return array;
    }


    private int partition(int[] array, int start, int end)
    {
        int pivot = array[end];
        int pIndex = start;
        for(int i=start; i<end; i++)
        {
            if(array[i]<=pivot)
            {
                int temp = array[i];
                array[i] = array[pIndex];
                array[pIndex] = temp;
                pIndex++;
            }
        }
        int temp = array[pIndex];
        array[pIndex] = array[end];
        array[end] = temp;
        return pIndex;
    }

    public void printArray(int[] array)
    {
        for(int i=0; i<array.length; i++)
        {
            System.out.print(array[i] + ", ");
        }
        System.out.println("");
    }
}

Made in C:

#include <stdio.h>

int particionar(int datos[], int inic, int final)
{
    int i, ind_eje, pivote, temp;
    pivote = datos[final];
    ind_eje = inic;
    for(i = inic; i < final; i++)
    {
        if(datos[i] <= pivote)
        {
            temp = datos[i];
            datos[i] = datos[ind_eje];
            datos[ind_eje] = temp;
            ind_eje++;
        }
    }
    temp = datos[ind_eje];
    datos[ind_eje] = datos[final];
    datos[final] = temp;
    return(ind_eje);
}

void quickSort(int datos[], int inic, int final)
{
    if(inic < final)
    {
        int eje = particionar(datos, inic, final);
        quickSort(datos, inic, eje-1);
        quickSort(datos, eje+1, final);
    }    
}

int main()
{
    int original[]={158, 142, 111, 101, 99, 95, 91, 50, 46, 33, 31, 30, 29, 25, 25, 20, 9, 1};
    int tam = sizeof(original)/sizeof(int);
    printf("\nArreglo desordenado: \n");
    for(int i=0; i<tam; i++)
        printf("%d ", original[i]);
    quickSort(original, 0, tam-1);
    printf("\n\nArreglo ordenado: \n");
    for(int i=0; i<tam; i++)
        printf("%d ", original[i]);
    printf("\n\n");     
    return 0;
}

Funcionando.

Implementacion algoritmo QuickSort en Elixir

Con elixir aseguro que se esta trabajando con recursividad

defmodule Quicksort do
  def sort([]), do: [] # Cuando este Vacio
  def sort([head | tail]) do
    # Particiono cabeza y resto del arreglo
    { before, aft } = Enum.partition(tail, &(&1 < head))
    # Tomo cada uno de los elementos, los comparo y lo pongo en la mitad del
    # antes y el despues, el antes puede ser vacio, lo mismo el despues
    sort(before) ++ [head] ++ sort(aft)
  end
end

defmodule Ejecucion do
  def main do
    IEx.configure(inspect: [charlists: :as_lists])
    lista_elementos = [84, 32, 43, 12, 4, 49, 34, 5, 53, 4, 43, 100, 21, 2]

    IO.puts("---- Elementos No Ordenados ----")
    IO.inspect(lista_elementos, charlists: :as_lists)
    lista_elementos = Quicksort.sort(lista_elementos)
    IO.puts("\n---- Elementos Debidamente Organizados ----")
    IO.inspect(lista_elementos, charlists: :as_lists)
    :ok
  end
end

La forma de Ejecutarlo

Ejecucion.main()

Al ejecutarlo daría lo siguiente:

RecursionError: maximum recursion depth exceeded in comparison

alguien ha encontrado solución a esto? me pasa en un millon para arriba

from random import seed
from random import random
from time import time
import sys

def valoresRandom(cantidad):
	arregloDatos = [i for i in range(0,cantidad)]
	for i in range(0,cantidad):
		arregloDatos[i]=round(random()*1000)
	return arregloDatos

def particion(arr, low, high):
    i =(low-1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j]<= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] =arr[high],arr[i+1]
    return (i+1)


def quickSort(arr, low, high):
    if low < high:
        pi = particion(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)
    

valorEntrada = 1000000
arregloNoOrdenado = valoresRandom(valorEntrada)

timeStart = time()
arregloOrdenadoQuick = quickSort(arregloNoOrdenado,0,len(arregloNoOrdenado)-1)
timeEnd = time()
print(timeEnd-timeStart)

Código C++

#include <iostream>
#include <string.h>
using namespace std;
void swap(int *n, int *n1){
	int aux = *n;
	*n = *n1;
	*n1 = aux;
}

int particion(int array[], int low, int high){
	int i = (low - 1);
	int pivot = array[high];
	
	for(int j = low; j < high; j++){
		if(array[j] <= pivot){
			i++;
			swap(&array[i], &array[j]);
		}
	}
	
	swap(&array[i+1], &array[high]);
	
	return (i+1);
}

void quickSort(int array[], int low, int high){
	
	if(low<high){
		int pi = particion(array, low, high);
		quickSort(array, low, pi - 1);
		quickSort(array, pi + 1, high);
	}
}

int main(){
	
	int array [] = {1992, 1990, 10, 5, 6, 100, 0, 1, -1};
	int n = sizeof(array) / sizeof(array[0]);
	quickSort(array, 0, n - 1);
	
	cout<<"Array ordenado:"<<endl;
	
	for(int i = 0; i < n; i++){
		cout<<array[i]<<", "<<endl;
	}
}```

def particion(arr, low, high):
    i =(low-1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j]<= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] =arr[high],arr[i+1]
    return (i+1)


def quickSort(arr, low, high):
    if low < high:
        pi = particion(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)


arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10]
n = len(arr)
quickSort(arr, 0, n-1)
print("Array Ordenado:")
for i in range(n):
    print("%d" %arr[i]),

Mi implementación en Java:

public class Quicksort {

    /**
     * Ésta función toma el último elemento como el pivote, coloca
     * el elemento pivote en su posición correcta en el array
     * ordenado, y coloca los elementos pequeños a la izquierda
     * del pivote y los más grandes a la derecha del pivote.
     * */
    public int partition(int arr[], int low, int high) {
        int pivot = arr[high]; //Toma la última posición cómo pivote.
        int i = (low - 1); //Índice del elemento más pequeño.

        for (int j=low; j<high; j++) {

            /*Si el valor actual es más pequeño
            o igual que el pivote*/
            if (arr[j] <= pivot) {
                i++;

                //Intercambia arr[i] por arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        //Intercambia arr[i+1] y arr[high] (o el pivote).
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    /**
     * La función principal que implementa quickSort()
     * arr[] --> array a ordenar.
     * low --> Índice inicial.
     * high --> Índice final.
     * */
    public void sort(int arr[], int low, int high) {
        if (low < high) {
            /*
            * pi es 'partition index' (índice de partición)
            * */
            int pi = partition(arr,low,high);

            /*
            * Recursivamente ordena los elementos antes de la
            * partición y después de la partición.
            * */
            sort(arr,low,pi-1);
            sort(arr,pi+1, high);
        }
    }

    /**
     * Función de utilidad para imprimir el array.
     * */
    public void printArray(int arr[]) {
        int n = arr.length;

        for (int i=0; i<n;i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

codigo en php, creado por mi mismo

<?php
function sorts(&$array ,$i,$posPivote){
	$indexPivote = $posPivote;// El Pivote comienza en el final
	$j = $indexPivote - 1; // indice derecho comienza en el final - 1
	$pivote = $array[$indexPivote];
	//echo "El Pivote = array[ " . $indexPivote. " ] = " . $array[ $indexPivote ] . "\n";
	while ($i != $j && $i < $j):
		if( ($array[$i] > $pivote) && ($array[$j] < $pivote) ):
			$temp = $array[$i];
			$array[$i] = $array[$j];
			$array[$j] = $temp;
		endif;
		if( ($array[$j] == $pivote) && ($array[$i] > $pivote) ):
	    	$temp = $array[$i];
			$array[$i] = $array[$j];
			$array[$j] = $temp;
	   	endif;	
	    if( $array[$i] <= $pivote ){$i++;}
	    if($i == $j) break;
	    if( $array[$j] > $pivote ){$j--;}
	endwhile;

	if($array[$i] <= $pivote):
		$i++;
	endif;
	$array[$indexPivote] = $array[$i];//Aqui se podria usar $i o $j 
	$array[$i] = $pivote;
	echo "Paso\n";
	print_r($array);
	return $i;
}

function quickSort(&$array,$low,$posPivote){
	if( $low < $posPivote ){
	     $i = sorts($array,$low,$posPivote);
	     quickSort($array,$low,$i-1);
	     quickSort($array,$i + 1,$posPivote);
	}

}	
$array = [2,5,3,7,6,5,5,0,5,5,2];
$posPivote = count($array) - 1;
$start_time = microtime(TRUE);
quickSort($array,0,$posPivote);
$end_time = microtime(TRUE);d
echo ( $end_time - $start_time ) * 3600 . " Seg\n";
print_r($array);

En C:

#include <stdio.h>
#include <stdlib.h>

void swap(int *num1, int *num2) {

    int aux;
    aux = *num1;
    *num1 = *num2;
    *num2 = aux;

}




int particion(int arr[], int low, int high) {

    int i = low - 1;
    int j;
    int pivote = arr[high];
    //int aux;

    for (j = low; j < high; j++) {

        if (arr[j] <= pivote) {

            i++;
            swap(&arr[i], &arr[j]);

        }
    }

    int masUno = i + 1;

    swap(&arr[masUno], &arr[high]);
    return (masUno);

}

int quickSort(int arr[], int low, int high) {

    int parIndex;

    if (low < high) {

        parIndex = particion(arr, low, high);
        quickSort(arr, low, parIndex - 1);
        quickSort(arr, parIndex + 1, high);

    }


}

int main() {

    int array1[9] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};

    int arrayLength = sizeof(array1)/sizeof(array1[0]);

    quickSort(array1, 0, arrayLength-1);

    printf("Array: \n");

    for (int i = 0; i < arrayLength - 1; i++) {

        printf("%d\n ", array1[i]);

    }

    return 0;

}

Dejo mi ejemplo en c#.
Acerca de este lenguaje, acabo de pensar, que algoritmos como el bubble sort se podrian hacer con bucles foreach, los veo mas legibles que los for a la hora de manejar arrays.

using System;
namespace QuickSharpSort
{
    class Program
    {
        static void cambiar(ref int a,ref int b)
        {
            int temp = a;
            a = b;
            b = temp;
        }
        static int particion(int[] arr, int low, int high)
        {
            int i = low - 1;
            int pivot = arr[high];
            for (int j = low; j < high; j++)
            {
                if (arr[j] <= pivot)
                {
                    i = i + 1;
                    cambiar(ref arr[i],ref arr[j]);
                    
                }
            }
            cambiar(ref arr[i + 1], ref arr[high]);
            return i + 1;
        }

        static void quickSort(int[] arr, int low, int high)
        {
            if (low<high)
            {
                int pindex = particion(arr, low, high);
                quickSort(arr, low, pindex - 1);
                quickSort(arr, pindex+1,high);
            }
        }
        static void Main(string[] args)
        {
            int[] arr = { 1992, 1990, 10, 5, 6, 100, 0, 1, -10 };
            int n = arr.Length;
            quickSort(arr, 0, n - 1);
            Console.WriteLine("Array Ordenado: ");
            foreach (int i in arr)
            {
                Console.WriteLine(i);
            }
        }
    }
}

QuickSort.swift

import Foundation

func divide(arr: inout [Int], low: Int, high: Int) -> Int {
    var temp: Int?
    var i = low - 1
    var pivot = arr[high]
    
    for j in (low..<high) {
        if arr[j] <= pivot {
            i += 1
            temp = arr[i]
            arr[i] = arr[j]
            arr[j] = temp!
        }
    }
    
    temp = arr[i + 1]
    arr[i + 1] = arr[high]
    arr[high] = temp!
    
    return (i+1)
}

func quick_sort(arr: inout [Int], low: Int, high: Int) {
    if low < high {
        var partitionIndex: Int = divide(arr: &arr, low: low, high: high)
        quick_sort(arr: &arr, low: low, high: partitionIndex - 1)
        quick_sort(arr: &arr, low: partitionIndex + 1, high: high)
    }
}

Aqui mi codigo en C, no tengo problemas de compilacion pero al ejecutarlo sale el mensaje **“Segmentation fault (core dumped)” ** alguna idea de por qué?

#include <stdio.h>


int partition(int arr[], int low, int high){
    int i = low -1;
    int pivot= arr[high];

    for (int j = low; i <= high; i++)
    {
        if(arr[j]<= pivot){
            i++;
            arr[i] =arr[j];
            arr[j]=arr[i];
        }
    }
    
    arr[i+1]=arr[high];
    arr[high]=arr[i+1];

    return i+1;
}

int quickSort(int arr[],int low, int high){
    if (low<high){
        int pivot = partition(arr,low,high);
        quickSort(arr,low,pivot-1);
        quickSort(arr,pivot,high);
    }
}

int main(int argc, char const *argv[])
{
      
    int arr[]={10,50,20,30,2,40,15,16};
    //int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr,0,8);
    printf("Array ordenado \n ");
    for (int i = 0; i < 8; i++)
    {
        printf("%d , ",arr[i]);
    }
    printf("\nFin del ordenamiento");
    return 0;
}

quickSort en js

function particion(arr, low, high) {
	let i = (low - 1)
	let pivot = arr[high]

	for (let j = low; j < high; j++) {
		if (arr[j] <= pivot) {
			i = i + 1
			let aux = arr[i]
			arr[i] = arr[j]
			arr[j] = aux
		}
	}

	let aux = arr[i + 1]
	arr[i + 1] = arr[high]
	arr[high] = aux

	return (i + 1)
}

function quickSort(arr, low, high) {
	if (low < high) {
		let partIndex = particion(arr, low, high)
		quickSort(arr, low, partIndex - 1)
		quickSort(arr, partIndex + 1, high)
	}
}

var array = new Array(1992, 1990, 10, 5, 6, 100, 0, 1, -10)
let n = array.length
quickSort(array, 0, n - 1)
console.log(array)

¿Alguien me puede explicar por que quitar esa coma del final hace que se imprima de manera vertical, pero ponerla hace que imprima de manera horizontal?

La traduccion a C++:

#include <iostream>

void swap (int* a, int* b);
int partition(int* arr, int low, int high);
void quickSort(int* arr, int low, int high);

int main() {
  int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n-1);

  for (int i = 0; i < n; i++)
    std::cout << arr[i] << ", ";
  std::cout << "\n";

  return 0;
}

void swap (int* a, int* b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

int partition(int* arr, int low, int high) {
  int i = low-1;
  int pivot = *(arr+high);

  for (int j = low; j < high; j++) {
    if ( *(arr+j) <= pivot) {
      i++;
      swap( arr+i, arr+j );
    }
  }

  swap( arr+i+1, arr+high );
  return i+1;
}

void quickSort(int* arr, int low, int high) {
  if ( low < high ) {
    int partitionIndex = partition(arr, low, high);
    quickSort(arr, low, partitionIndex-1);
    quickSort(arr, partitionIndex+1, high);
  }
}

En C.

#include<stdio.h>

int particion(int vector[], int low, int high)
{
	int i = low-1, j, temp;
	int pivote = vector[high];
	
	for(j=low; j<high; j++)
	{
		if(vector[j]<=pivote)
		{
			i+=1;
			temp=vector[i];
			vector[i] = vector[j];
			vector[j]=temp;
		}
	}
	temp=vector[high];
	vector[high] = vector[i+1];
	vector[i+1] = temp;
	return (i+1);
}

int mergeSort(int vector[], int low, int high)
{
	int partitionIndex;
	if(low<high)
	{
		partitionIndex = particion(vector, low, high);
		mergeSort(vector, low, partitionIndex-1);
		mergeSort(vector, partitionIndex+1, high);
	}
}

int main() {
	int i;
	int datos[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
	int n = sizeof(datos)/sizeof(datos[0]);
	mergeSort(datos, 0, n);
	printf("Vector arreglado.\n");
	for(i=0; i<n; i++)
	{
		printf(" %d, ",datos[i]);
	}
	return 0;
}

C mamo con la parte de HTML xD

Comparto el desafio en C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int particion( int arr[], int low, int high)
{
    int i;
    int pivot;
    int dato;
    int j;

    i = low-1;
    pivot = arr[high];

    for(j=low; j<high; j++)
    {
        if(arr[j]<= pivot)
        {
            i = i+1;
            dato = arr[i];
            arr[i] = arr[j];
            arr[j] = dato;
        } 
    }

    dato = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = dato;

    return (i+1);
}

int quickSort(int arr[], int low, int high)
{   
    int pi;

    if (low < high)
    {
        pi = particion(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}


int main()
{
    int arr[] = {10, 3, 1995, 100, 0, -1, -3, 200};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i;

    quickSort(arr, 0, n-1);
    printf("Array Ordenado: \n");

    for(i=0; i<n; i++)
    {
        printf("%d, ", arr[i]);
    }
    return 0;
}```

Mi codigo en java:

public class QuickSort{
    
    public static void main(String[] args) {
        int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78,
            25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60,
            74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52,
            44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9,
            98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74,
            56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};
        
        //int arr[] = {5,3,4,1,2};

        System.out.println("Given Array"); 
        System.out.println(java.util.Arrays.toString(arr));
    
        QuickSort obj = new QuickSort(); 
        obj.quickSort(arr, 0, arr.length-1); 
    
        System.out.println("\nSorted array"); 
        System.out.println(java.util.Arrays.toString(arr));
    }

    public int Partition(int arr[], int low, int high){

        int i = low - 1;
        int pivot = arr[high];

        for (int j = low; j < high; j++) {
            if(arr[j] <= pivot){
                i++;
                Swap(arr,i, j);
            }  
        }
        
        Swap(arr,i+1, high);

        return i;

    }

    void Swap(int arr[], int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public void quickSort(int arr[], int low, int high){
        if(low < high){
            int pi = Partition(arr, low, high); //get the partition index
            quickSort(arr, low, pi); //the high is the partition index;
            quickSort(arr, pi + 1, high); //the low is the partition index + 1;
        }

    }
}

Si usan Python 3 la impresión la pueden hacer un poco más legible (a mi parecer) sólo poniendo

print(f'{ array[i] }')

Ahora sí, lo logré en C. Dejé en Comentarios las funciones de Python para comparación. 😄

/* #necesitamos dividir nuestro dataset
#necesitamos un punto pivotal
#recursivamente ordenar cada mitad de mi arreglo */

#include<stdio.h>

/* def particion(arr, low, high):
    i=(low-1)
    pivot = arr[high]

    for j in range(low, high):
        if arr[j]<=pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]
    return(i+1) */

int particion(int arr[], int low, int high)
{
    int i = (low-1);
    int pivot = arr[high];
    int tempA, tempB;

    for(int j = low; j<= high - 1; j++)
    {
        if(arr[j] <= pivot)
        {
            i++;
            tempA = arr[i];
            arr[i] = arr[j];
            arr[j] = tempA;
        }  
         
    }

    tempB = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = tempB;
    

    return(i+1);      
}

/* def quickSort(arr, low, high):
    if low < high:
        pi = particion(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high) */

int quickSort(int arr[], int low, int high)
{
    if(low < high)
    {
        int pi = particion(arr, low, high);
        quickSort(arr, low, pi-1);
        quickSort(arr, pi+1, high);
    }
}

/* arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10]
n = len(arr)
quickSort(arr, 0, n-1)
print("Array ordenado: ")
for i in range(n):
    print("%d" %arr[i]),  */

int main()
{    
    int arr[] = {1992,1990,10,5,6,100,0,1,-10};
    
    int n = 9;

    quickSort(arr, 0, n-1);

    printf("Array Ordenado:"); 
    
    for(int i = 0; i < n; i++)
    {
        printf("%d, ", arr[i]);
    }

    return 0;
}

Quick Sort en C:

#include<stdio.h>

void cambiar_pos(int *n1, int *n2) {
    int temp = *n1;
    *n1 = *n2;
    *n2 = temp;
}

int division(int arr[], int inicio, int final) {
    int pivote = arr[final];
    int i = (inicio - 1);

    for(int j = inicio; j <= final - 1; j++ ) {
        if(arr[j] > pivote) {
            i++;
            cambiar_pos(&arr[i], &arr[j]);
        }
    }
    cambiar_pos(&arr[i + 1], &arr[final]);
    return (i + 1);
}

void quickSort(int arr[], int inicio, int final) {
    if(inicio < final) {
        int pi = division(arr, inicio, final);
        quickSort(arr, inicio, pi - 1);
        quickSort(arr, pi + 1, final);       
    }
}

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

int main(int argc, char const *argv[])
{
    int arr[] = {3, 94, 86, 82, 90, 10, 87, 36, 61, 8, 17, 15, 22, 10, 23, 78, 25, 2, 30, 45, 98, 43, 98, 59, 53, 57, 2, 64, 1, 41, 32, 58, 19, 99, 60, 74, 48, 80, 44, 25, 68, 1, 89, 77, 60, 25, 99, 30, 76, 32, 57, 82, 52, 44, 72, 87, 34, 87, 65, 30, 54, 6, 31, 33, 44, 44, 42, 82, 90, 17, 9, 98, 28, 86, 69, 3, 17, 8, 45, 98, 12, 47, 95, 43, 72, 39, 41, 82, 74, 56, 65, 79, 50, 26, 67, 100, 24, 67, 38, 57};

    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Lista Ordenada: \n");
    printArray(arr, n);

    return 0;
}

Sos un crack Ricardo.

en c

#include <stdio.h>
#include <stdio.h>
#include <math.h>

int partition ( int arr[], , int low, int high)
{
int j
int i
int pivot
int datos

i =low-1
pivot = arr[high]

for (j=low j<high j++)
{
    if (arr[j]<= pivot)
    {
        i = i+1
        datos = arr[i]
        arr[i] = arr[j]
        arr[j] =datos
    }
}
dato =arr[i+1]
arr[i+1] = arr[high]
arr[high] = datos

return (i+1)

}

int quickSort(int arr[], int low, int high)
{
int pi

if(low < high)
{
    pi = partition(arr, low, high)
    quickSort(arr, low, pi-1)
    quickSort(arr, pi+1, high)
}

}

int main()
{
int arr[] = {15, 10, 1994, 2020. -34}
int n = sizeof(arr)/sizeof(arr[0])
int i

quickSort(arr, 0, n-1)
printf("el array ordenado es \n")

for (i=0, i<n, i++)
{
    printf("%d ", arr[i])
}
return 0

}

Aqui esta en Java

package principal;

public class Principal {
    
    public int particion(int arr[],int low,int high){
        int i =(low -1);
        int pivot = arr[high];
        int temp;
        
        for(int j = low; j < high ;j++){
            if(arr[j] <=  pivot ){
                i = i+1;
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;              
            }
            
        }
        
        temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        
        return(i + 1);
    }
    
    public void quickSort(int arr[],int low,int high){
        int pi = 0;
        if(low < high){
            pi = particion(arr,low,high);
            quickSort(arr, low, pi-1);
            quickSort(arr, pi+1, high);
        }
    } 
    //-------------------------------
    public static void main(String[] args) {
       Principal obj1 = new Principal();
      int arr[] ={15,14,13,12,11,10,11,12,13,14};
      int n = arr.length;
      obj1.quickSort(arr, 0, n-1);
        System.out.println("array ordenado");
        for(int i=0;i<  n;i++){
            System.out.println(arr[i]);
        }
        
        
    }
    
}

var arr = [1998, 1972, 2006, 10, 13, 4, 1018, 505, 896, -45];

function swap(arr, leftIn, rightIn){
    var temp = arr[leftIn];
    arr[leftIn] = arr[rightIn];
    arr[rightIn] = temp;
}

function partition(arr, left, right) {
  var pivot = arr[Math.floor((right+left) / 2)],
  i = left,
  j = right;

  while (i <= j) {
    while (arr[i] < pivot) {
      i++;
    }
    while (arr[j] > pivot) {
      j--;
    }
    if (i<=j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }

  return i;
}

function quickSort(arr, left, right) {

  var index;

  if (arr.length > 1) {
    index = partition(arr, left, right);

    if (left < index - 1) {
      quickSort(arr, left, index - 1);
    }

    if (index < right) {
      quickSort(arr, index, right);
    }
  }

  return arr; 
}

var result = quickSort(arr, 0, arr.length - 1);```

Dejo el algoritmo en JS, trate de hacerlo lo mas simple y óptimo:

function quickSort(array) {
    // Evaluamos que el arreglo tenga por lo menos 2 elementos
    if (array.length < 2) {
        return array;
    } else {
        // Tomamos el primer elemento del arreglo como pivote
        let piv = array.shift(); //Shift saca la primer posición
        let leftArray = [];
        let rightArray = [];
        // Recorremos el arreglo hasta acabar sus elementos
        while (array.length) {
            // Se mandan los elementos a los arreglos temporales
            if (array[0] <= piv) {
                leftArray.push(array.shift());
            } else {
                rightArray.push(array.shift());
            }
        }
        // Regresamos la unión de los temporales y el pivote 
        return array.concat(
            quickSort(leftArray), //Se ordenan ambos arreglos
            piv, //debe ser el punto medio
            quickSort(rightArray)); 
    }
}

Esta es una versión en python3 también, con algunas leves modificaciones.

def quick_sort(lista):
    """ Ordena la lista de forma recursiva.
        Pre: los elementos de la lista deben ser comparables.
        Devuelve: una nueva lista con los elementos ordenados. """

    # Caso base
    if len(lista) < 2:
        return lista
    # Caso recursivo
    menores, medio, mayores = _partition(lista)
    return quick_sort(menores) + medio + quick_sort(mayores)


def _partition(lista):
    """ Pre: lista no vacía.
        Devuelve: tres listas: menores, medio y mayores. """

    pivote = lista[0]
    menores = []
    mayores = []
    for x in range(1, len(lista)):
        if lista[x] < pivote:
            menores.append(lista[x])
        else:
            mayores.append(lista[x])
    return menores, [pivote], mayores


if __name__ == "__main__":
    lista_desordenada = [3 ,94 ,86 ,82 ,90,10 ,87 ,36 ,61 ,8,17 ,15 ,22 ,10,23]
    lista_ordenada =  []
        
    for i in quick_sort(lista_desordenada):
        lista_ordenada.append(i)
    
    print(f'La lista inicial es: \n {lista_desordenada}')
    print(f'La lista ordenada es: \n {lista_ordenada}')

Alguien sabe que debo añadir para que al momento de imprimir el array me aparezca en fila y no en columna para Python 3 ? En el codigo de Ricardo con solo añadir la coma al final del print funciona, pero solo para la version 2.7(el IDE online que se usa corre en 2.7).

Mi implementacion en Go Lang

package main

import (
	"fmt"
	"math/rand"
)

func pivot(arr []int, low int, high int ) int{
	i := low-1
	pivot := arr[high]

	for j := low; j < high ; j++ {
		if arr[j] <= pivot{
			i++
			arr[i], arr[j] = arr[j], arr[i]
		}
	}
	arr[i + 1], arr[high] = arr[high], arr[i + 1]
	return i + 1
}

func quickSort(arr []int, low int, high int)  {
	if low < high{
		pv := pivot(arr, low, high)
		quickSort(arr, low, pv - 1)
		quickSort(arr, pv + 1, high)
	}
}

func fillArray(length int) []int {
	var s []int
	i:=0
	for i < length{
		i++
		s= append(s, rand.Intn(100))
	}
	return s
}


func main() {
	array := fillArray(5)
	quickSort(array, 0 , len(array)-1)
	for _, i :=range array{fmt.Println(i)}
}

Codigo en C#

using System;

namespace QuickSort
{
    class Program
    {
        static int Particion (int[] Array,int low, int high)
        {
            int j, datos;

            int i = low - 1;
            int Pivot = Array[high];

            for (j= low; j<high; j++ )
            {
                if(Array[j]<=Pivot)
                {
                    i = i + 1;
                    datos = Array[i];
                    Array[i] = Array[j];
                    Array[j] = datos;
                }
            }
            datos = Array[i + 1];
            Array[i + 1] = Array[high];
            Array[high] = datos;

            return (i + 1);
        }

        static void QuickSort (int[] Array, int low, int high)
        {
            int Pi = 0;
            if (low < high)
            {
                Pi = Particion(Array, low, high);
                QuickSort(Array, low, Pi - 1);
                QuickSort(Array, Pi + 1, high);
            }

        }


        static void Main(string[] args)
        {
            Random Rnd = new Random();//Generador de numeros al azar para ordenar
            Random V = new Random();
            int T = V.Next(50, 201); //Tamaño al azar del Array
            int[] Array = new int[T];
            int n = Array.Length; //Largo del array
            int i;

            for (int x= 0; x<Array.Length; ++x)
            {
                Array[x] = Rnd.Next(0, 101);
            }

            foreach (int Watch in Array)
            {
                Console.WriteLine(Watch);
            }
            Console.WriteLine("El tamaño del array es: " + n);
            Console.WriteLine("\n");
            Console.WriteLine("Ordenando Array");
            QuickSort(Array, 0, n - 1);

            foreach (int watch in Array)
            {
                Console.WriteLine(watch);
            }

            Console.WriteLine("Fin del ordenamiento");
                               
        }
    }
}

Buenas tardes, alguien sabe porque en la consola me sale este error (Segmentation fault (core dumped)), y alguien sabe como lo puedo solucionar? ya investigue pero no pude solucionar nada. Agradezco cualquier ayuda. Gracias.

import java.text.DecimalFormat;
import java.text.Format;

public class main {
	public static int particion(double [] arr, int low, int high) {
		int i = (low-1);
		double pivot = arr[high];
		
		for (int j = low; j < high; j++) {
			if(arr[j]<=pivot) {
				i=i+1;
				double tem = arr[i];
				arr[i]=arr[j];
				arr[j]=tem;
			}
		}
		double tem = arr[i+1];
		arr[i+1]=arr[high];
		arr[high]=tem;
		return i+1;
	}
	
	public static void quickSort (double [] arr, int low, int high) {
		if (low < high) {
			int partIndex = particion(arr, low, high);
			quickSort(arr, low, partIndex-1);
			quickSort(arr, partIndex+1, high);
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		DecimalFormat df = new DecimalFormat("#");
		double [] arr = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};
		quickSort(arr, 0, arr.length-1);
		System.out.println("Arreglo Ordenado: ");
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if(i<arr.length-1) {
				
				System.out.print(df.format(arr[i])+", ");
			}else {
				System.out.print(df.format(arr[i]));
			}
		}
		System.out.print("]");
	}
	
}

Yo se que este no es un curso de Python, pero deberian ponerse un poco mas de acuerdo cuando toquen lenguajes de otros cursos, por ej. en el curso de Python con Aroesti el siempre indica o sugiere definir el main de la siguiente forma: if name== ‘main’: y aqui @CelisMX dice otra cosa.

Que mal curso, en la ruta que estoy siguiendo (Fundamentos de programación) se encuentra en la parte “basica” al igual que el curso de C, pero en ambos pareciera que necesitas saber programar desde antes de hacer estos cursos.

# QuickSort Algorithm
# 1. Dividir el data set
# 2. Recursivamente orderar cada mitad

def particion( arr, low, high ):
    i = ( low - 1 )
    pivot = arr[high]

    # Por cada elemento del array
    for j in range( low, high ):
        # Si el elementos es menor al pivote
        # Mandarlo al lado izquiero (sorted)
        if arr[j] <= pivot:
            #Track de hasta donde van sorteados
            i += 1

            #Swap del siguiente que no lo estaba con el que encontro menor
            arr[i], arr[j] = arr[j], arr[i]

    # Aqui debe de ir el pivote
    i += 1

    #Swap del pivote con el punto donde debe estar (se declara sorteado)
    arr[i], arr[high] = arr[high], arr[i]

    #Regresar donde quedo el pivote ordenado
    return i


def quickSort( arr, low, high ):
    if low < high:
        pi = particion( arr, low, high )

        # Ordenar lado izq
        quickSort( arr, low, pi - 1)

        # Ordenar lado derecho
        quickSort( arr, pi + 1, high )

def main():
    arr = [ 1992, 1990, 10, 200, 1, -10, 5 ]
    n = len(arr)
    quickSort(arr, 0, ( n - 1 ) )

    print("Array ordenado: ")
    for i in arr:
        print(i, end = ", ")

if __name__ == '__main__':
    main()

Hola Platzeritos, a ver si me pueden ayudar, lo que me pasa es que logro entender el código por una parte y por otra logro entender el cómo funciona el algoritmo, pero me está costando entenderlos al mismo tiempo, es decir hacer el enlace entre la forma “visual” del algoritmo y su codigo, les agradezco de antemano todas sus sugerencias 😄

Aqui esta mi Aporte en C
la verdad es que me costo demasiado, por que entre intentar comparar python con C, si cambian varias cosas, pero es cuestion de ver que show.

Por otra parte comenta que ya dominamos la funcion swap.
pero la verdad yo no se de que habla cuando menciona swap no recuerdo verlo visto en este curso.

Por lo que me costo trabajo investigar por mi cuenta, no esta mal, pero no es bueno decir que lo dominamos, para aquellos que apenas van por el camino del JEDI xD.

Bueno entre enojos y mas les dejo mi aporte, espero que ayude a alguien.

Posdata:
No esta mal que el curso lo den con varios lenguajes pero, siendo honestos si inicias con un lenguaje y cambias en un curso u otro, al menos ayudenos en las bases o denos mayor idea de como hacer la misma logica con otro lenguaje.
ya sea recomendarnos a investigar que es la funcion swap, o CharTo
o substring, etc

#include<stdio.h>
#include<iostream>
using namespace std;
void swap(int* a, int* b) 
{ 
    int t = *a; 
    *a = *b; 
    *b = t; 
}
int particion (int array[], int low, int high)
{
	int pivot = array[high];// crea nuevo array que contendra todo lo almacenado en el array asignado a pivot
	int i = (low - 1);//indice del elemento mas pequeno
	for(int j=low; j <= high- 1; j++)
	{
		if(array[j] < pivot)//si el valor actual es mayor al pivote 
		//aqui es donde separamos los lados
		{
			i++;
			//array[i], array[j] = array [j], array[i];
			swap(&array[i], &array[j]);
			//incrementamosen uno y lo almacenamos en el array
			//array i va ser igual al array j y checamos ambas posiciones
		}	
	}
	//array[i+1], array[high] = array[high], array[i+1];
	swap(&array[i+1], &array[high]);
	return (i+1);
}
void quickSort(int array[], int low, int high)
{
	if(low < high)
	{
		//creamos el indice donde apunta la parte donde se genera la particion
		int indexDivider = particion(array, low, high);	//aqui hacemos el swaping es decir, vamos moviendo los datos de lugar mediante recursividad
		quickSort(array, low,indexDivider - 1);//ordemos los datos de la mitad a los mas pequenos
		quickSort(array, indexDivider + 1, high);//ordenar los datos de la mitad mas uno a los mayores
	}	
}

void printArray(int array[], int n) 
{ 
    int i; 
   for (i=0; i< n; i++)
		printf(" %d ", array[i]);
    printf("|"); 
}

int main()
{
	int i;
	int array [] = {1992,1990,10, 5,6,100,0,1, 10};
	int n = sizeof(array)/sizeof(array[0]);
	quickSort(array, 0, n-1);
	printf("Array ya ordenado: ");
	printArray(array, n);
	return 0;
}```

Versión en JavaScript

//Divide the dataset
//Pivot point to compare
//Order each half of the array with recursion

const quickSort = (arr) =>{
    //Evaluate if the array is empty
    if(arr.length < 1){
        return [];
    }

    let left = [];
    let right = [];
    let pivot = arr[0];
    
    //Start in 1 because the pivot is the first element
    for(let i = 1; i < arr.length; i++){
        if(arr[i] < pivot){
            left.push(arr[i]);
        }else{
            right.push(arr[i]);
        }
    }

    //We need a empty array because the first element that we are going to concatenate is an array
    return [].concat(quickSort(left), pivot, quickSort(right));
}

console.log(quickSort([5, -2, 0, 1, 10, 8, -9]))

En C (El papa de los pollitos)

#include<stdio.h> 

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

void cambiar_posicion(int *n1, int *n2) 
{ 
    int temp =*n1;
    *n1 = *n2;
    *n2 = temp;
} 
  
int particion (int arr[], int low, int high) 
{ 
    int i = (low - 1);  
    int pivot = arr[high];    //Pivot 
    
  
    for (int j = low; j <= high- 1; j++) 
    { 
        if (arr[j] <= pivot) 
        { 
            i++;     
            cambiar_posicion(&arr[i], &arr[j]); 
        } 
    } 
    cambiar_posicion(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
  
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        int pi = particion(arr, low, high);
        quickSort(arr, low, pi - 1); 
        quickSort(arr, pi + 1, high); 
    } 
} 
  
void printArray(int arr[], int n) 
{ 
    int i; 
    for (i=0; i < n; i++) 
        printf("%d ", arr[i]); 
    printf; 
} 
  
int main(int argc, char const *argv[]) 
{ 
    int arr[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};
    int n = sizeof(arr)/sizeof(arr[0]);  
    quickSort(arr, 0, n-1); 
    printf; 
    printArray(arr, n); 
    printf("\n");
    return0; 
} ```

No se otro lenguaje solo que JavaScript :c y casi no me gusta usarlo

Mi conclusión del funcionamiento interno de quikSort

Apectos a tomar

• El tamaño de array siempre será el mismo, pero solo se trabaja con partes de esta

• No se trabajará primero por la parte de la derecha y luego de la izquierda, se harán ambas simultáneamente

• Nosotros le damos los valores la primera vez a quickSort pero partition le dará los parámetros las demás veces

• A pesar de que pasamos el array completo cada vez que llamamos partition solo usamos una parte cada vez menor

Condiciones para cambiar de posición un número:

• i, j deben de tener valores diferentes

• high debe de ser mayor que i al menos por dos

Acciones que podrían ocurrir

1. Ningún elemento cambia de lugar: Esto sucede cuando el número del extremo derecho es el mayor de toda la lista por lo tanto ya no se volverá a incluir para trabajar con él (aunque se conserva en el array) haciendo más chica la parte de la lista a compararar. Esto ocurre gracias a que siempre se entre dentro del if haciendo que i y j aumenten su valor al mismo tiempo y que high se mayor que i solo por uno

2. Solo los extremos cambian de lugar: Esto ocurre cuando pivot es el número menor de la parte que se está comparando, haciendo que i apunte al inicio de la parte trabajada y high apunte al final intercambiando lugar en esta línea

arr[i+1], arr[high] =arr[high],arr[i+1] 

1. Hay varios cambios de lugares: Esto es lo que normalmente debe de suceder y es un proceso que prepara la lista para que ocurra uno de los dos eventos anteriores

**Nota:**En la opción 1 y 2 se achicara el area del array en el que se trabaja

Esto fue a lo que llegue después de algo de tiempo analizando lo que ocurría dentro de quickSort con print y diferentes valores, si hay algo mal me lo podría comentar para corregirlo y entenderlo mejor muchas gracias

Hola Compañeros. Entiendo que la siguiente línea del código intercambia los valores almacenados en el array en las posiciones i y j:

arr[i], arr[j] = arr[j], arr[i]

Sin embargo, hice una prueba a mano y luego mediante el código imprimiendo los valores de las variables i y j, y me resulta que es el mismo !. Lo probé con el siguiente array de datos:

{10, 7, 30, 20}

En este caso:

Recibimos low en 0 y high en: 3
arr[0] vale 10 y pivot vale 20

Por lo cual se cumple la condición arr[0] <= pivot, entonces i que inicialmente valía -1 ahora vale 0 luego del incremento en 1 y cómo estamos en el primer ciclo del for, j también vale 0.

Mi pregunta es, si lo anterior es correcto, ¿porque intercambio el valor de la misma posición? SI no es correcto este análisis, aprecio me ayuden haciéndomelo saber.

Ejercicio en clase:

Algoritmo QuickSort en Lenguaje C

No que hice mal pero no funciona el codigo

def particion(arr, low, high):
i =(low-1)
pivot = arr[high]

for j in range(low, high):
if arr[j]<= pivot:
i = i+1
arr[i, arr[j]] = arr[j], arr[i]

arr[i+1], arr[high] = arr[high], arr[i+1]
return(i+1)

def quickSort(arr,low, high):
if low < high:
pi = particion(arr,low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)

arr = [1992, 1990, 10, 5, 6, 100, 0, 1, -10]
n = len(arr)
quickSort(arr, 0, n-1)
print(“Array ordenado:”)
for i in range(n):
print("%d" %arr[i]),```

El ejercicio de la clase

Implementación en C:

#include <stdio.h>

void swapValues(int *previous1, int *previous2)
{
  int buffer = *previous1;
  *previous1 = *previous2;
  *previous2 = buffer;
}

int partition(int arr[], int low, int high)
{
  int i = (low - 1); //index for smaller element
  int pivot = arr[high];
  int j;

  for (j = low; j < high; j++)
  {
    if (arr[j] <= pivot)
    {
      i++;
      swapValues(&arr[i], &arr[j]);
    }
  }
  swapValues(&arr[i+1], &arr[high]);
  return (i + 1);
}

void quickSort (int arr[], int low, int high)
{
  if(low < high)
  {
    int pi = partition(arr, low, high); //partition index
    quickSort(arr, low, pi-1);
    quickSort(arr, pi+1, high);
  }
}

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

int main(int argc, char const *argv[]) {
  int arr[] = {10, 7, 8, 9, 1, 5};
  int n = sizeof(arr)/sizeof(arr[0]);

  quickSort(arr, 0, n-1);

  printf("Sorted array is: \n");
  printArray(arr, n);

  return 0;
}

Reto completado!!!

Creo que el profesor y yo seriamos buenos amigos tenemos en común los mismos gustos en lenguajes XD bien aquí mi código C andaba un poco desganado así que solo hice el reto sin agregados ni cosas locas (-.-)
![](

#include <stdio.h>

void intercambia(int *a, int *b){
    int c = *a;
    *a = *b;
    *b = c;}
int particion(int arreglo[], int bajo, int alto){
    int id = bajo -1;
    int pivote = arreglo[alto];
    int i;
    for(i = bajo; i <alto; ++i){
        if(arreglo[i] <= pivote){
            ++id;
            intercambia(&arreglo[id], &arreglo[i]);}}
    intercambia(&arreglo[id + 1],&arreglo[alto]);
    return id + 1;}

void quick_sort(int arreglo[], int bajo, int alto){
    if(bajo < alto){
        int Pindex = particion(arreglo, bajo, alto);
        quick_sort(arreglo, bajo, Pindex -1);
        quick_sort(arreglo,Pindex +1, alto);}}


int main(void)
{
    int arreglo[9] = {1992,1990,10,5,6,100,0,1,-10};
    int n = sizeof(arreglo)/sizeof(int);
    quick_sort(arreglo,0, n - 1);
    int i;
    for(i = 0; i < n; ++i)
        printf(" %d ",arreglo[i]);
    printf("\n");
    return 0;
}```

En python :
![](

def particion(arreglo, min, max):
    i = min - 1
    pivote = arreglo[max]

    for j in range(min, max):
        if arreglo[j] <= pivote:
            i += 1
            arreglo[i], arreglo[j] = arreglo[j], arreglo[i]

    arreglo[i + 1], arreglo[max] =  arreglo[max], arreglo[i + 1]
    return i + 1

def quick_sort(arreglo, min, max):
    if min < max:
        Pindex = particion(arreglo,min, max)
        quick_sort(arreglo, min, Pindex - 1)
        quick_sort(arreglo, Pindex + 1, max)

if __name__ == "__main__":

    arreglo = [1992,1990,10,5,6,100,0,1,-10]
    n = len(arreglo)
    quick_sort(arreglo, 0, n-1)
    print("el arreglo ordenado")
    for i in arreglo:
        print("{} |".format(i),end = " "),

En C++
![](

#include <iostream>
#include <vector>

using namespace  std;

template<typename T>void intercambia(T &a, T &b){
    T c = a;
    a = b;
    b = c;}

template<typename T> vector<T> &operator <<(vector<T> &v, T valor){
    v.push_back(valor);
    return v;}

template<typename T>ostream &operator<<(ostream &o,const vector<T> &v){
    typename vector<T>::const_iterator i;
    for(i = v.begin(); i != v.end(); ++i)
        o << *i <<" ";
    return o;}

int particion(vector<int> &v, int bajo, int alto){
    int id = bajo - 1;
    int pivote = v[alto];
    for(int j = bajo; j < alto; ++j){
        if(v[j] <= pivote){
            ++id;
            intercambia(v[id],v[j]);}}

    intercambia(v[id + 1],v[alto]);
    return id + 1;}

void Quick_sort(vector<int> &v, int bajo, int alto){
    if (bajo < alto){
        int Pindex = particion(v,bajo,alto);
        Quick_sort(v,bajo,Pindex - 1);
        Quick_sort(v,Pindex + 1, alto);
    }}

int main(void)
{
    vector<int>arreglo;
    arreglo<<1992<<1990<<10<<5<<6<<100<<0<<1<<-10;
    Quick_sort(arreglo,0,arreglo.size() - 1);
    cout<<arreglo<<endl;
    return 0;
}

const defaultSortingAlgorithm = (a, b) => {
    if (a < b) {
        return -1;
    }
    if (a > b) {
        return 1;
    }
    return 0;
};

const quickSort = ( unsortedArray, sortingAlgorithm = defaultSortingAlgorithm ) => {
    const sortedArray = [...unsortedArray];

    const swapArrayElements = (arrayToSwap, i, j) => {
        const a = arrayToSwap[i];
        arrayToSwap[i] = arrayToSwap[j];
        arrayToSwap[j] = a;
    };

    const partition = (arrayToDivide, start, end) => {
        const pivot = arrayToDivide[end];
        let splitIndex = start;
        for (let j = start; j <= end - 1; j++) {
            const sortValue = sortingAlgorithm(arrayToDivide[j], pivot);
            if (sortValue === -1) {
                swapArrayElements(arrayToDivide, splitIndex, j);
                splitIndex++;
            }
        }
        swapArrayElements(arrayToDivide, splitIndex, end);
        return splitIndex;
    };

    const recursiveSort = (arraytoSort, start, end) => {
        if (start < end) {
            const pivotPosition = partition(arraytoSort, start, end);
            recursiveSort(arraytoSort, start, pivotPosition - 1);
            recursiveSort(arraytoSort, pivotPosition + 1, end);
        }
    };

    recursiveSort(sortedArray, 0, unsortedArray.length - 1);
    return sortedArray;
};

const testA = [1, -32, -4, -46, -35, 76, -57, 56, 7, -87, -9, 8, 6, ,59, -85, -9, -6, -35, -4, 353, -4, 13, 2, -42, -1];
const testASorted = quickSort(testA);
console.log(testASorted);

const testB = [-3, -2, -1, 0, 1, 2, 3];
const testBSorted = quickSort(testB);
console.log(testBSorted);

const testC = [3, 2, 1, 0, -1, -2, -3];
const testCSorted = quickSort(testC);
console.log(testCSorted);

const testD = [
    {
        id: 9,
        name: "Task 9"
    },
    {
        id: -1,
        name: "Task -1"
    },
    {
        id: 5,
        name: "Task 5"
    },
    {
        id: 3,
        name: "Task 3"
    },
    {
        id: -10,
        name: "Task -10"
    }
];
const testDSorted = quickSort(testD, (a, b) => {
    if (a.id < b.id) {
        return -1;
    }
    if (a.id > b.id) {
        return 1;
    }
    return 0;
});
console.log(testDSorted);```

Como no entendía muy bien me puse a investigar y me tarde días entendiendo el algoritmo en c, les dejo tal cual lo encontré en una pagina y asi fui resolviendo

// reto quickfort en c

#include<stdio.h>

/* Esta función toma el último elemento como pivote, lugares
el elemento pivote en su posición correcta en orden
matriz y coloca todos los más pequeños (más pequeños que el pivote)
a la izquierda del pivote y todos los elementos mayores a la derecha
de pivote */

// Una función de utilidad para intercambiar dos elementos
void swap(inta,intb){
int t=*a;
*a=*b;
*b=t;

}

int particion(int arr[], int low, int high){

int pivot = arr[high];// pivote
int i = (low-1);// Índice de elemento más pequeño

for(int j=low ; j<=high-1; j++){
    if(arr[j]<pivot){
       i++;
       swap(&arr[i], &arr[j]);
    }
}
swap(&arr[i+1],&arr[high]);
return (i+1);

}

/* La función principal que implementa QuickSort
arr [] -> Matriz para ordenar,
bajo -> Índice inicial,
alto -> índice final */

void quicksort(int arr[], int low, int high){

if(low<high){

/* pi es el índice de partición, arr [p] es ahora
en el lugar correcto */

        int pi = particion(arr, low, high);

     //Ordenar elementos por separado antes
    // partición y después de la partición
        quicksort(arr, low, pi-1);
        quicksort(arr, pi+1, high);
}

}

void print_arr(int arr[], int size){
int i;

for(i=0; i<size; i++)
    printf("%d \t", arr[i]);
    printf("\n");

}

int main(){
int arr[]={10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);

    quicksort(arr, 0, n-1);

printf("matrix ordenada \n");
    print_arr(arr, n);

    return 0;

}

en c

En C#

using System;


namespace QuickSort
{
    class Program
    {
        private static void Quick_Sort(int[] arr, int Low, int high)
        {
            if (Low < high)
            {
                int pivot = Partition(arr, Low, high);

                if (pivot > 1)
                {
                    Quick_Sort(arr, Low, pivot - 1);
                }
                if (pivot + 1 < high)
                {
                    Quick_Sort(arr, pivot + 1, high);
                }
            }

        }

        private static int Partition(int[] arr, int low, int high)
        {
            int pivot = arr[low];
            while (true)
            {

                while (arr[low] < pivot)
                {
                    low++;
                }

                while (arr[high] > pivot)
                {
                    high--;
                }

                if (low < high)
                {
                    if (arr[low] == arr[high]) return high;
                    //por si hay duplicados
                    int temp = arr[low];
                    arr[low] = arr[high];
                    arr[high] = temp;


                }
                else
                {
                    return high;
                }
            }
        }
        private static void imprimirArreglo(int[] arr, string texto)
        {
            Console.WriteLine(texto);
            foreach (var item in arr)
            {
                Console.Write(" " + item);
            }
            Console.WriteLine();
        }
        static void Main(string[] args)
        {
            int[] arr = new int[] { 1992, 1990, 10, 5, 6, 100, 0, 1, -10 };           
            imprimirArreglo(arr, "Arreglo Original: ");
            Quick_Sort(arr, 0, arr.Length - 1);
            Console.WriteLine();
            imprimirArreglo(arr, "Arreglo Ordenado : ");
        }
    }
}

Implementación en C#

using System;
using Curso_Basico_Algoritmos.ejercicios;

namespace Curso_Basico_Algoritmos
{
    class Program
    {
        static void Main(string[] args)
        {
            // var queue = new Queue();
            // queue.iniciar();
            // bubble_sort.inicializar();
            // insertion_sort.inicializar();
            // Reto_uno.iniciar();
            // Recursividad.Iniciar();
            QuickSort.iniciar();
        }
    }
}

using System;
using static System.Console;

/* 
    Necesitamos dividir nuestro dataset
    Necesitamis un punto povotal 
    Recursivamente ordenar cada mitad de mi array
*/
namespace Curso_Basico_Algoritmos.ejercicios
{
    public static class QuickSort
    {
        public static void iniciar(){
            int[] arr = new int[]{-10,7,5,-5,-3,8,1,6,-2,10,-6,3,-8,-7,-1};
            // int[] arr = new int[]{1991,1990,10,5,6,0,1,-10};
            int n = arr.Length;
            quickSort (arr, 0, n-1);
            Write("Array Ordenado:");
            printArray(arr);
        }
        static void printArray(int[] arr)
        {
          string answare = "";
          int cnt = 0;
          foreach (var item in arr)
          {
            if ( cnt == 0){
              answare = string.Format("{0}",item);
              cnt++;
            }else{
              answare = answare + "," + item.ToString();
            }
          }
          Console.Write(answare);
        }
        static int particion(int[] arr, int low, int hight){
            //tenemos en consideración que vamos a establecer una separación de números entre mayores y menores
            int i = (low-1);
            int pivot = arr[hight];

            /* foreach (var j in arr)
            {
                if (arr[j] <= pivot){
                    i++;
                    (arr[i], arr[j]) = (arr[j], arr[i]);
                }
            } */
            for (int j = low; j < hight; j++)
            {
                if (arr[j] <= pivot){
                    i++;
                    (arr[i], arr[j]) = (arr[j], arr[i]);
                }
            }
            
            (arr[i+1], arr[hight]) = (arr[hight], arr[i+1]);
            
            return (i+1);
        }

        //Índice de la partición 
        static void quickSort(int[] arr, int low, int hight){
            if(low < hight){
                int pi = particion(arr, low, hight);
                //Iniciar a hacer los ordenamientos
                //iniciamos desde el cero a nuestro pi (partition index)
                quickSort(arr, low, pi-1);
                //organizamos la otra mitad
                quickSort(arr, pi+1, hight);
            }
        }
    }
}

✌😃

En C++.

#include<iostream>
using namespace std;

int partition(int arr[],int  low,int high)
{
	int i=(low-1), pivot = arr[high];
	
	int temp;
	for(int j=low;j<high;j++)
	{
		if(arr[j]<=pivot)
		{
			i++;
			temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
		}
	}
	temp=arr[i+1];
	arr[i+1]=arr[high];
	arr[high]=temp;
	
	return i+1;
}

void quickSort(int arr[],int low,int high)
{
	int pi;
     if(low<high)
    {
     	pi=partition(arr,low,high);
 	    quickSort(arr, low, pi-1);
     	quickSort(arr, pi+1, high);
    }
 	
}

int arr[]={1992,23,344.-56,-454,334,4354,5,23};

int main()
{
	int n=sizeof(arr)/sizeof(arr[0]);
	quickSort(arr,0,n-1);
	cout<<"Arreglo Ordenado"<<endl;
	
	for(int i=0;i<n;i++)
	  cout<<arr[i]<<endl;
	return 0;
}

![](![quickSort.png](https://static.platzi.com/media/user_upload/quickSort-30dc589c-0bb0-49c8-970f-e8a94e62c9f4.jpg)`

Quiero arrastrar hasta esta clase el vídeo que compartió @Johan52752 con la única explicación que me ayudó a entender el QuickSort: https://www.youtube.com/watch?v=PgBzjlCcFvc

También les comparto un par más:

1. QuickSort explicado con vasos, teniendo en cuenta que la función de partición es realmente la que hace el trabajo (a través de QuickSort, recursivamente.
2. Una comparación entre MergeSort y QuickSort.

¡Saludos!

se me hizo un poco difícil entenderlo, pero aquí lo implemente en java

public class QuickSort {

	public int particion(int[] array, int low, int higth) {

		int pivot = array[higth];
		int i = low - 1;
		int aux, j, aux2;

		for ( j = low; j < higth; j++) {
			if (array[j] <= pivot) {
				i++;
				aux = array[i];
				array[i] = array[j];
				array[j] = aux;
			}
		}
		aux2 = i+1;
	 	aux = array[aux2];
		array[aux2] = array[higth];
	 	array[higth]= aux;
		
		
		return aux2;
	
	}

	public void quick_sort(int[] array, int low, int higth) {
		if (low < higth) {
			int part = particion(array, low, higth);
			// System.out.println(part);
			quick_sort(array, low, part - 1);
			quick_sort(array, part+1, higth);
		}

	}
	
	public void print (int[]array) {
		for (int z = 0; z < array.length; z++) {
			System.out.println(array[z] + " ");
		}
	}

}

////////////////////////////////
public class Main {
	
	public static void main(String[] args) {
		
		int []array = {10,7,8,9,1,5};
		
		QuickSort qs = new QuickSort();
		
		qs.print(array);
		qs.quick_sort(array, 0, array.length-1);
		System.out.println("ordenado");
		qs.print(array);
	}

}

#include <iostream>
using namespace std;

int arr[]={-100,-45,-5667,67,89,999,1000,23,45,67,78,1,2,3,4,5,6,7,8,9,0,112};

int particion(int arr[],int low,int high)
{
  	int i, pivot,aux;
  	i=low-1;
  	pivot=arr[high];
  	
  	for(int j=low;j<high;j++)
  	{
  	
  	   if(arr[j]<=pivot)
	  {
	  	  i++;
	  	  aux=arr[i];
	  	  arr[i]=arr[j];
	  	  arr[j]=aux;
	   } 
  		
	}
     aux=arr[i+1];
     arr[i+1]=arr[high];
     arr[high]=aux;
     
     return i+1;
}

int quickSort(int arr[],int low,int high)
{
	int pi;
	if(low<high)
	{
		pi=particion(arr,low,high);
		quickSort(arr,low,pi-1);
		quickSort(arr,pi+1,high);
	}
	return 0;
}



int main()
{
	int n;
	n=sizeof(arr)/sizeof(arr[0]);
	quickSort(arr,0,n-1);
	
	for(int i=0;i<n;i++)
	   cout<<arr[i]<<" ";
	
	return 0;
}

En c++

Aqui esta el codigo en c

#include <stdio.h>

int partition(int array[], int low, int high)
{
    int i = low - 1;
    int j;
    int pivot = array[high];
    for (j = low; j < high; j++)
    {
        if (pivot >= array[j])
        {
            i++;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp2 = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp2;
    return i + 1;
}
void quickSort(int array[], int low, int high)
{
    if (low < high)
    {
        int pp = partition(array, low, high);
        quickSort(array, low, pp - 1);
        quickSort(array, pp + 1, high);
    }
}
void print_quick_sort(int array[], int n)
{
    int i;
    printf("El resultado es \n");
    for (i = 0; i < n; i++)
    {
        printf("%d, ", array[i]);
    }
    printf("\n");
}
int main(int argc, char const *argv[])
{
    int array[] = {31, 22, 33, 44, 25, 152};
    int n = sizeof(array) / sizeof(array[0]);
    quickSort(array, 0, n - 1);
    print_quick_sort(array, n);
    return 0;
}

en C

#include <stdio.h>

int Particion(int Numeros[], int Low, int High)
{
    int i = Low - 1;
    int pivot = Numeros[High];
    int temp;

    for(int j = Low; j < High; j++)
    {
        if(Numeros[j] <= pivot)
        {
            i = i + 1;
            temp = Numeros[i];
            Numeros[i] = Numeros[j];
            Numeros[j] = temp;
        }
    }

    temp = Numeros[i + 1];
    Numeros[i + 1] = Numeros[High];
    Numeros[High] = temp;

    return (i + 1);
}

void QuickSort(int Numeros[], int Low, int High)
{
    if(Low < High)
    {
        int Pivote = Particion(Numeros, Low, High);

        Pivote = Particion(Numeros, Low, High);

        QuickSort(Numeros, Low, Pivote - 1);

        QuickSort(Numeros, Pivote + 1, High);
    }
}

int main()
{
    int Number[] = {1992, 1990, 10, 5, 6, 100, 0, 1, -10};

    int n = sizeof(Number)/sizeof(int);

    QuickSort(Number, 0, n - 1);

    for(int i = 0; i < n; i++)
    {
        printf("%d ,", Number[i]);
    }

    return 0;
}