[5.25] 06-6 퀵 정렬 (2)

비재귀적인 퀵 정렬 만들기

from for_class import Stack
from typing import MutableSequence

def qsort(a:MutableSequence, left:int, right:int)-> None:
    range = Stack(right - left + 1)

    range.push((left, right))

    while not range.is_empty():
        pl, pr = left, right = range.pop()
        x = a[(left + right) // 2]

        while pl <= pr:
            while a[pl] < x: pl += 1
            while a[pr] > x: pr -= 1
            if pl <= pr:
                a[pl], a[pr] = a[pr], a[pl]
                pl += 1
                pr -= 1
        if left < pr: range.push((left, pr))
        if pl < right : range.push((pl, right))

# 이때 stack - 고정 길이 스택 클래스 구현하기

from typing import Any
from collections import deque

class Stack:
    def __init__(self, maxlen:int = 256) -> None:
        self.capacity = maxlen
        self.__stk = deque([], maxlen)
    def __len__(self) -> int:
        return len(self.__stk)
    def is_empty(self) -> bool:
        return not self.__stk
    def is_full(self) -> bool:
        return len(self.__stk) == self.__stk.maxlen
    def push(self, value:Any) -> None:
        self.__stk.append(value)
    def pop(self) -> Any:
        return self.__stk.pop()
    def peek(self) -> Any:
        return self.__stk[-1]
    def clear(self) -> None:
        self.__stk.clear()
    def find(self, value:Any) -> Any:
        try:
            return self.__stk.index(value)
        except ValueError:
            return -1
    def count(self, value:Any) -> int:
        return self.__stk.count(value)
    def __contains__(self, value:Any) -> bool:
        return self.count(value)
    def dump(self) -> int:
        print(list(self.__stk))
        

sorted() 함수로 정렬하기

정렬을 수행하는 내장함수

이터러블 객체의 원소를 정렬하여 list로 반환한다. 

print('sorted() 함수를 사용하여 정렬합니다.')
num = int(input('원소 수를 입력하세요 : '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}] : '))

x = sorted(x)
print(x)