2021-1/컴퓨터알고리즘

Divide and Conquer 알고리즘의 quicksort알고리즘에 대해 알아보자!!!!! (위키피디아 ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC를 참고하여 작성했습니다) 퀵소트는 정렬 알고리즘의 하나인데 평균적으로 시간 복잡도가 O(nlogn)으로 빨라서 자주 쓰인다!! (worst case에는 O(n^2)) 기본 알고리즘은 리스트 가운데에서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 하는데 아무거나 고르면 된다!! 근데 나는 제일 앞의 원소를 선택할것이다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는..