11_quick_sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 그룹을 둘러 나눠 재귀 호출 하는 방식은 병합정렬과 같지만\n",
    "# 그 그룹을 나눌 때 미리 기준과 비교해서 나눈다는 점이 다르다. 즉. 먼저 기준과 비교를 해서 그룹을 나눈 다음 각각 제귀 호출하여 합치는 방식.\n",
    "\n",
    "# 쉽게 설명한 퀵정렬 알고리즘 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 쉽게 설명한 퀵정렬 알고리즘 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "# 나혼자 일단 해봄 \n",
    "\n",
    "def quick_sort(a):\n",
    "    n = len(a)\n",
    "   \n",
    "    if n <= 1:\n",
    "        return a\n",
    "    \n",
    "    flag = a.pop(-1)\n",
    "\n",
    "    group1 = []\n",
    "    group2 = []\n",
    "    result = []\n",
    "    \n",
    "    while a:\n",
    "        if a[0] < flag:\n",
    "            group1.append(a.pop(0))\n",
    "        else:\n",
    "            group2.append(a.pop(0))\n",
    "    \n",
    "    return quick_sort(group1) +[flag] + quick_sort(group2)\n",
    "            \n",
    "\n",
    "d = [6,8,3,9,10,1,2,4,7,5]\n",
    "print(quick_sort(d))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "# 책에서 써있는것.\n",
    "\n",
    "# 입력: 리스트 a\n",
    "# 출력: 정렬된 새 리스트\n",
    "\n",
    "def quick_sort(a):\n",
    "    n = len(a)\n",
    "    # 종료 조건: 정렬할 리스트의 자료 개수가 한개 이하이면 정렬할 필요가 없음\n",
    "    if n <=1:\n",
    "        return a\n",
    "    \n",
    "    # 기준 값을 정하고 기준에 맞춰 그룹을 나누는 과정\n",
    "    pivot = a[-1] # 편의상 리스트의 마지막을 기준 값으로 정함\n",
    "    g1 = []       # 그룹 1: 기준 값보다 작은 값을 담을 리스트\n",
    "    g2 = []       # 그룹 2: 기준 값보다 큰 값을 담을 리스트\n",
    "    \n",
    "    for i in range(0, n-1):\n",
    "        if a[i] < pivot:\n",
    "            g1.append(a[i])\n",
    "        else:\n",
    "            g2.append(a[i])\n",
    "    \n",
    "    # 각 그룹 기준에 대해 제귀 호출로 퀵 정렬을 한 후 \n",
    "    # 기준 값과 합쳐 하나의 리스트로 결괏값 반환\n",
    "    return quick_sort(g1)+[pivot]+quick_sort(g2)\n",
    "\n",
    "d = [6,8,3,9,10,1,2,4,7,5]\n",
    "print(quick_sort(d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 일반적인 퀵 정렬 알고리즘\n",
    "\n",
    "# 입력된 리스트 안에서 직접 위치를 바꿔가면서 정렬하는 일반적인 퀵 정렬을만들자."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 퀵 정렬 \n",
    "# 입력: 리스트 a \n",
    "# 출력: 없음(입력으로 주어진 a가 정렬됨)\n",
    "# 리스트 a에서 어디부터 어디까지가 정렬 대상인지 범위를 지정하여 정렬하는 재귀함수 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 나혼자 한번 해봄. \n",
    "\n",
    "def quick_sort(a,start,end):\n",
    "    if end-start <= 0:\n",
    "        return\n",
    "    \n",
    "    pivot = a[end]\n",
    "    \n",
    "    insert_point = start\n",
    "    \n",
    "    \n",
    "    for index in range(start,end):\n",
    "        if a[index] < pivot:\n",
    "            a[insert_point],a[index] = a[index],a[insert_point]\n",
    "            insert_point +=1\n",
    "    \n",
    "    a[end],a[insert_point] = a[insert_point],a[end]\n",
    "\n",
    "    print(a)\n",
    "    print(insert_point)\n",
    "    \n",
    "    quick_sort(a,start,insert_point-1)\n",
    "    quick_sort(a,insert_point+1,end)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 1, 2, 4, 5, 8, 6, 9, 7, 10]\n",
      "4\n",
      "[3, 1, 2, 4, 5, 8, 6, 9, 7, 10]\n",
      "3\n",
      "[1, 2, 3, 4, 5, 8, 6, 9, 7, 10]\n",
      "1\n",
      "[1, 2, 3, 4, 5, 8, 6, 9, 7, 10]\n",
      "9\n",
      "[1, 2, 3, 4, 5, 6, 7, 9, 8, 10]\n",
      "6\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "d = [6,8,3,9,10,1,2,4,7,5]\n",
    "quick_sort(d,0,len(d)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "# 책 내용 주석과 함께 있는것.\n",
    "\n",
    "def quick_sort_sub(a,start,end):\n",
    "    # 종료조건: 정렬 대상이 한 개 이하이면 정렬할 필요가 없음\n",
    "    if end - start <=0:\n",
    "        return\n",
    "    # 기준 값을 정하고 기준 값에 맞춰 리스트 안에서 각 자료의 위치를 맞춤\n",
    "    # [기준 값보다 작은 값들, 기준값, 기준 값보다 큰 값들]\n",
    "    pivot = a[end]\n",
    "    i = start\n",
    "    \n",
    "    for j in range(start,end):\n",
    "        if a[j] <= pivot:\n",
    "            a[i],a[j] = a[j],a[i]\n",
    "            i+=1\n",
    "    a[i], a[end] = a[end],a[i]\n",
    "    #재귀 호출 부분\n",
    "    quick_sort_sub(a,start, i-1) #기준 값보다 작은 그룹을 재귀 호출로 다시 정렬 \n",
    "    quick_sort_sub(a,i+1, end) # 기준 값보다 큰 그룹을 재귀 호출로 다시 정렬\n",
    "    \n",
    "# 리스트 전체(0~len(a)-1)를 대상으로 재귀 호출 함수\n",
    "def quick_sort(a):\n",
    "    quick_sort_sub(a,0,len(a)-1)\n",
    "        \n",
    "d = [6,8,3,9,10,1,2,4,7,5]\n",
    "quick_sort(d)\n",
    "print(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "알고리즘 분석\n",
    "\n",
    "최악의 경우 선택, 삽입 정렬과 같은 O(n^2)이지만 \n",
    "평균적일 때는 병합 정렬과 같은 O(n.logn)\n",
    "\n",
    "좋은 기준을 설정할 경우는 대부분의 경우는 O(n.logn)이라함.\n",
    "\n",
    "```"
   ]
  },
  {
   "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": []
  },
  {
   "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": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}