141 lines
3.5 KiB
Plaintext
141 lines
3.5 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"# Python QuickSort Algorithm"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"[5, 9, 1, 2, 4, 8, 6, 3, 7]\n",
|
|
"[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"#---------------------------------------\n",
|
|
"# Quick Sort\n",
|
|
"#---------------------------------------\n",
|
|
"def quick_sort(A):\n",
|
|
" quick_sort2(A, 0, len(A)-1)\n",
|
|
" \n",
|
|
"def quick_sort2(A, low, hi):\n",
|
|
" if hi-low < 1 and low < hi:\n",
|
|
" quick_selection(A, low, hi)\n",
|
|
" elif low < hi:\n",
|
|
" p = partition(A, low, hi)\n",
|
|
" quick_sort2(A, low, p - 1)\n",
|
|
" quick_sort2(A, p + 1, hi)\n",
|
|
" \n",
|
|
"def get_pivot(A, low, hi):\n",
|
|
" mid = (hi + low) // 2\n",
|
|
" s = sorted([A[low], A[mid], A[hi]])\n",
|
|
" if s[1] == A[low]:\n",
|
|
" return low\n",
|
|
" elif s[1] == A[mid]:\n",
|
|
" return mid\n",
|
|
" return hi\n",
|
|
" \n",
|
|
"def partition(A, low, hi):\n",
|
|
" pivotIndex = get_pivot(A, low, hi)\n",
|
|
" pivotValue = A[pivotIndex]\n",
|
|
" A[pivotIndex], A[low] = A[low], A[pivotIndex]\n",
|
|
" border = low\n",
|
|
"\n",
|
|
" for i in range(low, hi+1):\n",
|
|
" if A[i] < pivotValue:\n",
|
|
" border += 1\n",
|
|
" A[i], A[border] = A[border], A[i]\n",
|
|
" A[low], A[border] = A[border], A[low]\n",
|
|
"\n",
|
|
" return (border)\n",
|
|
" \n",
|
|
"def quick_selection(x, first, last):\n",
|
|
" for i in range (first, last):\n",
|
|
" minIndex = i\n",
|
|
" for j in range (i+1, last+1):\n",
|
|
" if x[j] < x[minIndex]:\n",
|
|
" minIndex = j\n",
|
|
" if minIndex != i:\n",
|
|
" x[i], x[minIndex] = x[minIndex], x[i]\n",
|
|
" \n",
|
|
"A = [5,9,1,2,4,8,6,3,7]\n",
|
|
"print(A)\n",
|
|
"quick_sort(A)\n",
|
|
"print(A)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"### Nice simple version written by Mr. UncleChu in comments\n",
|
|
"Slick code, but does not sort in place, so uses a lot more memory. Do not use for large lists or you'll get stackoverflow."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 5,
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"[5, 9, 1, 2, 4, 8, 6, 3, 7]\n",
|
|
"[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"def quick_sort_chu(a_list):\n",
|
|
" if len(a_list) < 2: return a_list\n",
|
|
" lesser = quick_sort([x for x in a_list[1:] if x <= a_list[0]])\n",
|
|
" bigger = quick_sort([x for x in a_list[1:] if x > a_list[0]])\n",
|
|
" return sum([lesser, [a_list[0]], bigger], [])\n",
|
|
"A = [5,9,1,2,4,8,6,3,7]\n",
|
|
"print(A)\n",
|
|
"B = quick_sort_chu(A)\n",
|
|
"print(B)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": []
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "Python 3",
|
|
"language": "python",
|
|
"name": "python3"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.7.0"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 2
|
|
}
|