정렬(Sorting) 알고리즘 O(n^2)

정렬 알고리즘 컴퓨터분야 전공을 했다면 한번쯤 반드시 들어봤을법한 "정렬" 에 관하여 얘기를 하고자 한다. 앞선 포스팅(이라고 해도 몇개월 전에 쓴..) 에서 잠깐 언급을 했었는데, 자세하게 보지않고 스쳐간 것 같아서 정리할 겸 글을 끄적여본다. 사실 간략하게 요약하면 "이진탐색(Binary Search)을 사용하기 위해 데이터를 정렬한다." 의 의미가 클 수 있다. 분산된 데이터는 자료를 참조하기가 어렵다. 예를 들어 100만개의 데이터가 있고, 맨 마지막에 데이터가 있다면, 원하는 데이터를 찾기 위해서는 100만개를 다 봐야할 수 있다. 그렇기 때문에 최악의 경우 n번 탐색을 해봐야 한다. 하지만 이진탐색을 사용하면 의 속도로 검색할 수 있다. 별로 체감이 안될 수 있는데, 다음 그래프를 보면 이해가..