정렬 / 버블정렬 / 선택정렬

정렬은 말 그대로 무작위로 나열된 숫자들을 내림차순 또는 오름차순으로 정렬하는 방법이다.

정렬 방법은 다양하게 있는데 버블정렬과 선택정렬에 대해 정리해보려고 한다.

나만 그런지 모르겠는데 정렬 이름만 듣고 무슨 정렬인지 바로 떠오르지가 않고 자꾸 헷갈려서 이번에 정리하면서 기억해보려고 한다. 

 

버블정렬 (bubble sort)

버블정렬은 인접한 두 수를 비교해서 정렬하는 방법이다.

정렬이 완료될 때까지 루프를 돌아서 정렬시킨다.

 

다음의 과정을 거친다.

 

1번째 루프

1. 5 10 7 22 4 

위 배열을 오름차순 배열로 만들기 위해 0 ~ 4 번 숫자라고 했을 때 0번 자리 숫자부터 하나 큰 자리에 있는 숫자와 비교하여 정렬을 한다.

0번자리와 1번자리를 비교했을 때 5 < 10 이기 때문에 자리를 바꾸지 않는다.

 

2. 5 10 7 22 4

1번 자리와 2번자리를 비교한다. 10 > 7 이므로 오름차순 정렬일 때 10이 더 뒤에 있어야한다. 자리를 바꾼다

 

3. 5 7 10 22 4

1번과 2번자리의 숫자가 바뀌어 2번자리에 10이 있다. 

2번자리와 3번자리를 비교한다. 10 < 22 이므로 그대로 둔다.

 

4. 5 7 10 22 4

3번자리와 4번자리를 비교한다. 22 > 4 이므로 자리를 바꾼다.

 

5. 5 7 10 4 22

1번째 루프 끝

 

2번째 루프

1. 5 7 10 4 22

1번째 루프가 끝났을 때의 상태이다. 0번자리와 1번자리를 비교한다. 5 < 7 이므로 그대로 둔다.

 

2. 5 7 10 4 22

1번과 2번자리를 비교한다 7 < 10 이므로 그대로 둔다

 

3. 5 7 10 4 22

2번과 3번자리를 비교한다. 10 > 4 이므로 자리를 바꾼다. 

 

4. 5 7 4 10 22

 

3번째 루프 

5 4 7 10 22

 

4번째 루프 

4 5 7 10 22

 

이 방식으로 루프를 돌면서 정렬시키는 방식이 버블 정렬이다.

 

버블정렬의 경우 한 번의 루프에서 제일 큰 수 한 개는 무조건 맞춰지지만 다른 수는 보장할 수 없다. 따라서 최악의 경우 배열의 길이 n 크기의 루프를 n 번 돌아야 하므로 시간복잡도는 n^2 이다.

 

선택 정렬 (selection sort)

최솟값, 또는 최댓값을 찾아서 자리를 바로 이동해주는 정렬방법이다.

 

5 10 7 22 4  

이 배열을 오름차순으로 정렬한다.

최솟값인 4를 찾고 맨 앞의 수와 바꾼다.

 

4 10 7 22 5

다시 최솟값을 찾고 두번째 자리와 바꾼다

 

4 5 7 22 10

반복한다

 

4 5 7 10 22

 

선택 정렬을 최악의 경우 n크기의 배열을 n번 탐색해야한다. 

따라서 버블정렬과 동일하게 n^2의 시간복잡도를 가진다