정렬, 탐색에 대해 알아보자.

목차
1. 정렬이란?
2. 탐색이란?
3. 정렬과 탐색의 차이점

 

정렬이란?

정렬(Sort)은 복수의 원소로 주어진 데이터를 정해진 기준에 따라 새롭게 늘어놓은 작업을 말한다. 졍렬을 위해서는 우선 사물들을 서로 비교할 수 있어야 한다. 비교할 수 있는 모든 속성들은 정렬의 기준이 될 수 있다. 정렬시켜야 될 대산을 보통 레코드(Record)라고 부른다. 또한 레코드는 여러 개의 필드로 이루어진다. 이들 중에서 정렬의 기준이 되는 필드를 키(Key) 또는 정렬 키(Sort Key)라고 한다.

 

단순하지만 비효율적인 방법

• 삽입 정렬 : 리스트에서 가장 작은 숫자를 선택해서 앞 쪽으로 옮기는 방법.
• 선택 정렬 : 손 안에 정렬된 카드가 있고 한 장씩 새로 받을 때마다 끼워 넣는 것. 정렬이 안된 부분의 숫자를 하나씩 정렬된 부분의 적절한 위치를 찾아 끼워 넣는 방법.
• 버블 정렬 : 인접한 2개의 레코드를 비교하여 크기가 순서대로가 아니라면 서로 교환하는 방법.

 

복잡하지만 효율적인 방법

• 퀵 정렬 : 리스트 안의 한 원소를 선택하고 그 원소를 기준으로 리스트를 분활하고 정렬함.
• 힙 정렬 : 최대 힙 또는 최소 힙을 구성하는 힙에서 원소를 하나씩 꺼내어 정렬된 리스트를 만듦.
• 병합 정렬 : 리스트를 반으로 나눈 후 각각을 정렬하고, 정렬된 부분 리스트를 병합하여 전체 리스트를 정렬함.
• 기수 정렬 : 가장 낮은 자리수부터 가장 높은 자리수까지 차례대로 정렬함.

 

탐색이란?

탐색(Search)은 많은 자료 중에서 무언가를 찾는 작업을 말한다. 보통 이런 레코드들의 집합을 테이블이라고 부른다. 레코들은 서로 구별하여 인식할 수 있는 키를 가지고 있는데 이를 탐색 키(Search Key)라고 한다. 결국 탐색은 원하는 탐색 키를 가진 레코드를 찾는 작업이다.

• 순차 탐색 : 리스트의 첫번째 원소부터 시작하여 찾고자 하는 값을 찾을 때까지 순차적으로 비교함.
• 이진 탐색 : 리스트를 반으로 나누어 찾고자 하는 값이 있는 부분만 탐색하여 탐색 속도를 높임.
• 보간 탐색 : 리스트를 반으로 나누는 것이 아니라 찾고자 하는 값이 위치할 것으로 예상되는 위치를 계산하여 탐색함.

 

정렬과 탐색의 차이점

1. 목적

• 정렬 : 데이터를 특정한 순서로 정렬하거나 배열함.
• 탐색 : 주어진 데이터 집합에서 특정 값을 찾거나 조건을 만족하는 데이터를 찾음

2. 동작

• 정렬 : 데이터를 기준에 따라 순서대로 재배열함.
• 탐색 : 주어진 데이터 집합에서 원하는 값을 찾기 위해 검색을 수행함.

3. 결과

• 정렬 : 데이터가 순서대로 정렬되어 있음.
• 탐색 : 원하는 값이나 조건에 맞는 데이터를 찾거나 해당 데이터가 없음을 알려줌. 

4. 알고리즘

• 정렬 : 버블 정렬, 퀵 정렬, 병합 정렬 등과 같은 정렬 알고리즘이 사용됨.
• 탐색 : 순차 탐색, 이진 탐색, 보간 탐색 등과 같은 탐색 알고리즘이 사용됨.

5. 시간 복잡도

• 정렬 : O(n log n)
• 탐색 : O(log n) 또는 O(n)

6. 적용 가능성

• 정렬 : 데이터를 정리하거나 비교할 때 사용됨.
• 탐색 : 데이터에서 특정 값을 찾거나 조건을 만족하는 데이터를 찾을 때 사용됨.