fork download
copy 
  1. def fn():
  2.     def part(lo,hi):
  3.         j = lo - 1
  4.         piv = arr[hi]
  5.         for i in range(lo, hi+1):
  6.             if arr[i]<=piv:
  7.                 j+=1
  8.                 arr[j],arr[i]=arr[i],arr[j]
  9.         return j
  10.  
  11.     def quicksort(lo,hi):
  12.         piv = part(lo,hi)
  13.         if lo < piv - 1:
  14.             quicksort(lo, piv - 1)
  15.         if piv + 1 < hi:
  16.             quicksort(piv + 1, hi)
  17.  
  18.     def select(k,lo,hi):
  19.         piv = part(lo,hi)
  20.         if piv == k-1:
  21.             return arr[piv]
  22.         elif k-1>piv:
  23.             return select(k,piv+1,hi)
  24.         return select(k,lo,piv-1)
  25.  
  26.     arr = [14,4,5,21,3,33,23]
  27.     n = len(arr)
  28.     print(arr)
  29.     for i in range(n):
  30.         print("%d => %d"%(i+1,select(i+1,0,n-1)))
  31.     quicksort(0, n-1)
  32.     print(arr)
  33. fn()
  34.  
Success #stdin #stdout 0.04s 9616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[14, 4, 5, 21, 3, 33, 23]
1 => 3
2 => 4
3 => 5
4 => 14
5 => 21
6 => 23
7 => 33
[3, 4, 5, 14, 21, 23, 33]
https://ideone.com/eGw7ga
Quicksort with partitions and select K min
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!