빅 오를 사용하면 내가 만든 알고리즘과 세상에 존재하는 범용 알고리즘을 비교할 기회가 생긴다.
4-1 버블정렬
정렬 알고리즘 ?: 컴퓨터 과학 분야에서 폭넓게 연구된 주제이며, 수년간 수십개의 정렬 알고리즘이 개발돼 있다.
정렬되지 않은 배열이 주어졌을 대, 어떻게 오름차순으로 정렬할 수 있을까?에 대한 문제를 해결한다.
배열 정렬의 단계
- 배열 내에서 연속된 두 항목을 가르킨다. 처음에는 배열의 첫 번째 원소부터 시작해서 처음 두 항목을 가르킨다. 첫 번째 항목과 두 번째 항목을 비교한다.
- 두 항목의 순서가 뒤바뀌어 있으면 두 항목을 교환한다. 순서가 올바르다면 2단계에서는 아무것도 하지 않는다.
- 포
- 배열의 끝까지 또는 이미 정렬된 값까지 1단계부터 3단계를 반복한다. 이것을 배열의 첫 패스스루라 끝났다 라고 한다. 즉, 배열 끝까지 값을 하나하나 가르키며 배열을 통과했다.
- 두 포인터를 다시 배열의 처음 두 값으로 옮겨서 1단계부터 4단계를 다시 힐행함으로써 새로운 패스스루를 실행한다. 교환이 일어나지 않는 패스스루가 생길 때까지 패스스루를 반복한다. 교환할 항목이 없다는 것은 배열이 정렬됐고 문제를 해결했다는 뜻
4-2 버블 정렬 실제로 해보기
[4, 2, 7, 1, 3] 이라는 배열을 정렬하고 싶다고 가정하자
- 먼저 4와 2를 비교
- 순서가 맞지 않으므로 둘을 교환한다 [2, 4, 7, 1, 3]
- 다음으로 4와 7을 비교한다 [2, 4, 7, 1, 3]
- 이제 7와 1을 비교한다
- 순서가 맞지 않으므로 교환한다 [2, 4, 1, 7, 3]
- 7과 3을 비교한다 [2, 4, 1, 3, 7]
- 순서가 맞지 않으므로 교환한다. 이제 7은 확실히 배열 내에서 올바른 위치에 있다. 7은 정렬되지 않은 값 중 가장 큰 값이다. 즉, 버블이었고 계속해서 오른쪽으로 옮겼기 때문이다.
- 두 번째 패스스루를 시작하면서 2와 4를 비교한다
- 올바른 순서이므로 다음 단계로 넘어가면서 4와 1을 비교한다
- 순서가 맞지 않으므로 교환한다 [2, 1, 4, 3, 7]
- 4와 3을 비교한다
- 순서가 맞지 않으므로 교환한다 [2, 1, 3, 4, 7] 첫 패스스루를 통해 7이 이미 올바른 위치에 있기 때문에 4와 7은 비교할 필요가 없으며 두 번재 패스스루도 끝이났다