정렬이란?

정렬과 탐색

정렬 (sorting) 이란?

• 일련의 항목들을 정해진 순서로 배치하여 자료를 좀더 의미 있는 구조로 만든다.
• 일반적으로 정렬알고리즘은 비교(comparsion) 정렬과 선형 시간(linear time) 정렬로 나뉜다.
  • 비교 정렬 : 정렬하기 위해 각 항목들을 비교하는데 의존한다. O(n log n) 시간 이상 걸린다.
  • 선형 시간 정렬 : O(n) 시간에 정렬하는데서 비롯됨. 자료의 특성에 의존한다.

탐색 (searching) 이란?

• 자료 집합에서 한 항목의 위치를 알아내는 것
• 선형 탐색 (linear search) : 집합을 한 끝에서 다른 끝까지 조사
• 다른 방법들은 테이블, 이진 탐색 트리 같이 탐색을 위해 특별하게 개발된 자료 구조에 의존
• 인플레이스 (in-place) 정렬 : 정렬이 진행됨에 따라 정렬된 자료를 넣을 메모리와 같은 크기의 메모리만 사용

종류

• 삽입 정렬

  • 간단하고 인플레이스 정렬이라는 장점이 있다.
  • 최상은 작은 자료 집합에 대한 점증식 정렬이다.

• 퀵 정렬

  • 일반적인 경우에 최상의 정렬로 여겨지는 인플레이스 정렬 알고리즘이다.
  • 최상은 중간 정도에서도 큰 크기의 자료 집합 정렬이다.

• 합병 정렬

  • 본질적으로 퀵정렬과 같은 성능을 보이지만 두 배의 기억장소를 필요로 한다.
  • 최상은 아주 커다란 자료 집합을 위한 정렬이다. 정렬되지 않는 집합을 나누는 작업을 용이하게 한다.

• 카운팅 정렬

  • 가장 큰 값을 알고 있는 정수들에 대해 동작하는 안정된 선형 시간 정렬 알고리즘

• 기수 정렬

  • 한 숫자씩 항목들을 정렬하는 선형 시간 정렬 알고리즘이다.
  • 정수로 표현 가능한 조각들로 쉽게 쪼갤 수 있는 고정된 크기의 항목들에 잘 맞는다.

• 이진 탐색

  • 빈번한 삽입이나 삭제가 예상되지 않는 정렬된 자료를 탐색하는데 효과적이다.
  • 자료 집합을 다시 정렬하는 것이 탐색보다 비싸므로 자료가 변하지 않을 때 가장 좋다.

  ​

애플리케이션

• 순서 통계
  • 집합에서 i번째로 작은 원소를 찾는 것이다.
• 이진 탐색
  • 정렬된 자료에 의존하는 효율적인 탐색 방법이다.
  • 이진 탐색은 기본적으로 반복해서 정렬된 집합을 나누고 각 구획의 중간 항목을 조사함으로써 동작
• 디렉토리 리스팅
  • 묶음으로 구조화된 파일 시스템에서의 파일 리스팅이다.
  • 일반적으로 운영체제는 디렉토리 리스트를 보여주기 전에 어떤 방법으로 정렬한다.
• 데이터베이스 시스템
  • 대체로 빠르게 저장되고 검색되어야 하는 많은 양의 자료를 갖는 큰 시스템이다.
  • 데이터베이스에 저장되는 자료의 양은 자료를 탐색하는 효율적이고 유연한 방법을 중요하게 여긴다.
• 철자 검사기
  • 문서내의 단어 철자를 검사하는 프로그램이다.
  • 수천 단어들을 갖는 문서의 긴 문자열을 다루므로 용인되는 단어 집합을 효율적으로 탐색해야 한다.