[algorithms] ch2. Divide-and-Conquer algorithms (medians, quick sort)

(23.03.10)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

정리한 내용

2.4 medians  (+ quick sort)

---

Medians

확실하지 않은 풀이

 

 

quick sort

 

 

 

 

quick sort python code

def quick_sort(input, start, end):
  if start >= end:
    return input
  
  pivot = start
  left = start+1
  right = end

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

 

 

 

 

 

 

 

학교 강의 들으면서 정리했던 quick sort 내용: https://hey-stranger.tistory.com/135

[알고리즘] Quick sort: divide-and-conquer & loop invariants