[컴퓨터학개론 20장]- Search and Sort

sequential search(순차적 탐색)

• 순차적 탐색은 각 항목을 차례로 확인하여 우리가 탐색 중인 항목과 비교한다.
• 찾고자 하는 항목을 찾았거나, 모든 항목을 확인했는데 찾지 못했을 때에 멈춘다

Sorted Arrays [정렬된 배열] 

• ascending order : 오름 차순 1<2<3<4
• descending order : 내림차순 4>3>2>1
• 정렬된 배열에는 각 원소들이 순서대로 되어 있다.

Binary search(이진 탐색)

• 정렬된 배열 이어야 한다.
• 탐색은 중간부터 시작하여 항목을 발견하거나 확인하지 않은 항목들 중 절반을 제거-> 다시 중간부터 시작-> 반복

 

배열의 원소의 개수가 20개 이하 일 때는 sequential search가 binary search보다 빠르다. [비교 횟수와 시간의 개념은 다르다]

비교 횟수는 항상 binary search가 적다.

그 이상의 개수 일대는 binary search가 더 빠르다.

 

Sorting

• 모음 내의 항목들을 정돈하여 항목들 내외 하나 (또는 그 이상)의 필드가 순서대로 정리되게 한다.

Sort key [정렬 키]

• 정리의 기본이 되는 필드

Sorting algorithms [정렬 알고리즘]

 

정렬이 왜 중요한가?

배열에서 원소를 찾으려고 할 때

정렬이 되어 있는 경우 binary search를 사용,

정렬이 되어 있지 않은 경우 sequential search를 사용, 

속도면에서 차이가 남.

 

Selection Sort [선택 정렬]

• 알파벳 순으로 제일 먼저 나오는 이름을 찾아내어, 다른 종이에 적는다
• 원래 목록에서 그 이름을 지운다
• 이 과정을 모든 이름이 원래 목록에서는 지워지고 다른 목록에 올려졌을 때까지 반복하는데, 이때 두 번째 목록에는 똑같은 이름이 정렬된 순서대로 들어 있게 된다.

Bubble Sort [버블 정렬]

 

• 리스트의 마지막 요소에서 시작하여 올라가며, 원소들을 한쌍씩 비교하고 한 쌍중 아래에 있는 항목이 위의 항목보다 작을 때 교환한다.
• 장점 : 정렬된 배열이면 바로 return 해줌!

 

Insertion Sort [삽입 정렬]

• 앞부분을 정렬하고
• 새로운 1개씩을 알맞은 위치에 삽입해서 정렬 상태를 유지한다.
• 배열에 항목이 한 개이면, 이미 정렬된 것이다.
• 두 개의 항목이 있으면 둘을 비교하여 필요할 경우에 교환하면 정렬된다.
• 세 번째 항목을 앞의 두 항목과 비교해서 알맞은 위치에 놓는다.
• 이제 앞의 세 개의 항목은 정렬된 것이다.