기본 정렬(Basic Sort)

정렬의 개념: 특정 기준을 적용하여 나열함

3 4 1 2 

(오름차순)-> 1 2 3 4

(내림차순)-> 4 3 2 1

 

정렬의 종류: 선택정렬, 삽입정렬, 버블정렬

 

 

선택정렬: 최솟값을 앞으로 이동시킴 (기준: 오름차순)

14

4

8

23

11

5

3

2

4

9

위와 같은 숫자들을 정렬해야 한다고 할때, 선택정렬은 정렬되지 않은 부분에서의 최솟값을 찾아 자리를 바꿔준다.

위 배열에서는 2가 최솟값이고 아직 정렬이 되어있는 부분이 하나도 없으므로 2와 14를 바꿔준다.

2

4

8

23

11

5

3

14

4

9

그렇다면 위 배열의 2까지는 정렬이 완료된 것이다. 노란색 배경은 이 곳까지 정렬이 완료되었다는 의미로 사용했다.

한번 더 진행을 하게 된다면 다음과 같은 형태가 나온다.

2

3

8

23

11

5

4

14

4

9

선택 정렬의 목표는 정렬된 부분을 배열의 끝까지 이동시키는 것이다.

모든 숫자의 정렬이 완료된 상태를 보자.

2

3

4

4

5

8

9

11

14

23

 

 

삽입정렬: 원소를 차례대로 정렬된 배열에 삽입시킴(기준: 오름차순)

14

4

8

23

11

5

3

2

4

9

이 곳에서 14까지는 정렬된 배열이고, 차례로 이어진 배열은 삽입되는 원소들이라 하자. 이곳에 4가 삽입될 경우 인접한 14와 크기 비교를 해서 자리를 바꿔서 비교해준다. 4는 14보다 작기 때문에 기준이 오름차순이라면 4가 14의 앞에 위치하게 된다.

4

14

8

23

11

5

3

2

4

9

위와 같은 방식으로 8도 인접한 것과 비교를 해서 삽입시켜주는 방식으로 계속해서 정렬하는 방식이다.

 

 

버블정렬: 인접한 원소를 비교하여 큰 수를 뒤로 보냄(기준: 오름차순)

14

4

8

23

11

5

3

2

4

9

다음과 같이 정렬되지 않은 배열이 있을 때, 제일 처음 원소인 14와 4를 비교하게 되면 4가 14보다 작기에 4와 14의 위치를 바꿔준다. 그렇다면 원소는 4 14 8 23 11 5 3 2 4 9 의 순으로 나열되어 있을 것이고, 이때 14와 8 또한 비교해서 자리를 바꿔준다. 이 방식을 10번 하게 된다면 다음과 같은 표가 나온다.

4

8

14

11

5

3

2

4

9

23

그렇다면 제일 큰 수를 정렬 완료한 것이다. 버블정렬의 목표는 제일 작은 수까지 정렬을 완료하는 것이다.