정렬

정렬 알고리즘

컴퓨터 분야에서 중요시 되는 문제 가운데 하나.

데이터가 주어졌을 때 이를 순서대로 나열하는 문제.

정렬해야 하는 이유는 탐색을 위해서.

데이터가 정렬되어 있을 시 이진 탐색 이라는 알고리즘 사용 가능

삽입과 삭제가 자주 되는 경우 정렬에 더 많은 시간이 들어가므로 순차 탐색 하는 경우도 있음 (해시 탐색도 사용)

조회에 필요한 것이 바로 검색

• 이진 탐색

  이미 정렬된 데이터의 집합에 유효

  정렬을 수행 하는 이유 중 하나.

  임의의 값을 집었을 시 그 값보다 왼쪽은 무조건 그 값보다 작고, 오른쪽은 무조건 그 값보다 크다.

• 비교 정렬

  주어진 데이터 값 서로 비교하여 순서에 맞게 자리를 바꿔주는 형태

  데이터의 크기를 n이라고 했을 때 비교 정렬의 경우에는 n^2 번 만큼 비교 해야 정렬됨

  온갖 수단과 방법을 동원해 현재는 대략 n lg n 번 바교할 수 있도록 줄인 상태.

  n lg n 보다 더 이상 줄일 수 없음

• 실제

  실제로 돌려보면 결과가 다르게 나오는 경우 종종 있음

  하드웨어 입출력에 관여해 정렬 알고리즘마다 예상 시간이 각각 다르게 나오는 현상.

요약

• 정렬은 데이터가 주어졌응ㄹ 때 이를 순서대로 나열.

• 정렬해야 하는 이유는 이진탐색과 같은 탐색을 사용하기 위해.

• 이진 탐색은 임의의 값을 집었을 시 그 값의 왼쪽은 모두 그 값보다 작고 오른쪽은 모두 그 값보다 큼

• 비교 정렬은 주어진 값을 서로 비교해여 순서에 맞게 자리를 바꿔주는 형태

• 실제로 정렬 알고리즘들의 예상 시간은 하드웨어 입출력 때문에 실제와 다른 경우 많음