버블정렬이던, 선택정렬이던
중요한 포인트는 시간복잡도 입니다.
구현할 때엔 항상 최악의 경우를 가정 및 생각해서 구현하여야 합니다.
--> 즉, 시간복잡도 생각해야한다는 말입니다.

버블정렬 (bubble sort)

bubble sort는 두 인접한 데이터의 크기를 비교해 정렬하는 방법입니다.

진행 순서

1. 인접한 두 데이터를 비교하며 정렬을 진행합니다.
2. 정렬이 끝날 때까지 비교~교환 과정이 반복됩니다.
3. 반복이 끝날 때마다, 가장 큰 값(또는 작은 값)이 원소들 중 가장 뒷 위치로 이동하게 됩니다.

장점

1. 구현이 쉽다는 점이 장점입니다. 알게모르게 저희는 버블정렬을 사용하여 sorting을 해왔을 것입니다.
2. 직관적이고 간단한 코드로 작성이 가능합니다. (보통 2중반복문을 써서 sorting함)
3. 안정 정렬 : 값이 같은 원소들 간의 순서가 정렬 후에도 유지됩니다.
4. 제자리 정렬 : 추가적인 메모리가 필요하지 않습니다.

단점

• 시간복잡도가 좋지 않습니다.
  이유는, n 개를 n번 loop 돌기 때문에, 시간 복잡도는 O(n^2) 입니다.

시간복잡도

1. 최악의 경우 시간복잡도 : O(n^2)입니다. (n은 데이터 즉, 원소의 개수) 이미 정렬되어 있는 경우에도 항상 배열 전체를 checking(스캔)해야 하기 때문입니다.
   또한, 코딩테스트를 볼 때, 최악의 경우를 가정하고 코드를 구현하기 때문에,
   시간복잡도가 O(n^2)이면 시간제한에 걸리기 쉽습니다. 이러한 단점때문에 쉽지않습니다.

2. 평균적인 시간복잡도: O(n²)입니다. 원소의 위치에 관계없이 전체 배열 스캔이 반복되기 때문입니다.

3. 최선의 경우 시간복잡도: O(n). 이미 정렬되어 있는 경우에도 항상 배열 전체를 스캔하게 되지만, 일반적으로는 최소 n-1번의 비교가 필요합니다.

요약하면

버블 정렬은 간단하게 구현할 수 있는 장점이 있지만, 시간복잡도 측면에서 효율적이지 않은 알고리즘입니다. 실제 상황에서는 더 나은 성능을 갖는 다른 정렬 알고리즘들(퀵 정렬, 병합 정렬 등)이 더 자주 사용되지만,
근본인 버블 및 선택 정렬이 돌아가는 원리와 시간복잡도가 O(n^2)인 이유는 파악하고 있어야합니다.

코드

int N = 5;
int[]arr = new int[N];
for(int i=0;i<arr.length;i++){
	arr[i]= // 입력받는 스트림 작성 버퍼 || 스캐너
}

// SORTING --> 이 부분이 해당 알고리즘의 핵심
for(int i=0;i<N-1;i++){
	for(int j=0;j<N-1-i;j++){
    	if(arr[j]>arr[j+1]){
        	int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

선택정렬 (Selection Sort)

• 핵심이론 : 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심입니다.
• 다시 말해, 비교 기반 정렬 알고리즘 중 하나로, 최소값(또는 최대값)을 찾아 위치를 교환해 가며 정렬하는 방식입니다.

특징

1. 주어진 배열을 최소값(또는 최대값)을 찾아 왼쪽(또는 오른쪽)의 정렬된 요소 뒤에 삽입하는 방식으로 정렬합니다.
2. 단계별로 최소값(또는 최대값)을 찾아서 다른 원소와 교환하며 정렬합니다.

장점

1. 구현이 간단하고 직관적입니다.
2. 제자리 정렬: 추가적인 메모리가 필요하지 않습니다.
3. 교환 횟수가 버블 정렬에 비해 적어 교환에 많은 결제가 필요한 경우에는 성능상의 이점이 있습니다.

단점

1. 지극히 평균적인 성능에서도 시간복잡도가 좋지 않습니다.
   --> 이러한 이유때문에 앞서 말했듯이,
   시간복잡도가 O(n^2)이라서 잘 채택되지 않으나, 원리는 이해하고 있어야합니다.

   왜냐하면, 난이도가 높은 알고리즘을 구현할 때,
   부분적으로 선택 또는 버블정렬이 필요한 순간이 오기 때문입니다.

2. 불안정 정렬: 값이 같은 원소들 간의 순서가 정렬 후에 바뀔 수 있어 상대적인 순서가 변경될 수 있습니다.

시간복잡도 O

1. 최악의 경우 시간복잡도: O(n²)입니다.(n은 원소의 개수) 정렬이 이미 완료되었어도 최소값(또는 최대값)을 찾는 과정에 지연이 있습니다.
2. 평균적인 시간복잡도: O(n²)입니다. 상황에 따라 버블 정렬보다는 조금 빠르지만 시간복잡도가 최적이라고 할 수는 없습니다.
3. 최선의 경우 시간복잡도: O(n²). 정렬 상태에 상관없이 항상 전체 배열을 검색해야 합니다.

정리

• 선택 정렬은 구현이 간단하지만 시간복잡도 측면에서 효율적이지 않은 알고리즘입니다.
  그러나 교환 비용이 높을 때 이점이 있을 수 있습니다.
  But 실제 상황에서 성능이 더 좋은 퀵 정렬, 병합 정렬 등이 더 자주 사용됩니다.

버블 gif 출처
선택 gif 출처