정렬 1 (Sorting)

[Bubble / Selection / Insertion Sort]

sorting : n 구분 / 분류

 

정렬(Sorting)이란, 항목을 체계적으로 정리하는 과정이다.

알고리즘에서의 정렬은 요소들을 요소에 종류에 따라 오름차순/내림차순, 사전 순서대로 열거하는 알고리즘을 뜻한다.

 

 

1. 버블 정렬 (Bubble Sort)

: 연속으로 맞닿아있는 데이터를 비교하고 즉시 교환 해나가는 배열

[배열의 2개의 아이템을 선택 -> 2개의 아이템을 비교 -> 왼쪽 > 오른쪽 이면 교환 -> 배열 끝날 때 까지 반복] => 하나의 사이클

이와 같은 사이클을 모든 데이터가 정렬 될 때 까지 반복한다.

 

배열 [40, 20, 50, 30, 10]을 버블 정렬을 사용하여 오름차순으로 정렬 하여 보았다.

<원본 데이터>

<버블 정렬의 첫 번째 사이클>

인덱스 0과 1에 위치한 데이터부터 비교를 시작 하였다.

40과 20을 비교한 후 20이 40보다 오름차순에서 왼쪽에 위치 하여야 함으로 서로 교환을 한다. 이와 같은 과정을 배열의 종료까지 반복하면 <첫 번째 사이클>이 종료 된다.

이때의 배열은 [20, 40, 30, 10, 50] 이다.

 

 

<버블 정렬의 두 번째 사이클>

<두 번째 사이클>이 끝난 후의 배열은 [20, 30, 10, 40, 50] 이다.

 

 

<버블 정렬의 세 번째 사이클>

<세 번째 사이클>이 끝난 후의 배열은 [20, 10, 30, 40, 50] 이다.

 

 

<버블 정렬의 네 번째 사이클>

<네 번째 사이클>이 끝난 후의 배열은 [10, 20, 30, 40, 50] 이다.

 

네 개의 사이클이 끝난 후의 배열의 데이터가 오름차순으로 정렬 되었다.

 

 

 

2. 선택 정렬 (Selection Sort)

: 배열에서 데이터를 선별하고 데이터를 선택해서 올바른 자리에 곧바로 위치시키는 배열

 

[2개씩 데이터를 비교 -> 배열에서 가장 작은 데이터의 인덱스를 저장 -> 가장 작은 데이터를 가장 왼쪽의 데이터(인덱스 0의 값)와 교환] 이러한 사이클로 자리가 확정된 데이터의 오른쪽 데이터부터 반복한다. (오름차순으로 정렬이 될 때 까지)

 

버블 정렬에서 사용하였던 배열 [40, 20, 50, 30, 10]을 선택 정렬을 통해 오름차순으로 정렬하는 과정이다.

<선택 정렬 첫번째 사이클>

① : 가장 작은 숫자를 찾기 위해서 두 개의 데이터를 비교 40 > 20 => 가장 작은 숫자 : 20

② : 20 < 50 => 가장 작은 숫자 : 20

③ : 20 < 30 => 가장 작은 숫자 : 20

④ : 20 > 10 => 가장 작은 숫자 : 10

⑤ : 가장 작은 숫자 10이 값으로 존재하는 요소의 인덱스 4를 저장

⑥ : 데이터 10을 40과 교환하여 가장 왼쪽에 위치 시킴

 

 

<첫번째 사이클을 돌고 난 후의 배열>

<첫 번째 사이클>을 돌고 난 후의 배열

<선택 정렬 두번째 사이클>

※ 배열의 데이터 중 가장 작은 데이터인 10이 가장 왼쪽에 위치 하였기 때문에 10의 위치는 확정

① : 20 < 50 => (10을 제외한)가장 작은 숫자 : 20

② : 20 < 30 => 가장 작은 숫자 : 20

③ : 20 < 40 => 가장 작은 숫자 : 20

20은 올바른 위치에 있기에 교환 하지 않는다.

 

 

<선택 정렬 세번째 사이클>

※ 10, 20 확정

① : 50 > 30 => (10, 20을 제외한)가장 작은 숫자 : 30

② : 30 < 40 => 가장 작은 숫자 : 30

③ : 가장 작은 숫자 30이 값으로 존재하는 요소의 인덱스 3를 저장

④ : 값이 확정된 인덱스 0, 1를 제외하고 가장 왼쪽의 인덱스 2의 값 50과 30을 교환

 

 

<선택 정렬 네번째 사이클>

※ 10, 20, 30 확정

① : 50 > 40 => (10, 20, 30을 제외한)가장 작은 숫자 : 40

② : 가장 작은 숫자 40이 값으로 존재하는 요소의 인덱스 4를 저장

③ : 값이 확정된 인덱스 0, 1, 2를 제외하고 가장 왼쪽의 인덱스 3의 값 50과 40을 교환

 

 

<선택 정렬을 통한 정렬 완료>

※ 10, 20, 30, 40이 확정 되었기 때문에 50은 정렬할 필요 없음

선택 정렬을 사용한 정렬이 완료 되었다.

 

 

 

3. 삽입 정렬 (Insertion Sort)

: 배열에서 하나의 데이터를 선정 한 후 해당 데이터의 왼쪽의 데이터와 비교하여 올바른 자리로 이동시키는 정렬

 

[인덱스 1의 데이터를 선택 -> 선택한 데이터의 왼쪽의 데이터와 크기 비교 -> 선택한 데이터가 더 작다면 교환] 이러한 사이클로 모든 인덱스 2, 3, 4, ... 값을 순서대로 정렬한다.

 

원본 배열 [40, 20, 50, 30, 10]을 삽입 정렬을 통해 오름차순으로 정렬하는 과정이다.

 

인덱스 1의 데이터인 20을 기준으로 왼쪽 데이터와 비교한다.

① : 40 > 20 이므로, 교환 한다.

 

 

인덱스 2의 데이터인 50을 기준으로 왼쪽 데이터와 비교한다.

① : 40 > 50 이므로 교환 하지 않는다.

※ 20은 이미 40보다 작다는 것을 앞선 과정에서 비교하였기 때문에 50과 20은 별도로 비교하지 않는다.

 

 

인덱스 3의 데이터인 30을 기준으로 왼쪽 데이터와 비교한다.

① : 50 > 30 이므로 교환

② : 40 > 30 이므로 교환

③ : 20 < 30 이므로 교환 하지 않는다.

 

 

인덱스 4의 데이터인 10을 기준으로 왼쪽 데이터와 비교한다.

① : 50 > 10 이므로 교환

② : 40 > 10 이므로 교환

③ : 30 > 10 이므로 교환

④ : 20 > 10 이므로 교환

 

삽입 정렬 방식으로 배열이 오름차순으로 정렬 되었다.