Python Quicksort

<커맨드 라인에서 동작하는 퀵 정렬>

#퀵정렬 함수
def quicksort(xList):
    
    if len(xList) <= 1:
        return xList
    
    smallerList = []
    biggerList = []
    equalList = []
 
    pivot = xList[len(xList) // 2]
    
    for i in xList:
        if i < pivot:
            smallerList.append(i)
        elif i > pivot:
            biggerList.append(i)
        else:
            equalList.append(i)
 
    return quicksort(smallerList) + equalList + quicksort(biggerList)
 
#정수 검사 함수
def isInt(n):
    try:
        int(n)
        return True
    except ValueError:
        return False
 
import sys
 
inputList = []
error = "잘못 입력하셨습니다.\n[파일명][-o][A:오름차순 or D:내림차순][-i][정렬할 정수 배열]"
 
#정수 배열을 입력했는지 검사
for x in range(4,len(sys.argv)):
    if isInt(sys.argv[x]) == False:
        print(error)
        sys.exit(1)
 
#옵션을 올바르게 입력했는지 검사
if sys.argv[1] == "-o" and sys.argv[2] == "A" and sys.argv[3] == "-i":
    for x in range(4,len(sys.argv)):
        inputList.append(int(sys.argv[x]))
 
    print(quicksort(inputList))
 
elif sys.argv[1] == "-o" and sys.argv[2] == "D" and sys.argv[3] == "-i":
    for x in range(4,len(sys.argv)):
        inputList.append(int(sys.argv[x]))
 
    quicksortD = quicksort(inputList)
    quicksortD.reverse()
    print(quicksortD)
    
else:
    print(error)
    sys.exit(1)
 

python에서 함수를 정의할 때 파라미터의 타입을 정해주지 않아도 되기 때문에 변수만 넣어 놓으면 리스트를 받아온다.

함수의 구현은 pivot을 리스트의 중간 위치에 있는 값으로 정해놓고 리스트의 왼쪽부터 pivot보다 작으면 smallList, 크면 biggerList, 같으면 equalList에 넣어준다.

그런 다음 반환을 할 때 smallList + equalList + biggerList 순서로 반환을 하되 smallList와 biggerList는 다시 quicksort 함수의 인자로 주어 각각 재귀적으로 처리되게 해준다.

재귀의 탈출 조건으로 함수의 인자 값으로 들어온 xList의 길이가 1 이하이면(더 이상 정렬 x) 자기 자신을 반환하도록 한다.

이 함수가 동작할 때 커맨드 라인에서 인자 값을 받아오게 하기 위해 sys 라이브러리를 사용했다.

sys 라이브러리의 argv는 

argv[0] = 파일 명(경로 포함)

argv[1] = 인자 1

argv[2] = 인자 2

...

형식이다. (다른 기능들도 많은데 일단 지금은 이 기능만 사용)

앞에 옵션의 위치는 정해져 있으므로

argv[1] = -o : 정렬할 방식 선택

argv[2] =  AorD : 오름차순or내림차순

argv[3] = -i : 정렬할 배열

로 정해 놓았고, argv[4] 부터는 반복문을 돌면서 인자 값들을 리스트에 담아 한 번에 quicksort 함수로 넘겨준다.

이 때 주의해야 할 점은 argv는 인자 값을 String 타입으로 참조하기 때문에 형변환을 해줘야 한다.

range(시작 번호,끝 번호)는 내장 함수로 시작 번호부터 끝 번호까지를 차례로 담고 있을 수 있다.

quicksort(xList) 함수의 경우 반환을 내림차순 방식으로 반환하기 때문에 오름차순으로 정렬할 때는 이 함수의 반환 값을 변수에 다시 남고 revers() 함수를 통해 뒤집어 준다.

따로 예외 처리를 한 부분은 옵션을 알맞게 입력하였는지의 여부와 정수 배열을 입력했는지(isInt())를 검사한다.

결과 화면