ควิกซอร์ต

ควิกซอร์ต น่าจะเป็นขั้นตอนวิธีที่ใช้จริงที่เราคุ้นเคยที่สุดที่ใช้การสุ่มอย่างได้ผลดีมากๆ ขั้นตอนวิธีนี้ในแบบที่เป็นดิเทอร์มินิสติกต้องใช้เวลา O (n^2) ในการเรียงเลข n ตัว สำหรับอินพุทบางรูปแบบ เช่น อาร์เรย์ที่ถูกเรียงมาอยู่แล้ว อย่างไรก็ตาม ถ้าขั้นตอนวิธีสลับตัวในอาร์เรย์แบบสุ่มก่อนที่จะเริ่มทำงาน มันจะมีความน่าจะเป็นสูงที่จะทำงานเสร็จในเวลา O (n log n) สำหรับอินพุททุกรูปแบบ ความแตกต่างระหว่างสองแบบนี้จะมีความสำคัญมาก เมื่อเราต้องจัดเรียงข้อมูลจำนวนมากๆ

การตัดให้น้อยที่สุด

ตัวอย่างที่ซับซ้อนขึ้นกว่าอีกหน่อย คือการใช้ขั้นตอนวิธีเชิงสุ่มแก้ปัญหาทางด้านทฤษฎีกราฟ นี่คือขั้นตอนวิธีสำหรับแก้ปัญหา การตัดให้น้อยที่สุด (minimum cut)

   หาการตัดน้อยสุด (กราฟไม่มีทิศทาง G) {       ตราบใดที่ G ยังมีโหนดมากกว่า 2 โหนด ให้ทำ{           สุ่มเลือกเส้นเชื่อม (u,v) จาก G           หด (contract) เส้นเชื่อม โดยให้รักษาการมีเส้นเชื่อมหลายเส้น (multi-edge) เอาไว้           ลบลูปทั้งหมดออก       }       ให้เส้นเชื่อมที่เหลืออยู่เป็นเอาต์พุต   }

ในที่นี้ การหดเส้นเชื่อม (u,v) หมายความถึง การเพิ่มโหนดขึ้นใหม่ (ให้ชื่อ w)แล้วให้แทนทุกเส้นเชื่อม (u,x) และ (v,x) ด้วย (w,x) แล้วลบโหนด u และ vออกจาก G

ให้ n = |V[G]|สามารถแสดงได้ว่า ขั้นตอนวิธีนี้ให้ผลเป็นการตัดที่น้อยที่สุด ด้วยความน่าจะเป็นอย่างน้อย n-2ดังนั้นหากเราให้มันทำงาน n2log (n) รอบ และเลือกผลลัพธ์ที่มีค่าน้อยที่สุดเราก็จะสามารถหาการตัดที่น้อยที่สุดได้ด้วยความน่าจะเป็นสูง