정렬 알고리즘 #1 - 버블 정렬 (bubble sort), 삽입 정렬(insertion sort)

1. 버블 정렬 (bubble sort)

버블 정렬은 인접한 2개의 원소를 비교하여 정렬을 완성하는 알고리즘이다.

거품이 수면 위로 올라오는 듯한 모습을 보여 버블 정렬이라 불린다.

- 시간 복잡성

best-case : 이미 정렬되어 있는 경우 → O(n)

average-case : O(n²)

worst-case : 역순으로 정렬되어 있는 경우 → O(n²)

- Java 코드

2. 삽입 정렬 (insertion sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입하여 정렬을 완성하는 알고리즘이다.

정렬할 리스트가 완성되면 작업을 멈추고 즉시 반환할 수 있다.

다만 버블 정렬은 교환을 위한 임시변수만 필요한 것에 비하여,

삽입 정렬의 경우 정렬하려는 리스트의 2배 정도되는 저장 공간이 필요하다.

- 시간 복잡성

best-case : 역순으로 정렬되어 있는 경우 → O(n)

average-case : O(n²)

worst-case : 이미 정렬되어 있는 경우 → O(n²)

- Java 코드