4. 정렬 알고리즘

Date :210609

정렬 알고리즘

1. 선택 정렬

남은 자료 중에 최솟값을 뽑아 차례대로 배치하는 것

첫번째값을 기준으로
2번째-n번째 값과 비교해서 가장 작은 값을 1번째로 바꾼다.
이후 2번째값을 기준으로
3번째-n번째 값과 비교해서 가장 작은 값을 2번째로 바꾼다.
(이때 기준이였던 값이 가장 작은 값이 아니라면 뒷자리로 밀려난다.)

•  

선택정렬 예시

2. 버블 정렬

두개의 인접한 데이터를 비교해서 작은 데이터를 왼쪽으로 (오름차순) , 큰 데이터를 왼쪽으로 (내림차순) 마지막까지 반복하는 정렬방법이다.
최댓값을 찾는 작업을 수행하여 가장 큰값이 맨 뒤에 위치 한다. 가장 큰 값을 이동 한 후, 다시 처음으로 돌아가 두번째 큰값을 찾아 뒤에 위치하도록 한다. 반복적으로 큰값을 찾는 과정을 수행하기에 수행 시간이 길어지는 단점이 있다.

버블 정렬 예시 (글씨가 엉망이네요...뒤에서 부터 큰값을 채운다는 의미입니다)

3. 삽입 정렬

많은 사람들을 한 줄로 줄 세울때를 생각해보자
현재 정렬되지 않은 줄 = a
줄을 만들 공간을 확보한다 -> 리스트 생성(b)
a에 있는 사람 중 맨 앞 사람을 b로 이동한다.
a 두번째 사람과 b 첫번째 사람을 비교한다. a > b 일 경우 b뒤에 a가 위치한다. a < b일 경우 b앞에 위치한다.
이후 a세번째 사람과 b두번째 사람을 비교한다. a에 아무도 없을 때 까지 이 과정을 반복한다.

4. 쉘 정렬

삽입 정렬을 확장한 개념으로 데이터를 매개 변수를 기준으로 그 값만큼 떨어진 데이터를 하나의 subfile로 본다.
예를 들어 데이터 3,5,2,7,8,9 에서 매개변수가 2면 두칸 떨어진 데이터가 한 subfile이다. -> 3,2,8
이로 인해 떨어져있는 데이터를 쉽게 정렬 할 수 있다. subfile 에 있는 데이터를 삽입정렬 한 후
매개변수 값을 줄여가면서 삽입정렬을 반복하다가 매개변수가 1이 되면(모든 데이터가 다 붙었다.) 모든 데이터가 정렬됐음을 의미한다.
아래 그림으로 더 쉽게 이해할 수 있다.

5. 분할통치법

해결하려는 문제를 작은 여러개의 단위로 분할해서 문제를 해결하는 방법
합볍정렬, 퀵정렬, 이진탐색이 분할통치법을 이용한다.
이 기법의 세 단계는 분할단계(원래문제를 소문제로 나누는 것), 통치단계(소문제의 해를 순서대로 구하는 것), 합병단계(소문제의 해를 합해서 원래 문제에 대한 해를 만드는 것)

6. 합병정렬 (병합정렬)

큰 그룹을 최소단위로 분할한 후 (1개의 데이터) 인접한 데이터와 합병하여 비교한 후 다시 인접한 그룹과 합병하여 비교한다.
이 과정을 반복하여 정렬하는 과정이다.
즉, 전체 데이터를 한개로 다 쪼갠 후 서로 합쳐가면서 크기를 비교하여 정렬한다.

• 과정
  전체 데이터: 72,34,2,5,7,61,26,11,53,42 (최소 단위)
  1단계 정렬: (34,72),(2,5),(7,61)(11,26),(42,53)
  2단계 정렬: (2,5,34,72),(7,11,26,61),(42,53)
  3단계 정렬: (2,5,7,26,34,61,72),(42,53)
  4단계 정렬: (2,5,7,26,34,42,53,61,72)