Quickselect algorithm: Difference between revisions
Content added Content deleted
No edit summary |
(Quickselect algorithm en FreeBASIC) |
||
| Line 1,212: | Line 1,212: | ||
Given an intention to make many calls on FINDELEMENT for the same array, the array might as well be fully sorted first by a routine specialising in that. Otherwise, if say going for quartiles, it would be better to start with the median and work out so as to have a better chance of avoiding unfortunate "pivot" values. |
Given an intention to make many calls on FINDELEMENT for the same array, the array might as well be fully sorted first by a routine specialising in that. Otherwise, if say going for quartiles, it would be better to start with the median and work out so as to have a better chance of avoiding unfortunate "pivot" values. |
||
=={{header|FreeBASIC}}== |
|||
Una implementación directa del pseudocódigo de Wikipedia. |
|||
<lang freebasic> |
|||
Dim Shared As Long array(9), pivote |
|||
Function QuickPartition (array() As Long, izda As Long, dcha As Long, pivote As Long) As Long |
|||
Dim As Long pivotValue = array(pivote) |
|||
Swap array(pivote), array(dcha) |
|||
Dim As Long indice = izda |
|||
For i As Long = izda To dcha-1 |
|||
If array(i) < pivotValue Then |
|||
Swap array(indice), array(i) |
|||
indice += 1 |
|||
End If |
|||
Next i |
|||
Swap array(dcha), array(indice) |
|||
Return indice |
|||
End Function |
|||
Function QuickSelect(array() As Long, izda As Long, dcha As Long, k As Long) As Long |
|||
Do |
|||
If izda = dcha Then Return array(izda) : End If |
|||
pivote = izda |
|||
pivote = QuickPartition(array(), izda, dcha, pivote) |
|||
Select Case k |
|||
Case pivote |
|||
Return array(k) |
|||
Case Is < pivote |
|||
dcha = pivote - 1 |
|||
Case Is > pivote |
|||
izda = pivote + 1 |
|||
End Select |
|||
Loop |
|||
End Function |
|||
Dim As Long a = Lbound(array), b = Ubound(array) |
|||
Print "Array desordenado: "; |
|||
For i As Long = a To b |
|||
Read array(i) |
|||
Print array(i); |
|||
Next i |
|||
Data 9, 8, 7, 6, 5, 0, 1, 2, 3, 4 |
|||
Print !"\n\n Array ordenado: "; |
|||
For i As Long = a To b |
|||
Print QuickSelect(array(), a, b, i); |
|||
Next i |
|||
Sleep |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
Array desordenado: 9 8 7 6 5 0 1 2 3 4 |
|||
Array ordenado: 0 1 2 3 4 5 6 7 8 9 |
|||
</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |
||