퀵 정렬 (재귀X)

흔히 퀵 정렬에서는 왼쪽에서 오른쪽으로 가면서 피벗값보다 큰 값을,

오른쪽에서 왼쪽으로 가면서 피벗값보다 작은 값을 찾아 서로 바꾸면서 정렬을 진행함

 

오늘 할 건 재귀를 사용하지 않고 퀵 정렬을 구현하되 왼쪽에서 오른쪽으로만 이동하면서 정렬을 하고자 함

검색해야 하는 위치 정보를 [p, q]로 스택에 넣고 스택이 비워질 때까지 반복문 수행

8 3 11 9 12 2 6 15 18 10 7 14

가장 처음 스택에는 전체 범위 저장(0~11)

i = 피벗 인덱스(검색해야 하는 배열의 가장 앞)

j = 피벗 제외 배열을 이동하는 인덱스

j가 왼쪽에서 오른쪽으로 이동하면서 피벗보다 작은 값을 만나면 i를 1 증가시킨 후 그 자리의 값과 작은 값의 위치를 서로 바꿈

현재 i=0

j는 피벗(8) 옆부터 작은 값을 찾아감 ▶ 제일 먼저 3을 만남 ▶ i를 1증가 ▶ i=1 위치의 값과 3의 위치 바꿈 (1번째가 3이므로 그냥 그대로..)

j는 또 계속 다음 인덱스로 넘어가면서 피벗값보다 크면 통과, 작으면 또 i를 1 증가시킨 후 i번째 값과 j번째 값 자리바꿈

현재 i=1

2를 만남 ▶ i를 1증가 ▶ i=2 위치의 값과 2의 위치 바꿈(즉, 11과 2 자리바꿈) ▶ 8 3 2 9 12 11 6 15 18 10 7 14

...

그렇게 j가 배열을 끝까지 다 돌면 다음과 같이 정렬되어 있고 i=4로 7을 가리키고 있음

8 3 2 6 7 11 9 15 18 10 12 14

i가 가리키고 있는 값(피벗값보다 작은 숫자들 중 배열의 가장 오른쪽에 위치)과 피벗값 자리바꿈

7 3 2 6 8 11 9 15 18 10 12 14

이로써 피벗값을 기준으로 좌측은 피벗값보다 작은 수들의 집합, 우측은 피벗값보다 큰 수들의 집합이 형성

좌측 집합, 우측 집합은 또 다시 스택에 위치 정보를 저장해서 위와 같이 정렬 수행(위 과정 반복 - 스택이 빌 때까지)

 

import random

def quick_sort(data):
    stack = [[0, len(data)-1]]    # 스택에 검색할 범위를 리스트로 삽입
    while stack:    # 스택에 값이 있을 때만 반복문 수행
        findRange = stack.pop()
        p = findRange[0]    # 검색 시작 인덱스
        q = findRange[1]    # 검색 끝 인덱스

        if p < q:
            pivot = data[p] # 검색 범위에서 가장 앞 요소
            i = p
            for j in range(p+1, q+1):
                if data[j] < pivot:     # 피벗값보다 작은 요소를 찾으면 i를 오른쪽으로 한 칸 이동한 뒤 그 인덱스에 있는 값과 작은 요소값 자리 바꿈
                    i += 1
                    data[i], data[j] = data[j], data[i]

            data[i], data[p] = data[p], data[i]     # 피벗값과 피벗값보다 작은 요소(검색 범위에서 작은 값들 중 가장 오른쪽에 위치) 자리바꿈

            if i+1 < q:     # 피벗 기준 피벗의 오른쪽 집합 (피벗의 오른쪽에 정렬할 요소가 있을 때 스택에 추가)
                stack.append([i+1, q])
            if i-p >= 2:    # 피벗 기준 피벗의 왼쪽 집합 (정렬하고자 하는 요소가 2개 이상일 때 스택에 추가)
                stack.append([p, i-1])

    print(data)


arr = [random.randrange(1, 1000) for i in range(10)]
print(arr)
quick_sort(arr)

 

실행 결과