tri rap.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val partitionne : 'a list -> 'a -> 'a list * 'a list * 'a list = <fun>\n"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec partitionne l x = match l with\n",
    "  |[]->([],[],[])\n",
    "  |u::r-> match partitionne r x with\n",
    "    |(a,b,c)-> if u<x then (u::a,b,c) else if u = x then (a,u::b,c) else (a,b,u::c) ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int list * int list * int list = ([1; 3; 3; 0; 3], [4], [8; 9])\n"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "partitionne [1;3;8;4;9;3;0;3] 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val qsort : 'a list -> 'a list = <fun>\n"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec qsort l = match l with\n",
    "|[]->[]\n",
    "|x::r -> let a,b,c=partitionne r x in (qsort a) @ (qsort b) @ [x] @(qsort c);;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int list = [0; 1; 2; 2; 3; 3; 4; 4; 9; 9]\n"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "qsort [1;4;9;3;0;2;9;4;2;3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let swap t i j = let a = t.(i) in t.(i)<-t.(j) ; t.(j)<-a ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let parti t deb fin piv = let a = t.(piv) in \n",
    "  swap t piv (fin-1) in\n",
    "  let i = ref deb in\n",
    "  for j = deb to fin-2 do\n",
    "    if t.(j)<=a then ( swap t (!i+1) j ; i:= !i+1 )\n",
    "  done ; swap t (!i) (fin-1) ; !i ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val aux : 'a array -> int -> int -> unit = <fun>\n"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let rec aux t deb fin = if deb<fin then let k = parti t 0 (Array.length t) 0  in  aux t deb k ; aux t k fin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val tri_rapide : 'a array -> unit = <fun>\n"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let tri_rapide t = aux t 0 (Array.length t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "val a : int array = [|9; 8; 7; 6; 5; 4; 3; 2; 1|]\n"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let a = [|3;8;4;4;8;3;9;3.8;;4;|]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int = 4\n"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "parti a 0 9 4 ;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "- : int array = [|1; 4; 3; 2; 5; 8; 7; 6; 9|]\n"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml 4.08.1+flambda",
   "language": "OCaml",
   "name": "ocaml-jupyter"
  },
  "language_info": {
   "codemirror_mode": "text/x-ocaml",
   "file_extension": ".ml",
   "mimetype": "text/x-ocaml",
   "name": "OCaml",
   "nbconverter_exporter": null,
   "pygments_lexer": "OCaml",
   "version": "4.08.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}