동작 방식
- 맨 처음 값 기준으로 왼쪽에서 오른쪽으로 큰게 있는지 확인
- 그런다음 오른쪽에서 왼쪽으로는 기준값보다 작은값이 있는지 확인
- 그런다음 그 두 값의 자리를 바꾼다.
- 그러다 작은값의 index 보다 큰 값의 index 값이 더 크게 되었을때
- 기준 값과 작은 값을 자리를 바꾼다.
- 그러면 기준값은 재자리를 찾았다.
- 그런다음 기준값을 기준으로 왼쪽과 오른쪽 배열에 대해 위 작업을 반복 수행한다.
특징
평균적으로 속도가 가장 빨라라이브러리 등 많은 곳에서 쓰인다.
장점
- O(N×N) 정렬보다 압도적으로 빠르다.
단점
- 최악의 경우에는 O(N×N)의 속도를 낸다 (ex > 배열이 이미 정렬이 되어 있는경우)
분할 정복의 장점을 사용하지 못하기 때문.
시간 복잡도
O(NlogN)
- 추론 1 : 원소가 10개의 배열 1개를 O(N*N) 작업을 한다고 가정 == 100
- 추론 2 : 원소가 5개의 배열 2개를 O(N*N) 작업을 한다고 가정 == 50
- 해당 원리를 '분할정복'이라 한다.
- 따라서 기준값을 기준으로 반씩 쪼개기 때문에 logN x 원소의 수 N
- 결론 : 시간 복잡도는 NlogN
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 25
@ Update : 2020. 01. 25
@ Description : Quick sort (퀵 정렬)
'''
def fn_swapping(list_target, int_index_a, int_index_b):
'''
@Description: List index swapping
@Arguments Example
list_target = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
int_index_a = 0
int_index_b = 2
'''
value_tmp = list_target[int_index_a]
list_target[int_index_a] = list_target[int_index_b]
list_target[int_index_b] = value_tmp
return list_target
def fn_quick_sort(list_input):
'''
@Description: quick sort (퀵 정렬)
@Arguments Example
list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
'''
int_len_list_input = len(list_input)
value_standard = list_input[0]
print("start : " + str(list_input))
for _ in range(int_len_list_input):
if int_len_list_input > 1:
int_left_index = 0
int_right_index = 0
for int_index in range(1, int_len_list_input):
if value_standard < list_input[int_index]:
int_left_index = int_index
break
for int_index in range(1, int_len_list_input):
if value_standard > list_input[int_len_list_input - int_index]:
int_right_index = int_len_list_input - int_index
break
if int_left_index > int_right_index or int_left_index == 0:
list_input = fn_swapping(list_input, 0, int_right_index)
list_left_responce = []
list_right_responce = []
if int_right_index > 0:
list_left_responce = fn_quick_sort(list_input[0:int_right_index])
if len(list_input[int_right_index + 1:]) > 0:
list_right_responce = fn_quick_sort(list_input[int_right_index +1:])
if len(list_left_responce + list_right_responce) > 0:
list_input = list_left_responce + [value_standard] + list_right_responce
break
else:
list_input = fn_swapping(list_input, int_right_index, int_left_index)
else:
return list_input
return list_input
if __name__ == "__main__":
list_fn_quick_sort_param = [10, 1, 5, 8, 4, 3, 2, 9, 6, 7]
print(fn_quick_sort(list_fn_quick_sort_param))