Quicksort In-Place

eunseo_thatsme·2022년 5월 19일
0

HackerRank

목록 보기
6/16
post-thumbnail

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이 있음

profile
내가 공부한 것들

0개의 댓글