음기의 공부노트

데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 사람은 수십에서 수백 개의 데이터를 다루는 데 그치지만 컴퓨터가 다뤄야 할 데이터는 보통이 백만 개 단위이며 데이터베이스 같은 경우 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어 있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다

실제 응용에서는 상황에 따라 두 가지 이상의 정렬 방법을 사용하는 경우가 많다. 예를 들면, 정렬 대상이 특정 크기 이하로 단편화될 때 까지는 퀵정렬을 쓰다가, 그 특정 크기 이하가 됐을 때에는 작은 규모에서 강점을 보이는 삽입정렬을 쓴다거나. 혹은 특정 횟수 이상 재귀호출이 발생하면 O(n log n)이 보장되는 힙정렬을 쓴다거나.

1. O(n^2)
   • 대개 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다. 
     •  선택정렬
       • 설명
     •  버블정렬
       • 설명 : 1번째와 2번째 원소를 비교하여 정렬하고, 2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지, ...한다. 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 거품정렬이다.
       • 거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 이미 정렬된 자료를 정렬하는 바보짓을 왜 하냐는 의문이 들 수 있지만, 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.
         가장 손쉽게 구현하여 사용할 수 있지만, 만들기가 쉽고 직관적일 뿐이지 알고리즘적 관점에서 보면 대단히 비효율적인 정렬 방식이다.
       • 이해하기 쉽고 코드가 짧은 덕에 각종 교습서에서 정렬 알고리즘의 예시로 많이 보여주며, 입력량이 작으면 어지간한 비효율적인 방법도 씹어먹고 수행이 가능하지만 실제 개발에서는 전혀 쓰이지 않는다고 봐도 무방하다. 정말 어지간한 경우가 아닌 이상 버블정렬은 피해야 한다.
     • 칵테일 정렬
       • 설명
     • 삽입정렬
       • 설명

참조 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98