Quicksort In-Place

Problem Link
https://www.hackerrank.com/challenges/quicksort3/problem?/isFullScreen=True

✅ Problem Summary

Lumoto Partitioning 알고리즘을 이용한 퀵소트(quicksort) 구현 문제

---

🧮 Applied Theory & Algorithm

1. Lumoto Partition Scheme

• pivot 값을 정한 후, 배열 앞에서 부터 순차적으로 탐색
• pivot보다 큰 수가 나타나면 직전의 pivot보다 작은 수와 위치를 바꾸는 방식으로 정렬
  
  그림출처:hackerrank quicksort in-place

---

📑 My Answer

• 모든 테스트 케이스 통과

# Lomuto Partitioning
def quickSort(arr, l , r):
    if l >= r or l < 0:
        return

    arr, p = partition(arr, l, r)
    quickSort(arr, l, p-1)
    quickSort(arr, p+1, r)

def partition(arr, l, r):
    i, pivot = l-1, arr[r]
    for j in range(l, r):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    i += 1
    arr[i], arr[r] = arr[r], arr[i]
    print(*arr)
    return arr, i

---

💼 Takeaway

• 퀵소트 구현 방법이 다양하다는 것을 알게됨
• 또 다른 퀵소트 알고리즘으로 Hoare partition scheme이 있음

---