understanding pesudo-code of QuickSort

🦢 백준 퀵 정렬 대표 문제 모음) 추후

🦢 퀵 정렬 concepts 포스팅) 추후

---

🦢 QuickSort pseudo-code

quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- partition(A, p, r);  # 분할
        quick_sort(A, p, q - 1);  # 왼쪽 부분 배열 정렬
        quick_sort(A, q + 1, r);  # 오른쪽 부분 배열 정렬
    }
}

partition(A[], p, r) {
    x <- A[r];    # 기준원소 - pivot을 rightmost 설정
    i <- p - 1;   # i는 x보다 작거나 작은 원소들의 끝지점
    for j <- p to r - 1  # j는 아직 정해지지 않은 원소들의 시작 지점
        if (A[j] ≤ x) then A[++i] <-> A[j]; # i값 증가 후 A[i] <-> A[j] 교환
    if (i + 1 != r) then A[i + 1] <-> A[r]; # i + 1과 r이 서로 다르면 A[i + 1]과 A[r]을 교환
    return i + 1;
}

 

🦢 대표 예시)

배열 [5,8,1,3,7,9,2]

※ rightmost element를 pivot으로 설정 ※

 

① pseudo-code quick_sort) 

▶ 1번째 quick_sort(A,0,6) [5,8,1,3,7,9,2]

→ partition: rightmost 2를 기준으로 분리 - [1,2,5,3,7,9,8] 

→ quick_sort(A,0,0) & quick_sort(A,2,6)

※ [2] 완료 ※

 

▶ 2번째 quick_sort(A,0,0) [1] (1 quick sort 좌측)

→ p<r if문 조건 만족하지 않으므로 끝!

※ [1,2] 완료 ※

 

▶ 3번째 quick_sort(A,2,6) [5,3,7,9,8] (1 quick sort 우측)

→ partition: rightmost 8을 기준으로 분리 - [5,3,7,8,9]

※ [1,2,8] 완료 ※

 

▶ 4번째 quick_sort(A,0,2) [5,3,7] (3 quick sort 좌측)

→ partition: rightmost 7을 기준으로 분리 - [5,3,7]

※ [1,2,7,8] 완료 ※

 

▶ 5번째 quick_sort(A,0,1) [5,3] (4 quick sort 좌측) / 4 quick sort 우측 없음

→ partition: rightmost 3을 기준으로 분리 - [3,5]

※ [1,2,3,7,8] 완료 ※

 

▶ 6번째 quick_sort(A,1,1) [5] (5 quick sort 우측) / 5 quick sort 좌측 없음

→ p<r if문 조건 만족하지 않으므로 끝!

※ [1,2,3,5,7,8] 완료 ※

 

▶ 7번째 quick_sort(A,1,1) [9] (3 quick sort 우측)

→ p<r if문 조건 만족하지 않으므로 끝!

※ [1,2,3,5,7,8,9] 완료 ※

 

② pseudo-code partition) rightmost 원소를 pivot으로 설정하고 pivot 기준 왼쪽과 오른쪽 배열 나눈 뒤의 pivot 위치 출력 

 

▶ ex) 위 1번째 quicksort에서 rightmost element를 pivot으로 두고 partition하는 과정을 정리해보자면

 

[5,8,1,3,7,9,2] → [1,2,5,3,7,9,8]

 

① pivot 설정) 시작 p, 끝 r, 비교대상이 되는 pivot은 rightmost element로 A[r]은 2

② i 설정) i는 시작 element p인 5 앞에서부터 시작 (여기에서 i는 pivot보다 작거나 같은 수들의 끝 위치)

③ j 시작) j는 시작 element p인 5부터 끝 element r -1인, 끝 바로 앞부분 9까지 순회

→ A[j]가 A[r]보다 같거나 작다면, A[++i]와 A[j]를 바꾼다. (A[j]가 pivot보다 작거나 같으므로 최대한 왼쪽으로 치우치게끔 하기 위해)

④ 마지막 pivot과 i 비교) j가 다 돌고 난 뒤, i가 1이 더해진 결과의 위치가 pivot위치가 아니라면, pivot보다 큰 원소가 분명히 있었다는 뜻이 되므로, pivot을 i+1 위치와 바꿔주어, pivot 기준 왼쪽은 같거나 작은 원소들, 오른쪽은 큰 원소들로 쭉 구성되게 한다.

⑤ 최종적으로 pivot의 위치를 return)

🦢 QuickSort pseudo-code - python code

# Python program for implementation of Quicksort Sort

# This implementation utilizes pivot as the last element in the nums list
# It has a pointer to keep track of the elements smaller than the pivot
# At the very end of partition() function, the pointer is swapped with the pivot
# to come up with a "sorted" nums relative to the pivot

# Function to find the partition position
def partition(array, low, high):

	# choose the rightmost element as pivot
	pivot = array[high]

	# pointer for greater element
	i = low - 1

	# traverse through all elements
	# compare each element with pivot
	for j in range(low, high):
		if array[j] <= pivot:

			# If element smaller than pivot is found
			# swap it with the greater element pointed by i
			i = i + 1

			# Swapping element at i with element at j
			(array[i], array[j]) = (array[j], array[i])

	# Swap the pivot element with the greater element specified by i
	(array[i + 1], array[high]) = (array[high], array[i + 1])

	# Return the position from where partition is done
	return i + 1

# function to perform quicksort


def quickSort(array, low, high):
	if low < high:

		# Find pivot element such that
		# element smaller than pivot are on the left
		# element greater than pivot are on the right
		pi = partition(array, low, high)

		# Recursive call on the left of pivot
		quickSort(array, low, pi - 1)

		# Recursive call on the right of pivot
		quickSort(array, pi + 1, high)


data = [1, 7, 4, 1, 10, 9, -2]
print("Unsorted Array")
print(data)

size = len(data)

quickSort(data, 0, size - 1)

print('Sorted Array in Ascending Order:')
print(data)

'''
Unsorted Array
[1, 7, 4, 1, 10, 9, -2]
Sorted Array in Ascending Order:
[-2, 1, 1, 4, 7, 9, 10]
'''

---

* 썸네일 출처) HackerRank

* pseudo-code 설명 출처) https://youtu.be/COk73cpQbFQ

* python code 출처) https://www.geeksforgeeks.org/python-program-for-quicksort/