[그림으로 배우는 알고리즘] 3. 정렬과 검색

정렬(Sort) 

대상이 갖고 있는 특성을 기준으로 나열하는 것

 

정렬 종류

 

1. 버킷 정렬 : 최대 값의 갯수만큼 데이터를 저장하고 정렬

2. 기수 정렬 : 숫자의 각 자리를 기준으로 차례대로 데이터를 정렬한다.

3. 단순 선택 정렬 : 데이터 중 최소 값 또는 최대 값을 찾아, 첫 번째 요소(또는 마지막 요소)와 교환한다.

4. 단순 교환 정렬(버블 정렬) : 서로 이웃한 데이터끼리 크고 작음을 비교해서 올바른 위치로 데이터를 이동시킨다.

5. 단순 삽입 정렬 : 정렬한 데이터를 이미 정렬된 데이터들 사이의 올바른 위치에 삽입한다.

6. 셸 정렬 : 정렬할 데이터들을 일정한 개수의 그룹으로 묶어서 정렬한다.(그룹으로 묶은 다음, 그룹 안에서 정렬)

7. 병합 정렬 : 정렬할 데이터를 반으로 자르고, 자른 데이터를 다시 반으로 자르는 작업 되풀이

8. 퀵 정렬 : 정렬할 데이터 안에서 임의의 숫자를 선택하고 그 값의 크고 작음을 기준으로 데이터들을 반으로 쪼갠다.

9. 힙 정렬 : 힙 구조를 이용하여 정렬한다.

 

버킷 정렬

다른 배열에 데이터를 저장하고 정렬

빈 배열을 준비하고 배열의 번호와 일치하는 모든 데이터를 저장한 다음에 1번째 데이터부터 꺼내는 것이 버킷 정렬.

 

기수 정렬

아래 자릿수부터 윗 자리수까지 버킷 정렬을 반복

정렬할 데이터의 자릿수가 k 라면 버킷정렬을 k번 실시한다.

 

기수 정렬에서 2가지 중요 사항

1. 정렬할 지릿수 선택 방향을 가장 낮은 자릿수에서 윗 자릿수로 할 것

2. 아래 자리에서 이미 정렬된 데이터들의 순서는 그대로 유지할 것

 

단순 선택 정렬

최소 값(최대 값)을 골라서 이미 정렬된 마지막 요소와 교환하는 정렬

가장 알기 쉬운 정렬 알고리즘

 

단순 선택 정렬로 오름차순 정렬하는 단계

1. '정렬되지 않은 부분'안에서 최소 값(또는 최대 값)을 찾는다.

2. '최소값'과 '정렬되지 않은 부분의 1번째 요소'와 교환한다.

(이 작업이 최소 값을 '정렬된 부분의 마지막 요소'로 만든다)

3. '정렬되지 않은 부분'의 시작 위치를 한 칸 뒤로 옮긴다.

(이 작업이 '정렬되지 않은 부분'의 범위를 한 칸씩 줄이게 된다)

4. '정렬되지 않은 부분'의 요소 수가 1이 될 때까지 1-3단계를 반복한다.

('정렬되지 않은 부분'안의 최소 값(or 최대값)을 선택해서 '정렬된 부분' 끝으로 옮긴다.)

 

단순 교환 정렬(버블 정렬)

이웃한 데이터 2개의 크고 작음을 기뵤한 뒤, 정렬 순서와 반대일 경우 앞뒤 데이터들의 순서를 바꾸어 데이터를 정렬

 

정렬할 배열은 '정렬되지 않은 부분(앞부분)' 과 '정렬된 부분(뒷부분)' 으로 나뉜다.

정렬을 시작할 때는 '정렬된 부분'은 비어 있는 상태

'정렬되지 않은 부분'이 배열 전체를 차지

 

'정렬된 부분'이 데이터 열 전체를 차지하면 정렬이 완료

 

단순 삽입 정렬

정렬된 데이터를 비교해서 올바른 위치에 삽입하는 정렬

 

데이터 열 안의 어떤 데이터를 기준 데이터로 삼는다.

기준 데이터보다 앞에 위치하는 데이터들을 차례로 비교하여,

기준 데이터를 정렬조건과 일치하는 위치에 삽입하여 데이터를 정렬한다.

('정렬된 부분' 안에 '정렬되지 않은 부분'의 데이터를 정렬 조건에 맞추어 삽입해 나가는 알고리즘)

 

셸 정렬

정렬할 데이터 배열을 일정 길이의 그룹으로 나누고, 그 그룹 안에서 정렬조건에 맞추어 정렬한다.

(이웃한 데이터들을 순사적으로 정렬x)

 

병합(merge)

병합 : '정렬된 여러 개의 데이터 열' 들을 '정렬된 하나의 데이터 열'로 만드는 알고리즘.

 

정렬된 여러개의 데이터 열이 있을 때, 전체 열의 최소 값은 항상 각 데이터 열의 1번째에 있으므로

각 열의 1번째 데이터만 주의 깊게 살피면 된다.

 

검색(Search) 이란?

여러 개의 데이터 안에서 원하는 데이터를 찾아내는 알고리즘

 

검색 알고리즘 종류 

1. 순차 검색 : 처음부터 끝까지 샅샅이 데이터를 비교

2. 이진 검색 : 정렬된 데이터 안에서 고속 검색

3. 문자열 검색 : 주어진 문자열 안에서 원하는 문자열의 위치를 찾아낸다.

4. KMP 검색 : 일치하지 않는 문자의 위치와 부분 문자열의 구성 정보를 통해 효율적으로 문자 검색

5. BM 검색 : 부분 문자열의 끝부분부터 앞부분 순서대로 문자를 비교

 

 

 

 

책 - 그림으로 배우는 알고리즘 Basic 공부하면서 정리했습니다.