오늘

• 웹 통신 과제 advanced 구현
• quick sort

지금

quick sort

가장 빠른 정렬 방법으로 알려져 quick sort로 불린다. 실제로 평범한 상황에서는 가장 빠른 정렬 방식이나 최악의 경우에는 O(n^2)의 시간 복잡도를 가진다.

정렬 방식

1. 맨뒤, 또는 맨앞의 값을 선택 (pivot)
2. 선택한 값을 제외한 나머지 리스트의 값들을 맨앞과 맨뒤를 순회하면서 조회 (left, right)
3. 왼쪽의 값이 선택한 값보다 작다면 인덱스를 증가 시킴 (left index++)
4. 오른쪽의 값이 선택한 값보다 크다면 인덱스를 감소 시킴 (right index--)
5. 왼쪽은 선택한 것 보다 크고, 오른쪽은 작다면 두 개의 위치를 변경함 ( right <-> left )
6. 위 과정을 왼쪽의 인덱스가 오른쪽의 인덱스보다 작을 때 까지진행함 (left < right)
7. 6번 까지의 과정이 끝나면 선택한 값과 왼쪽 인덱스의 값 자리를 변경함 (left <-> pivot)
8. 변경한 위치를 기준으로 양 옆으로 나누어 재귀로 진행함(sort(arr, left , pivot-1) && sort(arr, pivot+1, right))

데이터가 모두 정렬되어 있는 경우에는 시간 복잡도가 굉장히 올라간다.
그 최대는 O(n^2)이 된다. 이런 경우에는 삽입정렬등을 사용해 빠르게 해결할 수 있다.

웹 통신 과제를 하면서

오늘 웹 통신관련 토이(toy)를 만들어 보면서 모듈화를 조금 더 신경써서 해야 할 것 같다는 생각이 들었다.
app을 만들면서 함수의 독립성을 유지하고 재사용성을 고려하여 매서드를 구성해야 할 것 같다는 생각이 들었다.

내가만든 코드에서는 이벤트 핸들링을 init 메서드 안에서 정의하여 실행하는 식으로 구성했는데,
핸들러를 따로 분리하는게 init 메서드에 대한 가독성이 올라갔다.

내일

• 알고리즘