2021.12.08 코테_퀵 정렬 연습

# 오늘의 문제

퀵 정렬 연습

 # 나의 코드

퀵 정렬 연습

퀵정렬 : pivot ( 보통 배열의 첫번째 값을 지정한다 )이라고 하는 다른 값들과 비교할 값을 중점으로 왼쪽과 오른쪽을 나눈 후 재귀적으로 해당 함수를 계속 호출해 정렬하는 방식

직관적인 일반적 프로그래밍 언어식으로 만든 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
  if start >= end:
    return

  pivot = start
  left = start + 1
  right = end

  while left <= right:
    while left <= end and array[left] <= array[pivot]:
      left += 1
    while right > start and array[right] >= array[pivot]:
      right -= 1
    
    if left>right:
      array[right], array[pivot] = array[pivot], array[right]
    else:
      array[left], array[right] =  array[right], array[left]
    
    quick_sort(array, start, right -1)
    quick_sort(array, right + 1, end)


quick_sort(array, 0, len(array)-1)
print(array)

 

python스럽게 작성한 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):

#재귀적으로 돌게되면 array의 값이 작아지는데 그 값이 1이 되면 함수 멈춤
  if len(array) <= 1:
    return array
  
  pivot = array[0]
  tail = array[1:]

  #list tail에 있는 애들을 하나씩 가져와서(Loop를 돌아서)
  #pivot 보다 값이 작으면 리스트에 넣어라
  left_side = [x for x in tail if x <= pivot]
  #반대
  right_side = [x for x in tail if x > pivot]

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)


print(quick_sort(array))