Bienvenido al Curso

1

Introducci贸n al curso b谩sico de algoritmos y estructuras de datos

Introducci贸n a los algoritmos

2

驴Qu茅 entiende una computadora?

3

Lenguajes de programaci贸n

4

Estructuras de datos

5

驴Qu茅 es un algoritmo?

6

Metodolog铆a para la construcci贸n de un algoritmo

7

Variables y tipos de datos

8

User defined data types

9

Instalando Ubuntu Bash en Windows

10

Creando nuestro user defined data type

11

Abstract Data Types b谩sicos: Lists, Stacks, Queues

12

Explicaci贸n gr谩fica Data Types b谩sicos

13

Glosario de funciones para Abstract Data Types

14

Clases y objetos

15

Creando tu primera Queue: Arrays

16

Creando tu primera Queue: implementaci贸n.

17

Creando tu primera Queue: implementar la funci贸n enQueue

18

Creando tu primera Queue: implementar la funci贸n deQueue

19

Creando tu primera Queue: main code

Algoritmos de ordenamiento

20

Algoritmos de ordenamiento

21

Bubble sort

22

Bubble sort: implementaci贸n

23

Bubble sort: main code

24

Insertion sort

25

Desaf铆o: implementa un algoritmo de ordenamiento

Recursividad

26

Recursividad

27

La funci贸n Factorial, calculando el factorial recursivamente

28

Manejo de cadenas de caracteres

29

Arte: Generando arte recursivo

Divide and conquer y programaci贸n din谩mica

30

Divide and Conquer (divide y vencer谩s)

31

Qu茅 es la programaci贸n din谩mica (divide y vencer谩s v2.0)

32

MergeSort

33

Desaf铆o: Buscar el algortimo m谩s r谩pido de sort

34

Implementando QuickSort con Python

35

Implementando QuickSort con Python: main code

Algoritmos 'Greedy'

36

Qu茅 son los Greedy Algorithm

37

Ejercicio de programaci贸n greedy

38

Ejercio de programaci贸n greedy: main code

Grafos y 谩rboles

39

Grafos y sus aplicaciones

40

脕rboles

驴C贸mo comparar Algoritmos?

41

C贸mo comparar algoritmos y ritmo de crecimiento

驴Qu茅 sigue?

42

Cierre del curso y siguientes pasos

No tienes acceso a esta clase

隆Contin煤a aprendiendo! 脷nete y comienza a potenciar tu carrera

Implementando QuickSort con Python: main code

35/42
Recursos

Ya tenemos nuestras funciones definidas, en esta clase las llamaremos para probar nuestro QuickSort con Python.

Aportes 114

Preguntas 9

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad?

o inicia sesi贸n.

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 鈥減ivot=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()```

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 **鈥淪egmentation 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)

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

驴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 鈥渂asica鈥 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 鈥渧isual鈥 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(鈥淎rray 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;
}