Quick Sort, Binary Search

취업을 준비하며 자소서쓰고 면접 준비만 하면서.. 기술면접을 준비하려고보니 자료구조, 알고리즘 개념이 흐릿해진 것 같아 조금씩 코드를 작성하고 올려보려고 한다.

오늘은 Sorting Algorithm 중에서 가장 빠르다고 알려져 있는 Quick Sort이다.

O(nlog₂n)의 시간 복잡도를 가졌고, Python의 함수들은 Quick sort 혹은 Quick을 변형시킨 알고리즘을 사용한다고 한다.

 

필요한 요소는 이렇다.

pivot : 이 지점을 기준으로 리스트를 나눈다

less_list : pivot보다 작은 리스트

greater_list : pivot 보다 큰 리스트

eqaul_list : pivot과 같은 리스트

 

def quick(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr)//2] # " //2 " 는 정수 몫으로 반환
    less, greater, equal = [], [] ,[]
    for num in arr:
        if (pivot > num) :
            less.append(num)
        elif (pivot < num ):
            greater.append(num)
        else:
            equal.append(num)
    return quick(less) + equal + quick(greater)

print(quick([4,64,2,42,62,4,123,4123,46,3,3,1]))